Debian Codegraph @

doc/dapl_event_design.txt

raw
1 DAPL Event Subsystem Design v. 0.96
2 -----------------------------------
3
4 =================
5 Table of Contents
6 =================
7
8 * Table of Contents
9 * Referenced Documents
10 * Goals
11 + Initial Goals
12 + Later Goals
13 * Requirements, constraints, and design inputs
14 + DAT Specification Constraints
15 + Object and routine functionality, in outline
16 + Detailed object and routine specification
17 + Synchronization
18 + IBM Access API constraints
19 + Nature of DAPL Event Streams in IBM Access API.
20 + Nature of access to CQs
21 + Operating System (Pthread) Constraints
22 + Performance model
23 + A note on context switches
24 * DAPL Event Subsystem Design
25 + OS Proxy Wait Object
26 + Definition
27 + Suggested Usage
28 + Event Storage
29 + Synchronization
30 + EVD Synchronization: Locking vs. Producer/Consumer queues
31 + EVD Synchronization: Waiter vs. Callback
32 + CNO Synchronization
33 + Inter-Object Synchronization
34 + CQ -> CQEH Assignments
35 + CQ Callbacks
36 + Dynamic Resizing of EVDs
37 + Structure and pseudo-code
38 + EVD
39 + CNO
40 * Future directions
41 + Performance improvements: Reducing context switches
42 + Performance improvements: Reducing copying of event data
43 + Performance improvements: Reducing locking
44 + Performance improvements: Reducing atomic operations
45 + Performance improvements: Incrementing concurrency.
46
47 ====================
48 Referenced Documents
49 ====================
50
51 uDAPL: User Direct Access Programming Library, Version 1.0. Published
52 6/21/2002. http://www.datcollaborative.org/uDAPL_062102.pdf.
53 Referred to in this document as the "DAT Specification".
54
55 InfiniBand Access Application Programming Interface Specification,
56 Version 1.2, 4/15/2002. In DAPL SourceForge repository at
57 doc/api/access_api.pdf. Referred to in this document as the "IBM
58 Access API Specification".
59
60 =====
61 Goals
62 =====
63
64 Initial goals
65 -------------
66 -- Implement the dat_evd_* calls described in the DAT Specification (except
67 for dat_evd_resize).
68
69 -- The implementation should be as portable as possible, to facilitate
70 HCA Vendors efforts to implement vendor-specific versions of DAPL.
71
72 Later goals
73 -----------
74 -- Examine various possible performance optimizations. This document
75 lists potential performance improvements, but the specific
76 performance improvements implemented should be guided by customer
77 requirements.
78
79 -- Implement the dat_cno_* calls described in the DAT 1.0 spec
80
81 -- Implement OS Proxy Wait Objects.
82
83 -- Implement dat_evd_resize
84
85 Non-goals
86 ---------
87 -- Thread safe implementation
88
89 ============================================
90 Requirements, constraints, and design inputs
91 ============================================
92
93 DAT Specification Constraints
94 -----------------------------
95
96 -- Object and routine functionality, in outline
97
98 The following section summarizes the requirements of the DAT
99 Specification in a form that is simpler to follow for purposes of
100 implementation. This section presumes the reader has read the DAT
101 Specification with regard to events.
102
103 Events are delivered to DAPL through Event Streams. Each Event Stream
104 targets a specific Event Descriptor (EVD); multiple Event Streams may
105 target the same EVD. The Event Stream<->EVD association is
106 effectively static; it may not be changed after the time at which
107 events start being delivered. The DAT Consumer always retrieves
108 events from EVDs. EVDs are intended to be 1-to-1 associated with the
109 "native" event convergence object on the underlying transport. For
110 InfiniBand, this would imply a 1-to-1 association between EVDs and
111 CQs.
112
113 EVDs may optionally have an associated Consumer Notification Object
114 (CNO). Multiple EVDs may target the same CNO, and the EVD<->CNO
115 association may be dynamically altered. The DAT Consumer may wait for
116 events on either EVDs or CNOs; if there is no waiter on an EVD and it
117 is enabled, its associated CNO is triggered on event arrival. An EVD
118 may have only a single waiter; a CNO may have multiple waiters.
119 Triggering of a CNO is "sticky"; if there is no waiter on a CNO when
120 it is triggered, the next CNO waiter will return immediately.
121
122 CNOs may have an associated OS Proxy Wait Object, which is signaled
123 when the CNO is triggered.
124
125 -- Detailed object and routine specification
126
127 Individual events may be "signaling" or "non-signaling", depending
128 on the interaction of:
129 * Receive completion endpoint attributes
130 * Request completion endpoint attributes
131 * dat_ep_post_send completion flags
132 * dat_ep_post_recv completion flags
133 The nature of this interaction is outside the scope of this document;
134 see the DAT Specification 1.0 (or, failing that, clarifications in a
135 later version of the DAT Specification).
136
137 A call to dat_evd_dequeue returns successfully if there are events on
138 the EVD to dequeue. A call to dat_evd_wait blocks if there are fewer
139 events present on the EVD than the value of the "threshold" parameter
140 passed in the call. Such a call to dat_evd_wait will be awoken by the
141 first signaling event arriving on the EVD that raises the EVD's event
142 count to >= the threshold value specified by dat_evd_wait().
143
144 If a signaling event arrives on an EVD that does not have a waiter,
145 and that EVD is enabled, the CNO associated with the EVD will be
146 triggered.
147
148 A CNO has some number of associated waiters, and an optional
149 associated OS Proxy Wait Object. When a CNO is triggered, two things
150 happen independently:
151 * The OS Proxy Wait Object associated with the CNO, if any, is
152 signaled, given the handle of an EVD associated with the CNO
153 that has an event on it, and disassociated from the CNO.
154 * If:
155 * there is one or more waiters associated with the
156 CNO, one of the waiters is unblocked and given the
157 handle of an EVD associated with the CNO that has an
158 event on it.
159 * there are no waiters associated with the CNO, the
160 CNO is placed in the triggered state.
161
162 When a thread waits on a CNO, if:
163 * The CNO is in the untriggered state, the waiter goes to
164 sleep pending the CNO being triggered.
165 * The CNO is in the triggered state, the waiter returns
166 immediately with the handle of an EVD associated with the
167 CNO that has an event on it, and the CNO is moved to the
168 untriggered state.
169
170 Note specifically that the signaling of the OS Proxy Wait Object is
171 independent of the CNO moving into the triggered state or not; it
172 occurs based on the state transition from Not-Triggered to Triggered.
173 Signaling the OS Proxy Wait Object only occurs when a CNO is
174 triggered. In contrast, waiters on a CNO are unblocked whenever the
175 CNO is in the triggered *state*, and that state is sticky.
176
177 Note also that which EVD is returned to the caller in a CNO wait is
178 not specified; it may be any EVD associated with the CNO on which an
179 event arrival might have triggered the CNO. This includes the
180 possibility that the EVD returned to the caller may not have any
181 events on it, if the dat_cno_wait() caller raced with a separate
182 thread doing a dat_evd_dequeue().
183
184 The DAT Specification is silent as to what behavior is to be expected
185 from an EVD after an overflow error has occurred on it. Thus this
186 design will also be silent on that issue.
187
188 The DAT Specification has minimal requirements on inter-Event Stream
189 ordering of events. Specifically, any connection events must precede
190 (in consumption order) any DTO Events for the same endpoint.
191 Similarly, any successful disconnection events must follow any DTO
192 Events for an endpoint.
193
194 -- Synchronization
195
196 Our initial implementation is not thread safe. This means that we do
197 not need to protect against the possibility of multiple simultaneous
198 user calls occurring on the same object (EVD, CNO, EP, etc.); that is
199 the responsibility of the DAT Consumer.
200
201 However, there are synchronization guards that we do need to protect
202 against because the DAT Consumer cannot. Specifically, since the user
203 cannot control the timing of callbacks from the IBM Access API
204 Implementation, we need to protect against possible collisions between
205 user calls and such callbacks. We also need to make sure that such
206 callbacks do not conflict with one another in some fashion, possibly
207 by assuring that they are single-threaded.
208
209 In addition, for the sake of simplicity in the user interface, I have
210 defined "not thread safe" as "It is the DAT Consumer's responsibility
211 to make sure that all calls against an individual object do not
212 conflict". This does, however, suggest that the DAPL library needs to
213 protect against calls to different objects that may result in
214 collisions "under the covers" (e.g. a call on an EVD vs. a call on its
215 associated CNO).
216
217 So our synchronization requirements for this implementation are:
218 + Protection against collisions between user calls and IBM
219 Access API callbacks.
220 + Avoidance of or protection against collisions between
221 different IBM Access API callbacks.
222 + Protection against collisions between user calls targeted at
223 different DAT objects.
224
225 IBM Access API constraints
226 --------------------------
227
228 -- Nature of DAPL Event Streams in IBM Access API
229
230 DAPL Event Streams are delivered through the IBM Access API in two fashions:
231 + Delivery of a completion to a CQ.
232 + A callback is made directly to a previously registered DAPL
233 function with parameters describing the event.
234 (Software events are not delivered through the IBM Access API).
235
236 The delivery of a completion to a CQ may spark a call to a previously
237 registered callback depending on the attributes of the CQ and the
238 reason for the completion. Event Streams that fall into this class
239 are:
240 + Send data transport operation
241 + Receive data transport operation
242 + RMR bind
243
244 The Event Streams that are delivered directly through a IBM Access API
245 callback include:
246 + Connection request arrival
247 + Connection resolution (establishment or rejection)
248 + Disconnection
249 + Asynchronous errors
250
251 Callbacks associated with CQs are further structured by a member of a
252 particular CQ Event Handling (CQEH) domain (specified at CQ creation
253 time). All CQ callbacks within a CQEH domain are serviced by the same
254 thread, and hence will not collide.
255
256 In addition, all connection-related callbacks are serviced by the same
257 thread, and will not collide. Similarly, all asynchronous error
258 callbacks are serviced by the same thread, and will not collide.
259 Collisions between any pair of a CQEH domain, a connection callback,
260 and an asynchronous error callback are possible.
261
262 -- Nature of access to CQs
263
264 The only probe operation the IBM Access API allows on CQs is
265 dequeuing. The only notification operation the IBM Access API
266 supports for CQs is calling a previously registered callback.
267
268 Specifically, the IB Consumer may not query the number of completions
269 on the CQ; the only way to find out the number of completions on a CQ
270 is through dequeuing them all. It is not possible to block waiting
271 on a CQ for the next completion to arrive, with or without a
272 threshold parameter.
273
274 Operating System Constraints
275 ----------------------------
276
277 The initial platform for implementation of DAPL is RedHat Linux 7.2 on
278 Intel hardware. On this platform, inter-thread synchronization is
279 provided by a POSIX Pthreads implementation. From the viewpoint of
280 DAPL, the details of the Pthreads interface are platform specific.
281 However, Pthreads is a very widely used threading library, common on
282 almost all Unix variants (though not used on the different variations
283 of Microsoft Windows(tm)). In addition, RedHat Linux 7.2 provides
284 POSIX thread semaphore operations (e.g. see sem_init(3)), which are
285 not normally considered part of pthreads.
286
287 Microsoft Windows(tm) provides many synchronization primitives,
288 including mutual exclusion locks, and semaphores.
289
290 DAPL defines an internal API (not exposed to the consumer), though
291 which it accesses Operating Systems Dependent services; this is called
292 the OSD API. It is intended that this layer contain all operating
293 system dependencies, and that porting DAPL to a new operating system
294 should only require changes to this layer.
295
296 We have chosen to define the synchronization interfaces established at
297 this layer in terms of two specific objects: mutexes and sempahores w/
298 timeout on waiting. Mutexes provide mutual exclusion in a way that is
299 common to all known operating systems. The functionality of
300 semaphores also exists on most known operating systems, though the
301 sempahores provided by POSIX do not provide timeout capabilities.
302 This is for three reasons. First, in contrast to Condition Variables
303 (the native pthreads waiting/signalling object), operations on
304 sempahores do not require use of other synchronization variables
305 (i.e. mutexes). Second, it is fairly easy to emulate sempahores using
306 condition variables, and it is not simple to emulate condition
307 variables using semaphores. And third, there are some anticipated
308 platforms for DAPL that implement condition variables in relation to
309 some types of locks but not others, and hence constrain appropriate
310 implementation choices for a potential DAPL interface modeled after
311 condition variables.
312
313 Implementation of the DAPL OS Wait Objects will initially be based on
314 condition variables (requiring the use of an internal lock) since
315 POSIX semaphores do not provide a needed timeout capability. However,
316 if improved performance is required, a helper thread could be created
317 that arranges to signal waiting semaphores when timeouts have
318 expired. This is a potential future (or vendor) optimization.
319
320 Performance Model
321 -----------------
322 One constraint on the DAPL Event Subsystem implementation is that it
323 should perform as well as possible. We define "as well as possible"
324 by listing the characteristics of this subsystem that will affect its
325 performance most strongly. In approximate order of importance, these
326 are:
327 + The number of context switches on critical path
328 + The amount of copying on the critical path.
329 + The base cost of locking (assuming no contention) on the
330 critical path. This is proportional to the number of locks
331 taken.
332 + The amount of locking contention expected. We make a
333 simplifying assumption and take this as the number of cycles
334 for which we expect to hold locks on the critical path.
335 + The number of "atomic" bus operations executed (these take
336 more cycles than normal operations, as they require locking
337 the bus).
338
339 We obviously wish to minimize all of these costs.
340
341 -- A note on context switches
342
343 In general, it's difficult to minimize context switches in a user
344 space library directly communicating with a hardware board. This is
345 because context switches, by their nature, have to go through the
346 operating system, but the information about which thread to wake up
347 and whether to wake it up is generally in user space. In addition,
348 the IBM Access API delivers all Event Streams as callbacks in user
349 context (as opposed to, for example, allowing a thread to block within
350 the API waiting for a wakeup). For this reason, the default sequence
351 of events for a wakeup generated from the hardware is:
352 * Hardware interrupts the main processor.
353 * Interrupt thread schedules a user-level IBM Access API
354 provider service thread parked in the kernel.
355 * Provider service thread wakes up the sleeping user-level
356 event DAT implementation thread.
357 This implies that any wakeup will involve three context switches.
358 This could be reduced by one if there were a way for user threads to
359 block in the kernel, we might skip the user-level provider thread.
360
361 ===========================
362 DAPL Event Subsystem Design
363 ===========================
364
365
366 OS Proxy Wait Object
367 --------------------
368
369 The interface and nature of the OS Proxy Wait Object is specified in
370 the uDAPL v. 1.0 header files as a DAT_OS_WAIT_PROXY_AGENT via the
371 following defines:
372
373 typedef void (*DAT_AGENT_FUNC)
374 (
375 DAT_PVOID, /* instance data */
376 DAT_EVD_HANDLE /* Event Dispatcher*/
377 );
378
379 typedef struct dat_os_wait_proxy_agent
380 {
381 DAT_PVOID instance_data;
382 DAT_AGENT_FUNC proxy_agent_func;
383 } DAT_OS_WAIT_PROXY_AGENT;
384
385 In other words, an OS Proxy Wait Object is a (function, data) pair,
386 and signalling the OS Proxy Wait Object is a matter of calling the
387 function on the data and an EVD handle associated with the CNO.
388 The nature of that function and its associated data is completely up
389 to the uDAPL consumer.
390
391 Event Storage
392 -------------
393
394 The data associated with an Event (the type, the EVD, and any type
395 specific data required) must be stored between event production and
396 event consumption. If storage is not provided by the underlying
397 Verbs, that data must be stored in the EVD itself. This may require
398 an extra copy (one at event production and one at event consumption).
399
400 Event Streams associated purely with callbacks (i.e. IB events that
401 are not mediated by CQs) or user calls (i.e. software events) don't
402 have any storage allocated for them by the underlying verbs and hence
403 must store their data in the EVD.
404
405 Event Streams that are associated with CQs have the possibility of
406 leaving the information associated with the CQ between the time the
407 event is produced and the time it is consumed. However, even in this
408 case, if the user calls dat_evd_wait with a threshold argument, the
409 events information must be copied to storage in the CQ. This is
410 because it is not possible to determine how many completions there are
411 on a CQ without dequeuing them, and that determination must be made by
412 the CQ notification callback in order to decide whether to wakeup a
413 dat_evd_wait() waiter. Note that this determination must be made
414 dynamically based on the arguments to dat_evd_wait().
415
416 Further, leaving events from Event Streams associated with the CQs "in
417 the CQs" until event consumption raises issues about in what order
418 events should be dequeued if there are multiple event streams entering
419 an EVD. Should the CQ events be dequeued first, or should the events
420 stored in the EVD be dequeued first? In general this is a complex
421 question; the uDAPL spec does not put many restrictions on event
422 order, but the major one that it does place is to restrict connection
423 events associated with a QP to be dequeued before DTOs associated with
424 that QP, and disconnection events after. Unfortunately, if we adopt
425 the policy of always dequeueing CQ events first, followed by EVD
426 events, this means that in situations where CQ events have been copied
427 to the EVD, CQ events may be received on the EVD out of order.
428
429 However, leaving events from Event Streams associated with CQs allows
430 us to avoid enabling CQ callbacks in cases where there is no waiter
431 associated with the EVDs. This can be a potentially large savings of
432 gratuitous context switches.
433
434 For the initial implementation, we will leave all event information
435 associated with CQs until dequeued by the consumer. All other event
436 information will be put in storage on the EVD itself. We will always
437 dequeue from the EVD first and the CQ second, to handle ordering among
438 CQ events in cases in which CQ events have been copied to the EVD.
439
440
441 Synchronization
442 ---------------
443
444 -- EVD synchronization: Locking vs. Producer/Consumer queues.
445
446 In the current code, two circular producer/consumer queues are used
447 for non-CQ event storage (one holds free events, one holds posted
448 events). Event producers "consume" events from the free queue, and
449 produce events onto the posted event queue. Event consumers consume
450 events from the posted event queue, and "produce" events onto the free
451 queue. In what follows, we discuss synchronization onto the posted
452 event queue, but since the usage of the queues is symmetric, all of
453 what we say also applies to the free event queue (just in the reverse
454 polarity).
455
456 The reason for using these circular queues is to allow synchronization
457 between producer and consumer without locking in some situations.
458 Unfortunately, a circular queue is only an effective method of
459 synchronization if we can guarantee that there are only two accessors
460 to it at a given time: one producer, and one consumer. The model will
461 not work if there are multiple producers, or if there are multiple
462 consumers (though obviously a subsidiary lock could be used to
463 single-thread either the producers or the consumers).
464
465 There are several difficulties with guaranteeing the producers and
466 consumers will each be single threaded in accessing the EVD:
467 * Constraints of the IB specification and IBM Access API
468 (differing sources for event streams without guarantees of
469 IB provider synchronization between them) make it difficult
470 to avoid multiple producers.
471 * The primitives used for the producer/consumer queue are not
472 as widely accepted as locks, and may render the design less
473 portable.
474
475 We will take locks when needed when producing events. The details of
476 this plan are described below.
477
478 This reasoning is described in more detail below to inform judgments
479 about future performance improvements.
480
481 * EVD producer synchronization
482
483 The producers fall into two classes:
484 * Callbacks announcing IA associated events such as connection
485 requests, connections, disconnections, DT ops, RMR bind,
486 etc.
487 * User calls posting a software event onto the EVD.
488
489 It is the users responsibility to protect against simultaneous
490 postings of software events onto the same EVD. Similarly, the CQEH
491 mechanism provided by the IBM Access API allows us to avoid collisions
492 between IBM Access API callbacks associated with CQs. However, we
493 must protect against software events colliding with IBM Access API
494 callbacks, and against non-CQ associated IB verb callbacks (connection
495 events and asynchronous errors) colliding with CQ associated IBM
496 Access API callbacks, or with other non-CQ associated IBM Access API
497 callbacks (i.e. a connection callback colliding with an asynchronous
498 error callback).
499
500 Note that CQ related callbacks do not act as producers on the circular
501 list; instead they leave the event information on the CQ until
502 dequeue; see "Event Storage" above. However, there are certain
503 situations in which it is necessary for the consumer to determine the
504 number of events on the EVD. The only way that IB provides to do this
505 is to dequeue the CQEs from the CQ and count them. In these
506 situations, the consumer will also act as an event producer for the
507 EVD event storage, copying all event information from the CQ to the
508 EVD.
509
510 Based on the above, the only case in which we may do without locking
511 on the producer side is when all Event Streams of all of the following
512 types may be presumed to be single threaded:
513 * Software events
514 * Non-CQ associated callbacks
515 * Consumer's within dat_evd_wait
516
517 We use a lock on the producer side of the EVD whenever we have
518 multiple threads of producers.
519
520 * EVD Consumer synchronization
521
522 It is the consumer's responsibility to avoid multiple callers into
523 dat_evd_wait and dat_evd_dequeue. For this reason, there is no
524 requirement for a lock on the consumer side.
525
526 * CQ synchronization
527
528 We simplify synchronization on the CQ by identifying the CQ consumer
529 with the EVD consumer. In other words, we prohibit any thread other
530 than a user thread in dat_evd_wait() or dat_evd_dequeue() from
531 dequeueing events from the CQ. This means that we can rely on the
532 uDAPL spec guarantee that only a single thread will be in the
533 dat_evd_wait() or dat_evd_dequeue() on a single CQ at a time. It has
534 the negative cost that (because there is no way to probe for the
535 number of entries on a CQ without dequeueing) the thread blocked in
536 dat_evd_wait() with a threshold argument greater than 1 will be woken
537 up on each notification on that CQ, in order to dequeue entries from
538 the CQ and determine if the threshold value has been reached.
539
540 -- EVD Synchronization: Waiter vs. Callback
541
542 Our decision to restrict dequeueing from the IB CQ to the user thread
543 (rather than the notification callback thread) means that
544 re-requesting notifications must also be done from that thread. This
545 leads to a subtle requirement for synchronization: the request for
546 notification (ib_completion_notify) must be atomic with the wait on
547 the condition variable by the user thread (atomic in the sense that
548 locks must be held to force the signalling from any such notification
549 to occur after the sleep on the condition variable). Otherwise it is
550 possible for the notification requested by the ib_completion_notify
551 call to occur before the return from that call. The signal done by
552 that notify will be ignored, and no further notifications will be
553 enabled, resulting in the thread sleep waiting forever. The CQE
554 associated with the notification might be noticed upon return from the
555 notify request, but that CQE might also have been reaped by a previous
556 call.
557
558 -- CNO Synchronization
559
560 In order to protect data items that are changed during CNO signalling
561 (OS Proxy Wait Object, EVD associated with triggering, CNO state), it
562 is necessary to use locking when triggering and waiting on a CNO.
563
564 Note that the synchronization between trigerrer and waiter on CNO must
565 take into account the possibility of the waiter returning from the
566 wait because of a timeout. I.e. it must handle the possibility that,
567 even though the waiter was detected and the OS Wait Object signalled
568 under an atomic lock, there would be no waiter on the OS Wait Object
569 when it was signalled. To handle this case, we make the job of the
570 triggerer to be setting the state to triggered and signalling the OS
571 Wait Object; all other manipulation is done by the waiter.
572
573 -- Inter-Object Synchronization
574
575 By the requirements specified above, the DAPL implementation is
576 responsible for avoiding collisions between DAT Consumer calls on
577 different DAT objects, even in a non-thread safe implementation.
578 Luckily, no such collisions exist in this implementation; all exported
579 DAPL Event Subsystem calls involve operations only on the objects to
580 which they are targeted. No inter-object synchronization is
581 required.
582
583 The one exception to this is the posting of a software event on an EVD
584 associated with a CNO; this may result in triggering the CNO.
585 However, this case was dealt with above in the discussion of
586 synchronizing between event producers and consumers; the posting of a
587 software event is a DAPL API call, but it's also a event producer.
588
589 To avoid lock hierarchy issues between EVDs and CNOs and minimize lock
590 contention, we arrange not to hold the EVD lock when triggering the
591 CNO. That is the only context in which we would naturally attempt to
592 hold both locks.
593
594 -- CQ -> CQEH Assignments
595
596 For the initial implementation, we will assign all CQs to the same
597 CQEH. This is for simplicity and efficient use of threading
598 resources; we do not want to dedicate a thread per CQ (where the
599 number of CQs may grow arbitrarily high), and we have no way of
600 knowing which partitioning of CQs is best for the DAPL consumer.
601
602 CQ Callbacks
603 ------------
604
605 The responsibility of a CQ callback is to wakeup any waiters
606 associated with the CQ--no data needs to be dequeued/delivered, since
607 that is always done by the consumer. Therefore, CQ callbacks must be
608 enabled when:
609 * Any thread is in dat_evd_wait() on the EVD associated with
610 the CQ.
611 * The EVD is enabled and has a non-null CNO. (An alternative
612 design would be to have waiters on a CNO enable callbacks on
613 all CQs associated with all EVDs associated with the CNO,
614 but this choice does not scale well as the number of EVDs
615 associated with a CNO increases).
616
617 Dynamic Resizing of EVDs
618 ------------------------
619
620 dat_evd_resize() creates a special problem for the implementor, as it
621 requires that the storage allocated in the EVD be changed in size as
622 events may be arriving. If a lock is held by all operations that use
623 the EVD, implementation of dat_evd_resize() is trivial; it substitutes
624 a new storage mechanism for the old one, copying over all current
625 events, all under lock.
626
627 However, we wish to avoid universal locking for the initial
628 implementation. This puts the implementation of dat_evd_resize() into
629 a tar pit. Because of the DAT Consumer requirements for a non-thread
630 safe DAPL Implementation, there will be no danger of conflict with
631 Event Consumers. However, if an Event Producer is in process of
632 adding an event to the circular list when the resize occurs, that
633 event may be lost or overwrite freed memory.
634
635 If we are willing to make the simplifying decision that any EVD that
636 has non-CQ events on it will always do full producer side locking, we
637 can solve this problem relatively easily. Resizing of the underlying
638 CQ can be done via ib_cq_resize(), which we can assume available
639 because of the IB spec. Resizing of the EVD storage may be done under
640 lock, and there will be no collisions with other uses of the EVD as
641 all other uses of the EVD must either take the lock or are prohibitted
642 by the uDAPL spec.
643
644 dat_evd_resize() has not yet been implemented in the DAPL Event
645 subsystem.
646
647 Structure and pseudo-code
648 -------------------------
649
650 -- EVD
651
652 All EVDs will have associated with them:
653 + a lock
654 + A DAPL OS Wait Object
655 + An enabled/disabled bit
656 + A CNO pointer (may be null)
657 + A state (no_waiter, waiter, dead)
658 + A threshold count
659 + An event list
660 + A CQ (optional, but common)
661
662 Posting an event to the EVD (presumably from a callback) will involve:
663 ^ + Checking for valid state
664 |lock A + Putting the event on the event list
665 | ^lock B + Signal the DAPL OS Wait Object, if appropriate
666 v v (waiter & signaling event & over threshold)
667 + Trigger the CNO if appropriate (enabled & signaling
668 event & no waiter). Note that the EVD lock is not
669 held for this operation to avoid holding multiple locks.
670
671 ("lock A" is used if producer side locking is needed. "lock B" is
672 used if producer side locking is not needed. Regardless, the lock is
673 only held to confirm that the EVD is in the WAITED state, not for
674 the wakeup).
675
676 Waiting on an EVD will include:
677 + Loop:
678 + Copy all elements from CQ to EVD
679 + If we have enough, break
680 + If we haven't enabled the CQ callback
681 + Enable it
682 + Continue
683 + Sleep on DAPL OS Wait Object
684 + Dequeue and return an event
685
686 The CQ callback will include:
687 + If there's a waiter:
688 + Signal it
689 + Otherwise, if the evd is in the OPEN state, there's
690 a CNO, and the EVD is enabled:
691 + Reenable completion
692 + Trigger CNO
693
694 Setting the enable/disable state of the EVD or setting the associated
695 CNO will simply set the bits and enable the completion if needed (if a
696 CNO trigger is implied); no locking is required.
697
698 -- CNO
699
700 All CNOs will have associated with them:
701 + A lock
702 + A DAPL OS Wait Object
703 + A state (triggered, untriggered, dead)
704 + A waiter count
705 + An EVD handle (last event which triggered the CNO)
706 + An OS Proxy Wait Object pointer (may be null)
707
708 Triggering a CNO will involve:
709 ^ + If the CNO state is untriggerred:
710 | + Set it to triggered
711 | + Note the OS Proxy wait object and zero it.
712 | + If there are any waiters associated with the CNO,
713 | signal them.
714 v + Signal the OS proxy wait object if noted
715
716 Waiting on a CNO will involve:
717 ^ + While the state is not triggered and the timeout has not occurred:
718 | + Increment the CNO waiter count
719 lock + Wait on the DAPL OS Wait Object
720 | + Decrement the CNO waiter count
721 v + If the state is trigerred, note fact&EVD and set to untrigerred.
722 + Return EVD and success if state was trigerred
723 + Return timeout otherwise
724
725 Setting the OS Proxy Wait Object on a CNO, under lock, checks for a
726 valid state and sets the OS Proxy Wait Object.
727
728
729 ==============
730 Known Problems
731 ==============
732
733 -- Because many event streams are actually delivered to EVDs by
734 callbacks, we cannot in general make any guarantees about the order
735 in which those event streams arrive; we are at the mercy of the
736 thread scheduler. Thus we cannot hold to the guarantee given by
737 the uDAPL 1.0 specification that within a particular EVD,
738 connection events on a QP will always be before successful DTO
739 operations on that QP.
740
741 Because we have chosen to dequeue EVD events first and CQ events
742 second, we will also not be able to guarantee that all successful
743 DTO events will be received before a disconnect event. Ability to
744 probe the CQ for its number of entries would solve this problem.
745
746
747 =================
748 Future Directions
749 =================
750
751 This section includes both functionality enhancements, and a series of
752 performance improvements. I mark these performance optimizations with
753 the following flags:
754 * VerbMod: Requires modifications to the IB Verbs/the IBM
755 Access API to be effective.
756 * VerbInteg: Requires integration between the DAPL
757 implementation and the IB Verbs implementation and IB device
758 driver.
759
760 Functionality Enhancements
761 --------------------------
762
763 -- dat_evd_resize() may be implemented by forcing producer side
764 locking whenever an event producer may occur asynchronously with
765 calls to dat_evd_resize() (i.e. when there are non-CQ event streams
766 associated with the EVD). See the details under "Dynamic Resizing
767 of EVDs" above.
768
769 -- [VerbMod] If we ahd a verbs modification allowing us to probe for
770 the current number of entries on a CQ, we could:
771 * Avoid waking up a dat_evd_wait(threshold>1) thread until
772 there were enough events for it.
773 * Avoid copying events from the CQ to the EVD to satisfy the
774 requirements of the "*nmore" out argument to dat_evd_wait(),
775 as well as the non-unary threshold argument.
776 * Implement the "all successful DTO operation events before
777 disconnect event" uDAPL guarantee (because we would no
778 longer have to copy CQ events to an EVD, and hence dequeue
779 first from the EVD and then from the CQ.
780 This optimization also is relevant for two of the performance
781 improvements cases below (Reducing context switches, and reducing
782 copies).
783
784
785 Performance improvements: Reducing context switches
786 ---------------------------------------------------
787 -- [VerbMod] If we had a verbs modification allowing us to probe for
788 the current size of a CQ, we could avoid waking up a
789 dat_evd_wait(threshhold>1) thread until there were enough events
790 for it. See the Functionality Enhancement entry covering this
791 possibility.
792
793 -- [VerbMod] If we had a verbs modification allowing threads to wait
794 for completions to occur on CQs (presumably in the kernel in some
795 efficient manner), we could optimize the case of
796 dat_evd_wait(...,threshold=1,...) on EVDs with only a single CQ
797 associated Event Stream. In this case, we could avoid the extra
798 context switch into the user callback thread; instead, the user
799 thread waiting on the EVD would be woken up by the kernel directly.
800
801 -- [VerbMod] If we had the above verbs modification with a threshold
802 argument on CQs, we could implement the threshold=n case.
803
804 -- [VerbInteg] In general, It would be useful to provide ways for
805 threads blocked on EVDs or CNOs to sleep in the hardware driver,
806 and for the driver interrupt thread to determine if they should be
807 awoken rather than handing that determination off to another,
808 user-level thread. This would allow us to reduce by one the number
809 of context switches required for waking up the various blocked
810 threads.
811
812 -- If an EVD has only a single Event Stream coming into it that is
813 only associated with one work queue (send or receive), it may be
814 possible to create thresholding by marking only ever nth WQE on
815 the associated send or receive WQ to signal a completion. The
816 difficulty with this is that the threshold is specified when
817 waiting on an EVD, and requesting completion signaling is
818 specified when posting a WQE; those two events may not in general
819 be synchronized enough for this strategy. It is probably
820 worthwhile letting the consumer implement this strategy directly if
821 they so choose, by specifying the correct flags on EP and DTO so
822 that the CQ events are only signaling on every nth completion.
823 They could then use dat_evd_wait() with a threshold of 1.
824
825 Performance improvements: Reducing copying of event data
826 --------------------------------------------------------
827 -- [VerbMod] If we had the ability to query a CQ for the number of
828 completions on it, we could avoid the cost of copying event data from the
829 CQ to the EVD. This is a duplicate of the second entry under
830 "Functionality Enhancements" above.
831
832 Performance improvements: Reducing locking
833 ------------------------------------------
834 -- dat_evd_dequeue() may be modified to not take any locks.
835
836 -- If there is no waiter associated with an EVD and there is only a
837 single event producer, we may avoid taking any locks in producing
838 events onto that EVD. This must be done carefully to handle the
839 case of racing with a waiter waiting on the EVD as we deliver the
840 event.
841
842 -- If there is no waiter associated with an EVD, and we create a
843 producer/consumer queue per event stream with a central counter
844 modified with atomic operations, we may avoid locking on the EVD.
845
846 -- It may be possible, though judicious use of atomic operations, to
847 avoid locking when triggering a CNO unless there is a waiter on the
848 CNO. This has not been done to keep the initial design simple.
849
850 Performance improvements: Reducing atomic operations
851 ----------------------------------------------------
852 -- We could combine the EVD circular lists, to avoid a single atomic
853 operation on each production and each consumption of an event. In
854 this model, event structures would not move from list to list;
855 whether or not they had valid information on them would simply
856 depend on where they were on the lists.
857
858 -- We may avoid the atomic increments on the circular queues (which
859 have a noticeable performance cost on the bus) if all accesses to an
860 EVD take locks.
861
862
863 Performance improvements: Increasing concurrency
864 ------------------------------------------------
865 -- When running on a multi-CPU platform, it may be appropriate to
866 assign CQs to several separate CQEHs, to increase the concurrency
867 of execution of CQ callbacks. However, note that consumer code is
868 never run within a CQ callback, so those callbacks should take very
869 little time per callback. This plan would only make sense in
870 situations where there were very many CQs, all of which were
871 active, and for whatever reason (high threshold, polling, etc)
872 user threads were usually not woken up by the execution of a
873 provider CQ callback.
874
875