Re: [MirageOS-devel] mirageos 3.0 : let's break some APIs

[Hannes Mehnert <hannes@xxxxxxxxxxx>]

On 17/06/2016 11:26, Mindy wrote:
> To derail a bit, here are the CLOCK dependencies in tcpip:
> 
> * Arp could be refactored not to use wall-clock time for judging whether
> to expire entries, but a proper dynamic implementation still needs some
> dependency on the current TIME signature, I think.
> * ipv6 uses the clock for neighbor discovery protocol (lib/ipv6/ndpv6).
> I *believe* it's the case that, like ARP, this could be refactored to
> rely only on TIME, but I'm not very familiar with this code and would
> appreciate other opinions.
> * An ICMP implementation that provides timestamps would need CLOCK, as
> would a TCP that provides timestamps, but as far as I know we're not
> providing that functionality at the moment and that point is moot.
> * Some timers in TCP (lib/tcp/window.mli) currently compare wall clock
> time to figure out whether they need to act.  Like ARP, I think these
> could be refactored into sleeping threads, but since this code is much
> more involved and has higher performance demands I'm hesitant to make
> the claim boldly.  (There are a number of other apparent uses of Clock
> in TCP, but they all ultimately lead to invocations Window.Make.)

I doubt there is much practical usage of ICMP and TCP timestamps (apart
from geolocation exposure (see e.g.
http://sec.cs.ucl.ac.uk/users/smurdoch/papers/ccs06hotornot.pdf).  A
universe where a TCP/IP stack does not know anything about the absolute
time is desirable.

For the TCP sublibrary, I suspect that removing all the floats and calls
to Clock.now () will improve speed noticeable.

> Our existing use is a consequence of a pattern of implementing timers
> where we set some mutable state to a timestamp and then have a thread
> which occasionally compares this mutable state to the current time.  We
> could replace these with sleeping threads at the cost of increasing the
> number of threads running in the application, or probably by doing
> something more clever.  Links to cleverer ideas?

While sometimes it might be unavoidable to remember a value of a
(relative) timestamp and in the future comparing it with some added
delay, it is not my preferred solution.  It must encode the concrete
delay into the source code (bad for testing), and requires a dependency
to Clock (or better some monotonic counter, not there yet afaics).

I've no detailed insight into the scheduler, but my intuition is that
adding an enormous amount of sleepers (e.g. for each
maybe-to-be-retransmitted frame) does not scale.

What are alternatives?
 - pass in a timestamp - like charrua-core - it needs to deal with
timing out leases - but does so by accepting a float (immediately
converted to an int32) as input to input_pkt
(https://haesbaert.github.io/charrua-core/api/Dhcp_server.Input.html#VALinput_pkt)
- there's no dependency on Clock or scheduling some timeout task.  I'd
think that a similar solution can work for other caches, such as ARP cache.

 - tick event - like in ike (unfinished work) - your pure protocol
implementation has a concept of ticks (and requires that a tick occurs
every X ns) and performs the desired operations on a tick (see
https://github.com/isakmp/ike/blob/master/lwt/ike_lwt.ml and
https://github.com/isakmp/ike/blob/master/src/dispatcher.mli).  This
integrates neatly with purely functional protocols - no need to manually
call Clock or time - just define your tick interval (let's say for ARP
1500ms) and count ticks (expiration should be 150 seconds, just start
the expiry at 100 (*1500ms) and decrement on each tick.  once 0 is
reached, expire the entry).  It also fits well if you have e.g.
retransmissions:  while you send frame X and instantiate a timer "resend
in Y if no ACK received" (where you've to check for the "no ACK
received"), the tick event is just merged with other incoming events:
either your retransmit_at reaches 0 and you actually send out a new
packet, or you got rid of the retransmit frame 'coz you received an ACK
(assuming you've some list of packets_to_be_retransmitted in some
immutable state, and a handle : state -> input -> state * output (where
input is Tick | Bytes of Cstruct.t).

Certainly, the tick event needs an external timer in the effectful part
of the code (there might be use for a `on_timer : int64 -> bool ->
(event -> unit io) -> event` in the heart of MirageOS).

Using tick events also makes testing straightforward: instead of having
to accelerate the clock, and wait for timeouts, you can just pass in 5
tick events and see whether a new ARP request was generated as output.
If, similar to other libraries (like mirage-tls, lwt-tls), you contain
the state of a layer/handler as mutable field in the effectful piece of
code, this is the only piece of mutable state you need (and no exposure
thereof to the outside).


Guess there are more (maybe better?) alternatives, hope this was
understandable and helpful,

hannes

_______________________________________________
MirageOS-devel mailing list
MirageOS-devel@xxxxxxxxxxxxxxxxxxxx
http://lists.xenproject.org/cgi-bin/mailman/listinfo/mirageos-devel