[patch #7855] Provide alternative timeout implementation

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
URL:
  <http://savannah.nongnu.org/patch/?7855>

                 Summary: Provide alternative timeout implementation
                 Project: lwIP - A Lightweight TCP/IP stack
            Submitted by: rallysmith
            Submitted on: Thu 27 Sep 2012 03:36:58 PM GMT
                Category: None
                Priority: 5 - Normal
                  Status: None
                 Privacy: Public
             Assigned to: None
        Originator Email:
             Open/Closed: Open
         Discussion Lock: Any
         Planned Release: None

    _______________________________________________________

Details:

Attached is a patch that implements an absolute end-time based timeout scheme.
It is a large-ish patch, but is a NOP if the relevant "lwipopts.h" options are
not defined.

It is needed to fix the real-world problem of timeout drift affecting lwIP
correct operation. This can be seen on low-throughput systems if the
sys_arch_mbox_fetch() takes a significant amount of time to perform its work
and returns the SYS_ARCH_TIMEOUT state regardless of how much time has
actually passed; and can affect for example DHCP lease renewal (where I first
noticed the problem) since if the lease is short lwIP can hold onto an address
it is no longer entitled to because the DHCP coarse timeout drifts so far that
the renewal process is not started within the 50%->100% window.

NOTE: From searching Savannah it turns out Simon Goldschmidt had submitted a
patch (file#12539) to the bug#1902 report and some later changes aswell. None
of that work made it into the head of the tree though. This is an alternative
"absolute end-time" implementation and is not derived from that earlier work
by Simon.

Ideally, if the maintainers do not want to include this source into the
mainline, the mainline source SHOULD be updated to allow the actual
"sys_timeout()", "sys_untimeout()" and "sys_timeouts_mbox_fetch()" functions
to be over-ridden by architecture specific sourcefiles. i.e. a "lwipopts.h"
setting that stops the old DELTA code from being compiled by
"src/core/timers.c" thus allowing the run-time to provide target specific
versions. The need for an opaque "time" field within the timeout structure
will still remain and should be covered by the same change.




    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Thu 27 Sep 2012 03:36:58 PM GMT  Name: timeouts_absolute_endtime.patch
Size: 27kB   By: rallysmith

<http://savannah.nongnu.org/patch/download.php?file_id=26659>

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
Follow-up Comment #1, patch #7855 (project lwip):

i thnk that a relative timeout scheme is better suited for timeouts, as it is
easier to work with relative values in remainder class arithmetics. (by
forming a delta, you only need a one-side comparison ("is it due yet?") as
opposed to a two-side "is this timeout in the window i'm now working off?"
comparison).

the issue with timeout drift you menioned can easily be overcome by only
adjusting the `timeouts_last_time` parameter by as much time as actually
passed. i have just submitted patch #8244, which constitutes a better solution
in my opinion.

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
Follow-up Comment #2, patch #7855 (project lwip):

I do not see the "one-sided/two-sided comparison" point. Doing "endtime <=
now" is only a single comparison in the timeout list processing.

Irrespective of which approach is viewed as the "better" (since simplicity
over performance is always an on-going discussion :-) I do still believe that
my point about the lwIP allowing the timeout support to be overridden (via
lwipopts.h) to allow run-time specific implementations is valid. Such a change
would allow the baseline to continue to use deltas ... and would allow
developers to provide alternative implementations if better suited to the
specific run-time requirements.


    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
Follow-up Comment #3, patch #7855 (project lwip):

@comparison: `endtime <= now` does not catch the case when now is before the
timer wrap and endtime is after. you'd have to do at least `(endtime >
last_time_i_checked && endtime <= now) || (last_time_i_checked > now &&
endtime <= now)` -- or map times back to be deltas again internally, so that a
subtraction operation will take care of the wraps.

irrespective of that discussion, i support your approach of having a the
timeout functions exchangable, and do welcome an alternative implementation to
provide internal benchmarks. the point of my original comment here was mainly
to state that delta appraoch is not fundamentally broken, and to alert people
who might carelessly want to just drop the delta approach for an absolute
implementation (which wouldn't be you, but others who experience problems with
timeouts and wind up here).

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
Follow-up Comment #4, patch #7855 (project lwip):

Without digging too much into the patch again: by now I'd prefer a more
generic approach where stack-internal timers that are all cyclic timers (all
the timeout functions implemented in timers.c are) can be set up really cyclic
by the port (e.g. providing a constant table of cyclic timers to the port at
stack startup).

The rest of the timers (which are one-shot) doesn't care too much for drift, I
guess. Also, if drift was an issue on a specific platform, we could just make
sys_timeout/sys_untimeout overridable.

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Nachricht gesendet von/durch Savannah
  http://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
Follow-up Comment #5, patch #7855 (project lwip):

going back to cyclic timers would make it harder to run lwip in setups where
sleep is actually spent in hardware sleep with a configured interrupt.

how about having an additional sys_timeout_continue function, which would
schedule the next timeout relative to when the currently handled one should
have happened? this would make adding stable cyclic timers easy, and
alternative sys_timeout implementations could still decide not to implement it
(ie. alias it to sys_timeout) if they can't provide for drift-free time
keeping anyway.

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
Follow-up Comment #6, patch #7855 (project lwip):

> Follow-up Comment #4, patch #7855 (project lwip):
> ... Also, if drift was an issue on a specific platform, ...

Nope. Drift can occur on any platform with the "existing" lwIP design if
SYS_ARCH_TIMEOUT is returned. As previously mentioned it would just have a
more noticeable effect on lower CPU throughput systems. I first fixed the
problem (using a variant of this patch) ~4 years ago on a relativel slow
<60MHz AT91SAM7 design, and then when I got to my current company it exhibited
on a few different architectures (m68k, arm, mips, etc.) including some
relatively fast designs.

However, whatever design/patch is finally "committed to the head" I would be
happy with as long as the result is drift free :-)

If nothing else the concept of allowing a platform to override the lwIP timer
support via "opt.h" would be a good thing, regardless of whatever
implementation actually exists.

So,

> Follow-up Comment #4, patch #7855 (project lwip):
> ... we could just make sys_timeout/sys_untimeout overridable

gets my vote.

Was there ever an objection to the creation of SYS_TIME_TYPE and STTT_F to
make "time" opaque? (and the corresponding sys_arch_time_before()
macro/function to allow an opaque time object).



    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
Follow-up Comment #7, patch #7855 (project lwip):

> going back to cyclic timers would make it harder to run lwip
> in setups where sleep is actually spent in hardware sleep with
> a configured interrupt.

I can't follow that thought. As long as there's a way of telling lwIP how much
time has passed (this could even work by comparing return values of
sys_now()), it doesn't matter if you idle-loop or really sleep.

> Drift can occur on any platform with the "existing" lwIP
> design if SYS_ARCH_TIMEOUT is returned.

Of course. The question is whether that's a problem or not. The only problem I
see is the DHCP lease time, the rest of the timers shouldn't care for (rather
small) drift.

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Nachricht gesendet von/durch Savannah
  http://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
Follow-up Comment #8, patch #7855 (project lwip):

> The only problem I see is the DHCP lease time,
> the rest of the timers shouldn't care for (rather
> small) drift.

Agreed. Normally small amounts of drift would not be an issue for general
network operations (and that may be why people, especially those using static
interface configurations, have been successfully served by the current lwIP
implementation).

However, some protocols do require relatively high-frequency accurate
multi-packet timing (for exampled mDNS) or have externally visible timing
constraints like DHCP (again mDNS). We have a lwIP mDNS implementation that
passes the Bonjour Conformance Test on all the platforms we support (with this
patch applied), but it would not pass on all when using the current mainline
lwIP timer support.

Having lwIP generically support "accurate" timing would avoid support hiccups
in the future. As opposed to having some special cases implemented (e.g.
specific code for DHCP) that need to be tweaked/extended as lwIP evolves.


    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
Follow-up Comment #9, patch #7855 (project lwip):

Hello,
absolute timing is actually really great and simplifies stuff everywhere
(exaggerated, but well...).

See this sorting/comparison invariant which is in use in my code:

template< typename T, typename S = typename
std::enable_if<std::is_unsigned<T>::value>::type >
bool time_overflow_compare(T a, T b)
{
    return T(b - a) <= (std::numeric_limits<T>::max() / 2);
}

I use this pattern to convert lwip timing calls to my own replaced timing. I
posted another patch proposal to allow custom timing on NO_SYS build.

Kind Regards

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Nachricht gesendet von/durch Savannah
  http://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
Follow-up Comment #10, patch #7855 (project lwip):

Oh, another idea might be to let the timer handler function return a new
timeout (or 0/UINT_MAX/...) rather than re-registering. It seems reasonable to
store timeout timers in a heap, in which case one could reuse the spot and
sift-down instead of pop+push. But that's maybe just a micro-optimization ;)

    _______________________________________________________

Reply to this item at:

  <http://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Nachricht gesendet von/durch Savannah
  http://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel
Reply | Threaded
Open this post in threaded view
|

[patch #7855] Provide alternative timeout implementation

madhu
Update of patch #7855 (project lwip):

                  Status:                    None => Wont Do                
             Open/Closed:                    Open => Closed                

    _______________________________________________________

Follow-up Comment #11:

I don't think we need this any more, timeouts have changed since then.

    _______________________________________________________

Reply to this item at:

  <https://savannah.nongnu.org/patch/?7855>

_______________________________________________
  Message sent via Savannah
  https://savannah.nongnu.org/


_______________________________________________
lwip-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/lwip-devel