On 26 August 2015 at 16:27, Savolainen, Petri (Nokia - FI/Espoo) <petri.savolai...@nokia.com> wrote: > > > > > From: lng-odp [mailto:lng-odp-boun...@lists.linaro.org] On Behalf Of ext > Bill Fischofer > Sent: Wednesday, August 26, 2015 12:26 AM > To: LNG ODP Mailman List > Subject: [lng-odp] [ARCH] Order Resolution APIs > > > > We've been discussion the question of when and how ordered events get > resolved and I'd like to summarize the pros and cons as well as offer an > additional suggestion to consider: > > > > When odp_schedule() dispatches an event in an ordered context the system > will guarantee that downstream queues will see events in the same relative > order as they appeared on the originating ordered queue. While most ordered > events are expected to be processed in a straightforward manner (one event > in, one event out) by a worker thread, there are two special cases of > interest that require special consideration. > > > > The first special case is removing an event from an ordered flow (one event > in, none out). The most common use-case for this scenario is IPfrag > reassembly where multiple fragments are received and stored into a > reassembly buffer but none is emitted until the last fragment completing the > packet arrives. > > > > The second special case is inserting one or more events into an ordered flow > (one event in, multiple events out). In this case what is desired is that > the multiple output events should appear in the input event's order on any > output queue(s) to which they are sent. The simplest use-case for this > scenario is packet segmentation where a large packet needs to be segmented > for MTU or other reasons, or perhaps it is being replicated for multicast > purposes. > > > > As currently defined, order is implicitly resolved upon the next call to > odp_schedule(). Doing this, however, may be very inefficient on some > platforms and as a result it is RECOMMENDED that threads running in ordered > contexts resolve order explicitly whenever possible. > > > > It is not defined how/where event order is resolved (inside enqueue, > release_order, next schedule call, dequeue from destination queue, …). > > > > The rules are: > > - Order *must* be resolved before events are dequeued from the > destination queue > > - Ordering is based on the ordering context and order is maintained > as long as thread holds the context > > - The context *can* be released after > odp_schedule_release_ordered() (user hints that ordering is not needed any > more) > > - The context *must* be released in next schedule call, if still > holding it > > > > > > Order can be explicitly resolved via the odp_schedule_release_ordered() API > that tells the scheduler that the thread no longer requires order to be > maintained. Following this call, the thread behaves as if it were running > in a (normal) parallel context and the thread MUST assume that further > enqueues it performs until the next odp_schedule() call will be unordered. > > > > For the first special case (removing events from an ordered flow), releasing > order explicitly MAY improve performance, depending on what the caller does > between the odp_schedule_release_ordered() call and its next call to > odp_schedule(). The more interesting (and apparently controversial) case > involves processing that involves one or more enqueues in an ordered > context. > > > > odp_schedule_release_ordered() may improve performance in all cases. It > tells to the implementation that > > - All enqueues (and potential other operations like tm_enqueue) > that need ordering are done > > - The last enq operation was “the last” > > - All remaining order locks will not be called > > - In general, all serialization / synchronization for this context > can be now freed > > > > > > In some implementations, ordering is maintained as part of the scheduler > while in others it is maintained as part of the queueing system. Especially > in systems that use HW assists for ordering, this can have meaningful > performance implications. In such systems, it is highly desirable that it > be known at enqueue time whether or not this is final enqueue that the > caller will make in the current ordered context. > > > > Example 1: > > ------------- > > > > enq() > > enq() > > enq() // <= final enqueue > > release_ordered() > > > > Example 2: > > ------------- > > enq() > > > > if(1) > > enq() // <= final enqueue > > else > > enq() > > > > if(0) > > enq() > > > > release_ordered() > > > > > > Example 3: > > ------------- > > enq() > > > > order_lock() > > order_unlock() > > > > if(1) > > tm_enq() // <= final operation which needs ordering > > else > > tm_enq() > > > > if(0) { > > order_lock() > > order_unlock() > > enq() > > } > > > > release_ordered() > > > > > > If implementation needs to identify the last enqueue, it needs to store the > latest enqueue until the next enq or release_ordered() call. As soon as it > sees release_ordered(), it knows which enqueue (or other operation requiring > ordering) was the final. > > > > > > There are several approaches that can be taken to provide this information. > One is to provide an additional parameter to odp_queue_enq() and > odp_queue_enq_multi() that explicitly says whether this is the final enqueue > for a given ordered context or not. Another approach is to have two > separate APIs that are used to indicate whether an enqueue should or should > not resolve order as part of its operation. > > > > In the v2 version of the Ordering patch I've posted, the latter approach is > used. The semantics of odp_queue_enq() and odp_queue_enq_multi() are > extended to include order resolution as part of their processing when used > in an ordered context. For the (relatively rare) cases in which multiple > enqueues are needed, the corresponding odp_queue_enq_sustain() and > odp_queue_enq_multi_sustain() APIs are provided. These simply perform > ordered enqueues without releasing the ordered context. > > > > The argument for having a new API to sustain order is that it is expected > that most processing involves a single event in and single event out, so a > different API call is needed only for the exceptional case. So to do > multiple enqueues in a single ordered contest the application would issue > odp_queue_enq_sustain() one or more times followed by a final > odp_queue_enq() call. In the (common) case where the application is only > issuing one enqueue, then odp_queue_enq() would be used as is the case > today. > > > > Yes, commonly application would enqueue one or few events, but it may not be > simple or known in advance which operations and how many the application is > going to do. See example 3 above. > > > > Another approach would be to have odp_queue_enq() and odp_queue_enq_multi() > sustain order by default and introduce new APIs odp_queue_enq_final() and > odp_queue_enq_multi_final() as alternates that would be used to resolve > order as part of the enqueue operation explicitly. In that case to enqueue > multiple events in an ordered contest the application would issue one or > more odp_queue_enq() calls followed by an odp_queue_enq_final() call. In > the (common) case where the application is only issuing one enqueue, then > odp_queue_enq_final() would be used. > > > > I’m suggesting that these optimizations would be added later on (if needed) > > > > odp_queue_enq_release_ctx() { > > odp_queue_enq() > > release_context() > > } > > > > odp_queue_enq_multi_release_ctx() { > > odp_queue_enq_multi() > > release_context() > > } > > > > odp_tm_enq_release_ctx() { > > odp_tm_enq() > > release_context() > > } > > > > odp_schedule_order_unlock_release_ctx() { > > odp_schedule_order_unlock() > > release_context() > > }
IMO, the above suggested optimisations will be needed for sure if we want to increase the performance of different implementations since if the implementation is required to maintain the context via cache for every odp_queue_enq() until the odp_schedule()/ odp_release_ordered() API gets called this will impact the performance of some implementations. on the other hand if the applications choose to execute odp_enq_final() for normal use-case when there is only one packet being processed then this call will be much faster than calling two APIs odp_queue_enq() and odp_release_ordered() consecutively as since in the case of odp_queue_enq_final() call the implementation moves the control directly to the underlying scheduler without going through the cache. So if we bring the optimised API at a sooner stage (as early as possible in 1.4) the applications can optimise the performance and tune it better for different implementations. > > > > The point is to make it very explicit when scheduling context (atomic or > ordered) is released, and possibly extend the optimization to other calls > which need ordering. > > > > > > It's really a question of which approach is more convenient for the > application writer, so I'd like to get some feedback on that question. > > > > See above J > > > > A third possibility would be to introduce both sustain and final variants of > odp_queue_enq() and allow the default behavior of the "unqualified" versions > of these APIs to be specified via another API, e.g., > odp_queue_enq_order_set(ODP_SUSTAIN | ODP_RESOLVE) and (probably) a > corresponding "getter" function odp_queue_enq_order() that would return the > default behavior. Applications could always explicitly call > odp_queue_enq_sustain() or odp_queue_enq_resolve() to be independent of this > setting if they wish. > > > > Another optimization could be introduction of explicitly non-ordered calls. > For example, if application is not ready to drop the ordered context yet but > could allow some enqueues to be delivered out-of-order. > > > > > > odp_queue_enq_no_sync() (or something similar) may not maintain ordering > even when called from ordered context and thus could be faster than normal > enqueue (from ordered context). Maybe this use-case of no synchronisation should be discussed in detail and we can even add a new UNORDERED type queue so that the events enqueued to this queue will not maintain any relative order with one another and the application can use this queue if the relative order is not required for the event anymore. Regards, Bala > > > > -Petri > > > > Any of these options are trivially doable by extending the current patch, so > I'd like some discussion of what would be the preferred approach from both > application writers and platform implementer's perspectives. Let's get some > views posted here and we can also discuss during tomorrow's ARCH call. > > > > Thanks. > > > > Bill > > > > > > > > > _______________________________________________ > lng-odp mailing list > lng-odp@lists.linaro.org > https://lists.linaro.org/mailman/listinfo/lng-odp > _______________________________________________ lng-odp mailing list lng-odp@lists.linaro.org https://lists.linaro.org/mailman/listinfo/lng-odp
