From: ext Bill Fischofer [mailto:bill.fischo...@linaro.org]
Sent: Thursday, August 27, 2015 3:16 AM
To: Savolainen, Petri (Nokia - FI/Espoo)
Cc: LNG ODP Mailman List
Subject: Re: [lng-odp] [ARCH] Order Resolution APIs
I've posted v3 of the scheduler/ordered queue patch incorporating the changes
we agreed to during today's ARCH call. I've also extended
test/validation/scheduler to add tests for the new Scheduler Group APIs.
There are a few points to note in using these APIs that I discovered in writing
the validation tests:
1. Because odp_queue_enq() and queue_enq_multi() now sustain order, the program
is running in an ordered context until it issues another odp_schedule(),
odp_schedule_multi(), or odp_schedule_release_order() call. In CUnit this can
cause problems for tests that get events via the scheduler and then end the
test. If they don't add a call to odp_schedule_release_context() they next
test may find itself running in the same ordered context and give unexpected
results. I had to add explicit release calls in a couple of tests for this
reason. Existing code that use "ordered queues" that in have been implemented
as atomic queues since the beginning of ODP may find similar issues with these
semantics, so beware.
Since release_atomic() and release_order() are hints. They may start and may
even finish the context release, but performance reasons the release is not
guaranteed to be finished when the function call returns. Only a schedule()
call which returns 0 events guarantee that a thread does not hold any more a
context. So each test case should call schedule() until no events come out and
only then exit or continue to the next test case.
This is all in the spec. Test cases may have not honored it in this detail.
2. Given that odp_schedule_release_order() and odp_schedule_release_atomic()
both take no arguments and implicitly refer to the current context, I think
it's simpler to just combine these into a single odp_schedule_release_context()
call. Especially useful for general cleanup code which may not know what
flavor of context it's running in. This was discussed before, but I didn't
want to depart from today's agreements in this patch. However it would be good
to get input from other implementations as to whether this would complicate
things for them. If agreeable, we can make this change as part of ODP v1.4
Agree we could deprecate specific calls and introduce release_ctx(). For same
reasons, I didn’t remove release_atomic but added release_order in this first
phase.
3. It was not at all clear to me how to use the new ordered lock semantics.
The arguments are there in the linux-generic code, but they are marked
ODP_UNUSED since the code refers to the current context implicitly rather than
to any external object. When I tried to incorporate them into the validation
test I discovered I had no way of knowing how to issue a proper
odp_schedule_order_lock_init() call. The issue is that this call takes both a
queue and a lock as arguments. The obvious way to organize locks is in to
declare them at the top of a thread and init them before entering the
scheduling loop.
Like a spinlock, it’s a global resource and you must init it only once e.g.
after queue create. The pointer can be stored to queue context data ( just like
a spinlock pointer). The lock is needed to protect some queue specific shared
data (e.g. sequence counter), so it’ not big deal to save the lock pointer
along the data.
-Petri
void my_worker_thread()
{
odp_schedule_order_lock_t my_ordered_lock;
odp_queue_t from;
...other declarations
...other init code
odp_schedule_order_lock_init(&my_ordered_lock, ??need an odp_queue_t
here--what to use??);
while (1) {
ev = odp_schedule(&from, ...);
odp_schedule_order_lock_init(&my_ordered_lock, from); /* Syntax
good, but is this what we want? */
...processing
odp_schedule_order_lock(&my_ordered_lock);
...ordered critical section
odp_schedule_order_unlock(&my_ordered_lock);
...finish up parallel stuff
}
}
The lock/unlock calls seem straightforward, but that init() call for the lock
is puzzling. The lock is going to be associated with the queue that the
scheduler has selected, however the thread has no way of knowing in advance
what that queue might be. If locks were somehow pre-initialized during queue
creation that imposes its own problems since again how is the worker supposed
to find the specific lock that was associated with the queue the scheduler
selected? Of course this gets even more confusing if we support multiple locks
per ordered context and expect this sort of tie-in.
Of course, having these "locks" be private to each thread is strange to begin
with since multiple threads processing events originating from the same ordered
queue are looking to synchronize with each other. So moving the init() call
into the while() loop so that the ordered lock is re-initialized on ever pass
with the queue is strange. And passing a globally-initialized lock as an
argument to the thread doesn't work since a the lock init() call references a
specific queue and again which queue the scheduler will next select is unknown.
This was the reason I defined ordered locks to simply implicitly refer to the
current ordered context, the same as all of the other APIs that relate to
ordering do. Unless I've missed something terribly obvious I think the current
definition of ordered locks is basically unusable.
Bill
On Wed, Aug 26, 2015 at 6:30 AM, Bill Fischofer
<bill.fischo...@linaro.org<mailto:bill.fischo...@linaro.org>> wrote:
Thanks. Yes, tm_enq() needs to be upgraded to handle ordering as well. That's
an upgrade to the implementation of those APIs that will be done as soon as the
implementation patches are posted. Basically, any enq() operation needs to
hook into the reordering logic if the event being enqueued originated from an
ordered queue. The patch as currently posted does this for "normal" target
queues as well as for PKTOUT queues. TM queues would need the same
consideration.
Any of the options you mention can be done easily in SW. The question is which
one do we pick to make it easy for implementations to map the ODP APIs
efficiently to their platforms, especially those that have ordering HW? That's
why I wanted feedback from implementers on this question.
While it's always possible to create arbitrarily complex API combinations for
illustrative purposes, do we have use cases to support such constructs? Right
now, the only use case for order insertion that have been mentioned is packet
segmentation and multicast. Are there others that anyone is aware of? Unless
such use cases are expected to be common, it would seem to make sense to
optimize the API semantics for the common case of one event in, one event out,
and require the use of additional APIs or variants for the exceptional cases.
That aligns both with the run-to-completion model as well as the performance
requirements of mainline data plane processing.
The one optimization you mention (unlock an ordered lock and simultaneously
release the ordered context) is not one I had considered since we haven't heard
any requirements for this sort of combined semantics. Does anyone have any
requirement for such a combined operation? If not then I'd agree that we not
create combinations for their own sake.
On Wed, Aug 26, 2015 at 5:57 AM, Savolainen, Petri (Nokia - FI/Espoo)
<petri.savolai...@nokia.com<mailto:petri.savolai...@nokia.com>> wrote:
From: lng-odp
[mailto:lng-odp-boun...@lists.linaro.org<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()
}
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 ☺
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).
-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
