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

[Thomas Leonard <talex5@xxxxxxxxx>]

On 17 June 2016 at 14:38, Hannes Mehnert <hannes@xxxxxxxxxxx> wrote:
> 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.

Some benchmarks would be good here. My guess is that the extra
indirection of an int64 would outweight the slowness of the FPU, but
it's only a guess. I doubt it makes much difference.

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

Concete delays (that go via an abstract TIME module) don't have to be
bad for testing. You just pass a clock that instantly moves forward to
the next scheduled event. See e.g. this test clock here:

https://github.com/talex5/cuekeeper/blob/ce81f4e3c40b79d99ac4063d22cfba4cd568e7e5/tests/test.ml#L27

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

Something has to decide:

- how long to sleep the unikernel
- what to do when it wakes

I don't see any reason why the scheduler should be worse at this that
the TCP stack. Presumably both would use a priority queue.

You might get a more compat representation by having e.g. an array of
packets and their timeouts, but then you'd have to keep searching the
array.

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

Sounds fine, although it might complicate the code in some places (and
if you return the time you want it to wait for and a callback to
invoke when done then you're just reimplementing Lwt, although
possibly making it clearer that there are fewer effects besides
waiting).

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

Wouldn't updating all these counters be really slow? And what stops
the ticks when the VM should go to sleep?

> 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 don't need to do this. Just run the virtual clock (at full CPU
speed) to the desired test time. e.g. (from the CueKeeper tests I
linked above) we have:

  [...]
  run_to_day 5;
  next_actions |> assert_tree [
    n "Next actions" [
      n "Coding" [
        n "Job" [
          n "GC unused signals" [];
          n "+Write unit tests" [];
        ]
      ];
      n "Review" [
        n "Weekly review" [];
      ]
    ];
    n "Recently completed" [];
  ];

This is much more efficient that inserting millions of tick events.

> 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



-- 
Dr Thomas Leonard        http://roscidus.com/blog/
GPG: DA98 25AE CAD0 8975 7CDA  BD8E 0713 3F96 CA74 D8BA

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