| 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 |
|