1 package nl.openfortress.android6bed4;
4 import java.util.Hashtable;
5 import java.util.Queue;
6 import java.util.ArrayDeque;
8 import java.net.DatagramPacket;
9 import java.net.DatagramSocket;
10 import java.net.InetSocketAddress;
11 import java.net.Inet4Address;
12 import java.net.UnknownHostException;
14 import java.io.IOException;
18 /* The Neighbor Cache is modelled in Java, because Android/Java won't
19 * give access to the network stack.
21 * The primary task of the cache is to map IPv6-addresses in byte [16]
22 * format to a destination, which is stored as a Inet4SocketAddress
23 * for direct use with DatagramPacket facilities in Java. A hash is
24 * used to gain fast access to the target object.
26 * To find mappings, the cache will send up to 3 Neighor Solicitation
27 * messages to the direct peer. During this period it will pass through
28 * states ATTEMPT1 to ATTEMPT3, and finally become FAILED. This is a sign
29 * that no further attempts need to be made until the expiration of the
30 * mapping, about 30 seconds after starting it. This process starts
31 * when an unknown peer is approached, or one that is STALE.
33 * If a Neighbor Advertisement comes in, this information is sent here
34 * for processing. The cache entry will usually go to REACHABLE in such
37 * When traffic comes in with the direct address of this peer as its
38 * destination, then the cache is informed; if no mapping in REACHABLE
39 * state exists, then new attempts are started, so as to enable direct
40 * connectivity after the remote peer has opened a hole to us.
42 * The cache maintains a seperate timer queue for each state, and will
43 * act upon the objects if they expire. This makes the queue rather
46 * Before changing any piece of this code, please assure yourself that
47 * you understand each single synchronized section, and convince
48 * yourself that you understand the trick in NeighborQueue.dequeue().
49 * This is not just multitasking code; it may well be the most complex
50 * example of multitasking code that you ever came accross. Do not
51 * change the code unless you are absolutely certain that you have
52 * understood all the invariants that make this code work!
57 /* The states of neighbors in the cache.
59 public final static int ATTEMPT1 = 0; /* Discovery sequence */
60 public final static int ATTEMPT2 = 1;
61 public final static int ATTEMPT3 = 2;
62 public final static int FAILED = 3;
63 public final static int REACHABLE = 4; /* Confirmed in the last ~30s */
64 public final static int STALE = 5; /* Not used for up to ~30s */
65 public final static int NUM_NGB_STATES = 6; /* Count of normal states */
66 public final static int INTRANSIT = 7; /* Traveling between queues */
69 /* The timing spent in the various states of a cache entry. Stable states
70 * take up several seconds, while waiting for a response is faster.
71 * Note the remarks at NeighborQueue.dequeue() for an important constraint;
72 * specifically, STALE is spent in an attempt to recycle an entry as
73 * REACHABLE, so the time spent in STALE must not exceed the time spent
74 * in REACHABLE. This avoids having two entries for one neighbor in a
75 * queue, which would jeapourdise the timeout calculations. Note that
76 * this problem does not arise when an object occurs in multiple queues
77 * at once, because a mismatch with the queue's state means that those
78 * lingering neighbors are ignored as timeout sources.
80 * TODO: I found that Android can be pretty slow in responding over eth0,
81 * possibly worse over UMTS or (shiver) GPRS. So, it may be that the
82 * following timing must be slowed down, *or* that NgbAdv ought to be
83 * accepted in the STALE state.
85 final static int state_timing_millis [] = {
86 50, 50, 50, 30000, /* Discovery -- a few ms between steps */
87 27500, /* STALE -- 30 additional seconds */
88 30000 /* REACHABLE -- 30 seconds of bliss */
91 /* The timer queues for neighbor discovery, each in its own thread */
92 NeighborQueue queues [];
94 /* The neighbor cache contains all elements, regardless of their state.
95 * This is needed to avoid doing double work. If a neighbor is considered
96 * to be available, then it should be in here. Once it stops being of
97 * interest (STALE or FAILED expires) it will be removed.
99 * Note that the key and value are both Neighbor objects. The only part
100 * of the Neighbor dictating equality (and the hashCode) is the 6-byte
101 * key holding the remote peer's IPv4 address and UDP port, so it is
102 * possible to put one object into the Hashtable as both key and value;
103 * and then to lookup an entry with a minimally setup Neighbor as key
104 * to find a more evolved value; the latter will be incorporated into
105 * the procedures of the Neighbor Cache, including the various queues.
107 private Hashtable <Neighbor, Neighbor> neighbor_cache;
110 /* The public server, used as default return value for queires after
111 * unsettled neighbor cache entries.
113 private InetSocketAddress public_server;
116 /* The socket used as uplink to the rest of the 6bed4-using World.
118 private DatagramSocket uplink;
121 /* The 6bed4 address as a 16-byte array; may also be used as an 8-byte prefix.
123 private byte address_6bed4 [];
125 /* The 6bed4 address as a 6-byte key.
127 private byte address_6bed4_key [];
130 /* Construct a neighbor cache with no entries but a lot of structure */
131 public NeighborCache (DatagramSocket ipv4_uplink, InetSocketAddress pubserver, byte link_address_6bed4 []) {
132 uplink = ipv4_uplink;
133 public_server = pubserver;
134 address_6bed4 = new byte [16];
135 TunnelService.memcp_address (address_6bed4, 0, link_address_6bed4, 0);
136 address_6bed4_key = new byte [6];
137 address2key (address_6bed4, 0, address_6bed4_key);
138 queues = new NeighborQueue [NUM_NGB_STATES];
139 for (int i=0; i < NUM_NGB_STATES; i++) {
140 queues [i] = new NeighborQueue (this, i);
142 neighbor_cache = new Hashtable <Neighbor,Neighbor> ();
145 /* Remove an expired entry from the neighbor cache.
147 public void remove_from_cache (Neighbor ngb) {
148 byte key [] = new byte [6];
149 socketaddress2key (ngb.target, key);
150 synchronized (neighbor_cache) {
151 neighbor_cache.remove (key);
155 /* Attempt to retrieve an entry from the neighbor cache. The resulting
156 * actions as well as the return value may differ, depending on the
157 * state of the cache entry. This function always returns immediately,
158 * with the tunnel server as a default response for instant connections,
159 * but the cache may asynchronously attempt to find a direct path to the
162 * The "playful" argument is rather special. When set to true, it
163 * indicates that an initial experiment attempting to contact the
164 * neighbor directly is acceptable. This is usually the cae if the
165 * following conditions apply:
166 * 1. The message is resent upon failure
167 * 2. Success can be recognised and reported back here
168 * Setting this flag causes the first (and only the first) result
169 * from lookup_neighbor to point directly to the host; resends will
170 * be sent through the tunnel, while a few neighbor discoveries are
171 * still tried towards the remote peer, until something comes back
172 * directly to acknowledge contact. When something comes back over
173 * a direct route, this should be reported to the neighbor cache
174 * through received_neighbor_direct_acknowledgement() so it can
175 * learn that future traffic can be directly sent to the peer.
177 * A common case for which this holds is TCP connection setup:
178 * 1. Packets with SYN are sent repeatedly if need be
179 * 2. Packets with ACK stand out in a crowd
180 * So, when TCP packets with SYN are sent, their lookup_neighbor()
181 * invocation can set the playful flag; the first attempt will go
182 * directly to the peer and hopefully initiate direct contact; if
183 * not, future attempts are sent through the tunnel. When the
184 * remote peer accepts, it will return a packet with ACK set over
185 * the direct route, which is enough reason to signal success to
186 * the neighbor cache. Interestingly, the first reply message
187 * from a TCP server will generally hold the SYN flag as well, so
188 * if the remote 6bed4 stack is also playful about TCP, it is
189 * likely to send it back directly even if it received the opening
190 * SYN through the tunnel. This means that even a blocking NAT on
191 * the remote end will cause a new attempt on return. As usual,
192 * an ACK from client to server follows, which asserts to the
193 * server that it can talk directly (because, at that time, the
194 * client has picked up on the directly sent SYN+ACK).
196 * It is possible for TCP to initiate a connection from both ends
197 * at the same time. Effectively this splits the SYN+ACK into
198 * two messages, one with SYN and one with ACK. It may happen
199 * that direct contact is not correctly established if that is
200 * done, but the follow-up neighbor discovery that follow on a
201 * playful SYN that does not return an ACK over the direct route
202 * will establish NAT-passthrough if it is technically possible.
203 * A similar thing occurs when the initial SYN is lost for some
206 public InetSocketAddress lookup_neighbor (byte addr [], int addrofs, boolean playful) {
207 if (!is6bed4 (addr, addrofs)) {
208 return public_server;
210 boolean puppy = false;
212 byte seeker_key [] = new byte [6];
213 address2key (addr, addrofs, seeker_key); //TODO// Only used for seeker creation?
214 Neighbor seeker = new Neighbor (seeker_key);
215 synchronized (neighbor_cache) {
216 ngb = neighbor_cache.get (seeker);
218 ngb = new Neighbor (seeker_key); //TODO// Possibly seeker.clone ()
219 neighbor_cache.put (ngb, ngb);
230 // No usable entry exists, but no new attempts are needed.
231 // Simply return the default router's address.
233 // If the new entry was just inserted into the neighbor
234 // cache for this thread, then enqueue into ATTEMPT1, part
235 // of which is sending a neighbor solicitation. However,
236 // if the request is made by a playful puppy, then skip
237 // sending the Neighbor Discovery upon insertion into the
238 // ATTEMPT1 queue; the 6bed4 stack will instead send the
239 // initial message directly to the peer. To that end, return
240 // the direct neighbor instead of the safe default of the
241 // public server. Note that a repeat of the packet will
242 // no longer count as a puppy, so this is done only once.
244 queues [ATTEMPT1].enqueue (ngb, playful);
249 return public_server;
252 // The neighbor has been reached directly before; assume this
253 // is still possible (continue into REACHABLE) but also send a
254 // neighbor solicitation to keep the lines open.
255 solicit_neighbor (ngb);
258 // The neighbor is known to be available for direct contact.
259 // There is no work to be done to that end.
266 /* Send a Neighbor Solicitation to the peer. When this succeeds at
267 * penetrating to the remote peer's 6bed4 stack, then a Neighbor
268 * Advertisement will return, and be reported through the method
269 * NeighborCache.received_neighbor_direct_acknowledgement() so the
270 * cache can update its state, and support direct sending to the
273 public void solicit_neighbor (Neighbor ngb) {
274 byte key [] = new byte [6];
275 socketaddress2key (ngb.target, key);
276 byte ngbsol [] = new byte [72];
280 ngbsol [1] = ngbsol [2] = ngbsol [3] = 0;
281 ngbsol [4] = 0; ngbsol [5] = 4 + 28;
282 ngbsol [6] = TunnelService.IPPROTO_ICMPV6;
283 ngbsol [7] = (byte) 255;
284 TunnelService.memcp_address (ngbsol, 8, address_6bed4, 0);
285 key2ipv6address (key, ngbsol, 24);
288 ngbsol [ofs++] = (byte) TunnelService.ND_NEIGHBOR_SOLICIT;
290 ofs += 2; // Checksum
294 ngbsol [ofs++] = 0x00;
295 key2ipv6address (ngb.key, ngbsol, ofs);
297 // ICMPv6 Option: Source Link-Layer Address
298 ngbsol [ofs++] = 1; // SrcLLAddr
299 ngbsol [ofs++] = 1; // length is 1x 8 bytes
300 for (int i=0; i<6; i++) {
301 ngbsol [ofs++] = address_6bed4_key [i];
303 int csum = TunnelService.checksum_icmpv6 (ngbsol, 0);
304 ngbsol [42] = (byte) ((csum >> 8) & 0xff);
305 ngbsol [43] = (byte) ( csum & 0xff);
307 DatagramPacket pkt = new DatagramPacket (ngbsol, ngbsol.length, ngb.target);
309 } catch (IOException ioe) {
314 /* The TunnelServer reports having received a neighbor advertisement
315 * by calling this function. This may signal the cache that the
316 * corresponding cache entry needs updating.
318 public void received_neighbor_direct_acknowledgement (byte addr [], int addrofs) {
320 byte key [] = new byte [6];
321 address2key (addr, addrofs, key);
322 Neighbor seeker = new Neighbor (key);
323 synchronized (neighbor_cache) {
324 ngb = neighbor_cache.get (seeker);
336 // There is an entry waiting to be resolved.
337 // Apply the lessons learnt to that entry.
338 // Be careful -- another thread may be trying
339 // the same, so we use the dequeue function
340 // that checks again before proceeding.
341 if (queues [nst].dequeue (ngb)) {
343 // Only one thread will continue here, having dequeued the neighbor
344 queues [REACHABLE].enqueue (ngb);
350 // A persistent state has been reached, and any
351 // advertisements coming in have missed their
352 // window of opportunity. Note that this may be
353 // a sign of attempted abuse. So ignore it.
357 // Some thread is already working on this neighbor, so drop
358 // this extra notification.
366 /* The Neighbor class represents individual entries in the NeighborCache.
367 * Each contains an IPv6 address as 16 bytes, its state, and a timeout for
368 * its current state queue.
370 * Most of this class is storage, and is publicly accessible by the
371 * other components in this class/file.
373 * Note that the Neighbor class serves in the hashtable as a key and value;
374 * but as a key, the only input used are the 6 bytes with the remote peer's
375 * IPv4 address and UDP port. This means that another object can easily be
376 * constructed as a search entry, to resolve into the full entry.
378 * TODO: Inner class -- does that mean that the context is copied into this object? That'd be wasteful!
382 protected InetSocketAddress target;
383 protected long timeout;
386 /* The hashCode for this object depends solely on the key value.
387 * Integrate all the bits of the key for optimal spreading. The
388 * hashCode may only differ if the equals() output below also
391 public int hashCode () {
392 return key2hash (key);
395 /* The equals output determines that two Neighbor objects are
396 * the same if their key matches; that is, if their remote
397 * IPv4 address and UDP port is the same. It is guaranteed
398 * that the hashCode is the same for two equal objects; if two
399 * objects are unequal then their hashCode is *likely* to differ,
400 * but not guaranteed.
402 public boolean equals (Object oth) {
404 Neighbor other = (Neighbor) oth;
405 for (int i=0; i<5; i++) {
406 if (this.key [i] != ((Neighbor) other).key [i]) {
411 } catch (Throwable thr) {
416 /* Construct a new Neighbor based on its 6-byte key */
417 public Neighbor (byte fromkey []) {
419 for (int i=0; i<6; i++) {
420 key [i] = fromkey [i];
422 state = NeighborCache.ATTEMPT1;
423 target = key2socketaddress (key);
427 /* The NeighborQueue subclass represents a timer queue. The objects in this
428 * queue each have their own timeouts, as specified by state_timing_millis.
429 * New entries are attached to the back, timeouts are picked up at the front.
431 * The queues have understanding of the various states, and how to handle
434 class NeighborQueue extends Thread {
436 private NeighborCache cache;
438 private Queue <Neighbor> queue;
440 public NeighborQueue (NeighborCache owner, int mystate) {
443 queue = new ArrayDeque <Neighbor> ();
450 // First, fetch the head element (or wait for one to appear).
451 // Sample its timeout. Even if the head disappears later on,
452 // any further entries are certain to have a later timeout.
454 synchronized (queue) {
455 Neighbor head = null;
456 while (head == null) {
457 head = queue.peek ();
461 } catch (InterruptedException io) {
466 if (head.state == whoami) {
469 timeout = head.timeout;
473 // Now wait until the timeout expires. This is not done in
474 // a synchronous fashion, so the queue can be changed as
475 // desired by other threads. Note that misplaced items
476 // in the queue will be removed by the code further down
477 // before this thread can find rest.
480 sleep (timeout - System.currentTimeMillis ());
481 } catch (InterruptedException ie) {
486 // Now the time has come to remove the head elements that
487 // have expired. If nothing happened to the head of the
488 // queue, then this one should at least be removed, but
489 // following entries may just as well need removal. Do
490 // this in a queue-synchronous manner to stop other threads
491 // from altering the queue.
492 long now = System.currentTimeMillis ();
493 Queue <Neighbor> removed = new ArrayDeque <Neighbor> ();
494 synchronized (queue) {
495 Neighbor head = queue.peek ();
496 while ((head != null) && ((head.state != whoami) || (head.timeout <= now))) {
497 head = queue.remove ();
498 if (head.state == whoami) {
499 removed.offer (head);
500 } // else, misplaced item that can be silently dropped
501 head = queue.peek ();
505 // We now have a few elements in a temporary removed list;
506 // handle those by inserting them into their next lifecycle
507 // state (possibly meaning, destroy them).
510 /* TODO: Why would we want to remove the remote socket address?
512 // Remove the remote socket address, and continue with
513 // promotion to the next lifecycle state
514 for (Neighbor ngb : removed) {
522 // Promote the neighbor to its next lifecycle state
523 for (Neighbor ngb : removed) {
524 queues [whoami + 1].enqueue (ngb);
530 // Remove the neighbor from the cache
531 for (Neighbor ngb : removed) {
532 cache.remove_from_cache (ngb);
541 /* Insert a new element into the queue. If this is the first
542 * entry, be sure to notify the thread that may be waiting for
543 * something to chew on.
544 * Note that an entry may be enqueued only once, use dequeue
545 * to remove it from a possible former queue.
547 public void enqueue (Neighbor ngb) {
548 enqueue (ngb, false);
551 /* Insert a new element into the queue. If this is the first
552 * entry, be sure to notify the thread that may be waiting for
553 * something to chew on.
554 * Note that an entry may be enqueued only once, use dequeue
555 * to remove it from a possible former queue.
556 * The flag "no_action" requests that the side-effects that
557 * may take place after inserting the element in the queue
560 public void enqueue (Neighbor ngb, boolean no_action) {
562 // Initialise the neighbor for this queue
564 ngb.timeout = System.currentTimeMillis () + NeighborCache.state_timing_millis [whoami];
566 // Insert the Neighbor into the queue
567 synchronized (queue) {
568 boolean wasEmpty = queue.isEmpty ();
575 // Skip the side-effect of insertion is so desired.
580 // If this queue represents waiting for a reply to Neighbor
581 // Solicitation, then solicit the neighbor. This is not
582 // synchronous, because networking does not directly modify
583 // the queue, is slow and is asynchronous in nature anyway.
588 cache.solicit_neighbor (ngb);
595 /* Remove an element from the queue without awaiting timer
596 * expiration. This is only of interest when incoming traffic
597 * follows a direct route, while our previous attempts ran into
598 * FAILED because the remote didn't have its ports open for us yet.
599 * In addition, this may be used when a timer has gone STALE.
600 * Note that expiration timers on the queue can continue to run,
601 * they may simply find that the first element has not timed out
602 * and another cycle is needed for what is then the head.
603 * The state and timeout of the neighbor entry will not be modified
604 * by this call, but future enqueueing may do that nonetheless.
605 * The function returns success; that is, it tells the caller if
606 * the object was indeed found in the queue.
608 * *** Implementation note ***
610 * Dequeueing is expensive, as it involves going through the list
611 * of stored items. Keeping the structures up to date to speedup
612 * this operation is hardly more pleasant. So, we'll use a trick.
613 * We simply won't dequeue. This means that queues can hold items
614 * that should have been removed. As long as objects never cycle
615 * back to this queue before their timers in this queue have
616 * expired, the misplacement of a queue item could be directly
617 * inferred from the state, which does not match the queue's state.
618 * Such misplaced items can be silently removed. Doing this, the
619 * only remaining task for dequeue is to change the state in an
620 * atomic fashion -- that is, without risk of overlapping similar
621 * operations by other threads. As originally intended, there
622 * must be only one thread that receives true when removing an
623 * item from a queue that holds it. The loop that removes the
624 * queue elements from the head also changes to accommodate this
627 public boolean dequeue (Neighbor ngb) {
629 synchronized (queue) {
630 if (ngb.state != whoami) {
633 ngb.state = NeighborCache.INTRANSIT;
647 /* Check if an address is a 6bed4 address.
649 public boolean is6bed4 (byte addr [], int addrofs) {
650 if (TunnelService.memdiff_halfaddr (addr, addrofs, address_6bed4, 0)) {
653 if ((addr [addrofs + 11] != (byte) 0xff) || (addr [addrofs + 12] != (byte) 0xfe)) {
656 //TODO// Possibly require that the port number is even
660 /* Map an address to a 6-byte key in the provided space. Assume that the
661 * address is known to be a 6bed4 address.
663 public void address2key (byte addr [], int addrofs, byte key []) {
664 key [0] = (byte) (addr [addrofs + 8] ^ 0x02);
665 key [1] = addr [addrofs + 9];
666 key [2] = addr [addrofs + 10];
667 key [3] = addr [addrofs + 13];
668 key [4] = addr [addrofs + 14];
669 key [5] = addr [addrofs + 15];
672 /* Map an InetSocketAddress to a 6-byte key in the provided space.
674 public void socketaddress2key (InetSocketAddress sa, byte key []) {
675 int port = sa.getPort ();
676 byte addr [] = sa.getAddress ().getAddress ();
677 key [0] = (byte) (port & 0xff);
678 key [1] = (byte) (port >> 8 );
685 /* Map a key to an IPv6 address, following the 6bed4 structures.
687 public void key2ipv6address (byte key [], byte addr [], int addrofs) {
688 for (int i=0; i<8; i++) {
689 addr [addrofs + i] = address_6bed4 [i];
691 addr [addrofs + 8] = (byte) (key [0] ^ 0x02);
692 addr [addrofs + 9] = key [1];
693 addr [addrofs + 10] = key [2];
694 addr [addrofs + 11] = (byte) 0xff;
695 addr [addrofs + 12] = (byte) 0xfe;
696 addr [addrofs + 13] = key [3];
697 addr [addrofs + 14] = key [4];
698 addr [addrofs + 15] = key [5];
701 /* Map a key to an InetSocketAddress.
703 public InetSocketAddress key2socketaddress (byte key []) {
704 int port = (int) (key [0] & 0xff);
705 port = port | (((int) (key [1] << 8)) & 0xff00);
706 byte v4addr [] = new byte [4];
707 v4addr [0] = key [2];
708 v4addr [1] = key [3];
709 v4addr [2] = key [4];
710 v4addr [3] = key [5];
712 Inet4Address remote = (Inet4Address) Inet4Address.getByAddress (v4addr);
713 return new InetSocketAddress (remote, port);
714 } catch (UnknownHostException uhe) {
715 throw new RuntimeException ("Internet Error", uhe);
719 public int key2hash (byte key []) {
721 retval = key [0] ^ key [3];
723 retval += key [1] ^ key [4];
725 retval += key [2] ^ key [5];