Author: toad
Date: 2007-06-08 17:26:51 +0000 (Fri, 08 Jun 2007)
New Revision: 13490
Modified:
trunk/freenet/src/freenet/io/comm/DMT.java
trunk/freenet/src/freenet/node/CHKInsertSender.java
trunk/freenet/src/freenet/node/LocationManager.java
trunk/freenet/src/freenet/node/NodeDispatcher.java
trunk/freenet/src/freenet/node/PeerManager.java
trunk/freenet/src/freenet/node/RequestSender.java
trunk/freenet/src/freenet/node/SSKInsertSender.java
Log:
Include sub-message for best 3 locations seen so far but not visited.
Modified: trunk/freenet/src/freenet/io/comm/DMT.java
===================================================================
--- trunk/freenet/src/freenet/io/comm/DMT.java 2007-06-08 16:21:12 UTC (rev
13489)
+++ trunk/freenet/src/freenet/io/comm/DMT.java 2007-06-08 17:26:51 UTC (rev
13490)
@@ -96,6 +96,7 @@
public static final String MY_UID = "myUID";
public static final String PEER_LOCATIONS = "peerLocations";
public static final String PEER_UIDS = "peerUIDs";
+ public static final String BEST_LOCATIONS_NOT_VISITED =
"bestLocationsNotVisited";
//Diagnostic
public static final MessageType ping = new MessageType("ping") {{
@@ -956,6 +957,36 @@
return msg;
}
+ public static final Message createFNPSwapLocations(long[] uids) {
+ Message msg = new Message(FNPSwapNodeUIDs);
+ msg.set(NODE_UIDS, new ShortBuffer(Fields.longsToBytes(uids)));
+ return msg;
+ }
+
+ // More permanent secondary messages (should perhaps be replaced by new
main messages when stable)
+
+ public static final MessageType FNPBestRoutesNotTaken = new
MessageType("FNPBestRoutesNotTaken") {{
+ // Maybe this should be some sort of typed array?
+ // It's just a bunch of double's anyway.
+ addField(BEST_LOCATIONS_NOT_VISITED, ShortBuffer.class);
+ }};
+
+ public static final Message createFNPBestRoutesNotTaken(byte[] locs) {
+ Message msg = new Message(FNPBestRoutesNotTaken);
+ msg.set(BEST_LOCATIONS_NOT_VISITED, new ShortBuffer(locs));
+ return msg;
+ }
+
+ public static final Message createFNPBestRoutesNotTaken(double[] locs) {
+ return createFNPBestRoutesNotTaken(Fields.doublesToBytes(locs));
+ }
+
+ public static Message createFNPBestRoutesNotTaken(Double[] doubles) {
+ double[] locs = new double[doubles.length];
+ for(int i=0;i<locs.length;i++) locs[i] =
doubles[i].doubleValue();
+ return createFNPBestRoutesNotTaken(locs);
+ }
+
public static void init() { }
}
Modified: trunk/freenet/src/freenet/node/CHKInsertSender.java
===================================================================
--- trunk/freenet/src/freenet/node/CHKInsertSender.java 2007-06-08 16:21:12 UTC
(rev 13489)
+++ trunk/freenet/src/freenet/node/CHKInsertSender.java 2007-06-08 17:26:51 UTC
(rev 13490)
@@ -247,7 +247,7 @@
PeerNode next;
// Can backtrack, so only route to nodes closer than we are to
target.
double nextValue;
- next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1);
+ next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null);
if(next != null)
nextValue = next.getLocation().getValue();
else
Modified: trunk/freenet/src/freenet/node/LocationManager.java
===================================================================
--- trunk/freenet/src/freenet/node/LocationManager.java 2007-06-08 16:21:12 UTC
(rev 13489)
+++ trunk/freenet/src/freenet/node/LocationManager.java 2007-06-08 17:26:51 UTC
(rev 13490)
@@ -326,7 +326,7 @@
// Send our SwapComplete
Message confirm = DMT.createFNPSwapComplete(uid, myValue);
-
confirm.addSubMessage(DMT.createFNPSwapLocations(Fields.longsToBytes(extractUIDs(friendLocsAndUIDs))));
+
confirm.addSubMessage(DMT.createFNPSwapLocations(extractUIDs(friendLocsAndUIDs)));
node.usm.send(pn, confirm, null);
@@ -438,7 +438,7 @@
byte[] hisHash =
((ShortBuffer)reply.getObject(DMT.HASH)).getData();
Message confirm = DMT.createFNPSwapCommit(uid, myValue);
-
confirm.addSubMessage(DMT.createFNPSwapLocations(Fields.longsToBytes(extractUIDs(friendLocsAndUIDs))));
+
confirm.addSubMessage(DMT.createFNPSwapLocations(extractUIDs(friendLocsAndUIDs)));
filter1.clearOr();
MessageFilter filter3 =
MessageFilter.create().setField(DMT.UID,
uid).setType(DMT.FNPSwapComplete).setTimeout(TIMEOUT).setSource(pn);
Modified: trunk/freenet/src/freenet/node/NodeDispatcher.java
===================================================================
--- trunk/freenet/src/freenet/node/NodeDispatcher.java 2007-06-08 16:21:12 UTC
(rev 13489)
+++ trunk/freenet/src/freenet/node/NodeDispatcher.java 2007-06-08 17:26:51 UTC
(rev 13490)
@@ -3,8 +3,11 @@
* http://www.gnu.org/ for further details of the GPL. */
package freenet.node;
+import java.util.Arrays;
+import java.util.Comparator;
import java.util.HashSet;
import java.util.Hashtable;
+import java.util.Vector;
import freenet.io.comm.DMT;
import freenet.io.comm.Dispatcher;
@@ -17,6 +20,7 @@
import freenet.support.LRUQueue;
import freenet.support.Logger;
import freenet.support.ShortBuffer;
+import freenet.support.StringArray;
/**
* @author amphibian
@@ -347,7 +351,7 @@
// Forward
m = preForward(m, htl);
while(true) {
- PeerNode next = node.peers.closerPeer(pn, ctx.routedTo,
ctx.notIgnored, target, true, node.isAdvancedModeEnabled(), -1);
+ PeerNode next = node.peers.closerPeer(pn, ctx.routedTo,
ctx.notIgnored, target, true, node.isAdvancedModeEnabled(), -1, null);
if(logMINOR) Logger.minor(this, "Next: "+next+"
message: "+m);
if(next != null) {
// next is connected, or at least has been =>
next.getPeer() CANNOT be null.
@@ -423,6 +427,7 @@
short htl;
double nearest;
double best;
+ Vector notVisitedList; // List of best locations not yet
visited by this request
public ProbeContext(long id, double target, double best, double
nearest, short htl, short counter, PeerNode src, ProbeCallback cb) {
visitedPeers = new HashSet();
@@ -475,9 +480,19 @@
Logger.minor(this, "Probe request popped "+o);
}
}
- return innerHandleProbeRequest(src, id, lid, target, best,
nearest, htl, counter, true, true, null);
+ Message notVisited = m.getSubMessage(DMT.FNPBestRoutesNotTaken);
+ double[] locsNotVisited = null;
+ Vector notVisitedList = new Vector();
+ if(notVisited != null) {
+ locsNotVisited =
Fields.bytesToDoubles(((ShortBuffer)m.getObject(DMT.BEST_LOCATIONS_NOT_VISITED)).getData());
+ for(int i=0;i<locsNotVisited.length;i++)
+ notVisitedList.add(new
Double(locsNotVisited[i]));
+ }
+ return innerHandleProbeRequest(src, id, lid, target, best,
nearest, htl, counter, true, true, false, null, notVisitedList);
}
+ final int MAX_LOCS_NOT_VISITED = 3;
+
/**
*
* @param src
@@ -491,10 +506,12 @@
* @param checkRecent
* @param canReject
* @param cb
+ * @param locsNotVisited
* @return
*/
- private boolean innerHandleProbeRequest(PeerNode src, long id, Long
lid, double target, double best,
- double nearest, short htl, short counter, boolean
checkRecent, boolean canReject, ProbeCallback cb) {
+ private boolean innerHandleProbeRequest(PeerNode src, long id, Long
lid, final double target, double best,
+ double nearest, short htl, short counter, boolean
checkRecent, boolean canReject,
+ boolean fromRejection, ProbeCallback cb, Vector
locsNotVisited) {
short max = node.maxHTL();
if(htl > max) htl = max;
if(htl <= 1) htl = 1;
@@ -522,6 +539,11 @@
recentProbeContexts.popValue();
}
}
+ if(locsNotVisited != null) {
+ if(logMINOR)
+ Logger.minor(this, "Locs not visited:
"+locsNotVisited);
+ }
+
// Add source
if(src != null) ctx.visitedPeers.add(src);
if(rejected) {
@@ -546,6 +568,13 @@
PeerNode[] peers = node.peers.connectedPeers;
double myLoc = node.getLocation();
+ for(int i=0;i<locsNotVisited.size();i++) {
+ double loc = ((Double)
locsNotVisited.get(i)).doubleValue();
+ if(Math.abs(loc - myLoc) < Double.MIN_VALUE * 2) {
+ locsNotVisited.remove(i);
+ break;
+ }
+ }
// Update best
if(myLoc > target && myLoc < best)
@@ -589,6 +618,8 @@
if(src != null) {
// Complete
Message complete = DMT.createFNPProbeReply(id,
target, nearest, best, counter++);
+ Message sub =
DMT.createFNPBestRoutesNotTaken((Double[])locsNotVisited.toArray(new
Double[locsNotVisited.size()]));
+ complete.addSubMessage(sub);
try {
src.sendAsync(complete, null, 0, null);
} catch (NotConnectedException e) {
@@ -606,13 +637,36 @@
while(true) {
- PeerNode pn = node.peers.closerPeer(src, visited, null,
target, true, false, 965);
+ Vector newBestLocs = new Vector();
+ newBestLocs.addAll(locsNotVisited);
+ PeerNode pn = node.peers.closerPeer(src, visited, null,
target, true, false, 965, newBestLocs);
+
+ Double[] locs = (Double[]) newBestLocs.toArray(new
Double[newBestLocs.size()]);
+ Arrays.sort(locs, new Comparator() {
+ public int compare(Object arg0, Object arg1) {
+ double d0 = ((Double)
arg0).doubleValue();
+ double d1 = ((Double)
arg1).doubleValue();
+ double dist0 = PeerManager.distance(d0,
target);
+ double dist1 = PeerManager.distance(d1,
target);
+ if(dist0 < dist1) return -1; // best at
the beginning
+ if(dist0 > dist1) return 1;
+ return 0; // should not happen
+ }
+ });
+ locsNotVisited.clear();
+ for(int i=0;i<Math.min(MAX_LOCS_NOT_VISITED,
locs.length);i++)
+ locsNotVisited.add(locs[i]);
+
+ Message sub =
DMT.createFNPBestRoutesNotTaken((Double[])locsNotVisited.toArray(new
Double[locsNotVisited.size()]));
+
+ ctx.notVisitedList = locsNotVisited;
if(pn == null) {
// Can't complete, because some HTL left
// Reject: RNF
if(canReject) {
Message reject =
DMT.createFNPProbeRejected(id, target, nearest, best, counter, htl,
DMT.PROBE_REJECTED_RNF);
+ reject.addSubMessage(sub);
try {
src.sendAsync(reject, null, 0,
null);
} catch (NotConnectedException e) {
@@ -629,6 +683,7 @@
if(src != null) {
Message trace =
DMT.createFNPProbeTrace(id, target,
nearest, best, htl, counter, myLoc, node.swapIdentifier,
LocationManager.extractLocs(peers, true), LocationManager.extractUIDs(peers));
+ trace.addSubMessage(sub);
try {
src.sendAsync(trace, null, 0, null);
} catch (NotConnectedException e1) {
@@ -638,6 +693,7 @@
Message forwarded =
DMT.createFNPProbeRequest(id, target, nearest,
best, htl, counter++);
+ forwarded.addSubMessage(sub);
try {
pn.sendAsync(forwarded, null, 0, null);
return true;
@@ -692,6 +748,8 @@
if(ctx.src != null) {
Message complete = DMT.createFNPProbeReply(id, target,
nearest, best, counter++);
+ Message sub =
m.getSubMessage(DMT.FNPBestRoutesNotTaken);
+ if(sub != null) complete.addSubMessage(sub);
try {
ctx.src.sendAsync(complete, null, 0, null);
} catch (NotConnectedException e) {
@@ -711,8 +769,17 @@
double best = m.getDouble(DMT.BEST_LOCATION);
double nearest = m.getDouble(DMT.NEAREST_LOCATION);
short counter = m.getShort(DMT.COUNTER);
+ Message notVisited = m.getSubMessage(DMT.FNPBestRoutesNotTaken);
+ double[] locsNotVisited = null;
+ if(notVisited != null) {
+ locsNotVisited =
Fields.bytesToDoubles(((ShortBuffer)m.getObject(DMT.BEST_LOCATIONS_NOT_VISITED)).getData());
+ }
if(logMINOR)
Logger.minor(this, "Probe trace: "+id+ ' ' +target+ ' '
+best+ ' ' +nearest+' '+counter);
+ if(locsNotVisited != null) {
+ if(logMINOR)
+ Logger.minor(this, "Locs not visited:
"+StringArray.toString(locsNotVisited));
+ }
// Just propagate back to source
ProbeContext ctx;
synchronized(recentProbeContexts) {
@@ -763,7 +830,15 @@
recentProbeContexts.popValue();
}
- return innerHandleProbeRequest(src, id, lid, target, best,
nearest, htl, counter, false, false, null);
+ Message notVisited = m.getSubMessage(DMT.FNPBestRoutesNotTaken);
+ double[] locsNotVisited = null;
+ Vector notVisitedList = new Vector();
+ if(notVisited != null) {
+ locsNotVisited =
Fields.bytesToDoubles(((ShortBuffer)m.getObject(DMT.BEST_LOCATIONS_NOT_VISITED)).getData());
+ for(int i=0;i<locsNotVisited.length;i++)
+ notVisitedList.add(new
Double(locsNotVisited[i]));
+ }
+ return innerHandleProbeRequest(src, id, lid, target, best,
nearest, htl, counter, false, false, true, null, notVisitedList);
}
public void startProbe(double d, ProbeCallback cb) {
@@ -773,7 +848,7 @@
recentProbeRequestIDs.push(ll);
}
double nodeLoc = node.getLocation();
- innerHandleProbeRequest(null, l, ll, d, (nodeLoc > d) ? nodeLoc
: 1.0, nodeLoc, node.maxHTL(), (short)0, false, false, cb);
+ innerHandleProbeRequest(null, l, ll, d, (nodeLoc > d) ? nodeLoc
: 1.0, nodeLoc, node.maxHTL(), (short)0, false, false, false, cb, new Vector());
}
void start(NodeStats stats) {
Modified: trunk/freenet/src/freenet/node/PeerManager.java
===================================================================
--- trunk/freenet/src/freenet/node/PeerManager.java 2007-06-08 16:21:12 UTC
(rev 13489)
+++ trunk/freenet/src/freenet/node/PeerManager.java 2007-06-08 17:26:51 UTC
(rev 13490)
@@ -537,11 +537,11 @@
* This scans the same array 4 times. It would be better to scan once and
execute 4 callbacks...
* For this reason the metrics are only updated if advanced mode is enabled
*/
- public PeerNode closerPeer(PeerNode pn, HashSet routedTo, HashSet
notIgnored, double loc, boolean ignoreSelf, boolean calculateMisrouting, int
minVersion) {
- PeerNode best = closerPeerBackoff(pn, routedTo, notIgnored, loc,
ignoreSelf, minVersion);
+ public PeerNode closerPeer(PeerNode pn, HashSet routedTo, HashSet
notIgnored, double loc, boolean ignoreSelf, boolean calculateMisrouting, int
minVersion, Vector addUnpickedLocsTo) {
+ PeerNode best = closerPeerBackoff(pn, routedTo, notIgnored, loc,
ignoreSelf, minVersion, addUnpickedLocsTo);
if (calculateMisrouting) {
- PeerNode nbo = _closerPeer(pn, routedTo, notIgnored, loc,
ignoreSelf, true, minVersion);
+ PeerNode nbo = _closerPeer(pn, routedTo, notIgnored, loc,
ignoreSelf, true, minVersion, null);
if(nbo != null) {
node.nodeStats.routingMissDistance.report(distance(best,
nbo.getLocation().getValue()));
int numberOfConnected =
getPeerNodeStatusSize(PEER_NODE_STATUS_CONNECTED);
@@ -554,10 +554,10 @@
return best;
}
- private PeerNode closerPeerBackoff(PeerNode pn, HashSet routedTo, HashSet
notIgnored, double loc, boolean ignoreSelf, int minVersion) {
- PeerNode best = _closerPeer(pn, routedTo, notIgnored, loc, ignoreSelf,
false, minVersion);
+ private PeerNode closerPeerBackoff(PeerNode pn, HashSet routedTo, HashSet
notIgnored, double loc, boolean ignoreSelf, int minVersion, Vector
addUnpickedLocsTo) {
+ PeerNode best = _closerPeer(pn, routedTo, notIgnored, loc, ignoreSelf,
false, minVersion, addUnpickedLocsTo);
if(best == null) {
- best = _closerPeer(pn, routedTo, notIgnored, loc, ignoreSelf,
true, minVersion);
+ best = _closerPeer(pn, routedTo, notIgnored, loc, ignoreSelf,
true, minVersion, addUnpickedLocsTo);
}
return best;
}
@@ -565,8 +565,10 @@
/**
* Find the peer, if any, which is closer to the target location
* than we are, and is not included in the provided set.
+ * @param addUnpickedLocsTo Add all locations we didn't choose which we
could have routed to to
+ * this array. Remove the location of the peer we pick from it.
*/
- private PeerNode _closerPeer(PeerNode pn, HashSet routedTo, HashSet
notIgnored, double loc, boolean ignoreSelf, boolean ignoreBackedOff, int
minVersion) {
+ private PeerNode _closerPeer(PeerNode pn, HashSet routedTo, HashSet
notIgnored, double loc, boolean ignoreSelf, boolean ignoreBackedOff, int
minVersion, Vector addUnpickedLocsTo) {
PeerNode[] peers;
synchronized (this) {
peers = connectedPeers;
@@ -577,6 +579,7 @@
if(!ignoreSelf)
maxDiff = distance(node.lm.getLocation().getValue(), loc);
PeerNode best = null;
+ double bestLoc = -2;
int count = 0;
for(int i=0;i<peers.length;i++) {
PeerNode p = peers[i];
@@ -608,11 +611,20 @@
continue;
}
if(diff < bestDiff) {
+ if(bestLoc > 0 && addUnpickedLocsTo != null) {
+ Double d = new Double(bestLoc);
+ // Here we can directly compare double's because they
aren't processed in any way, and are finite and (probably) nonzero.
+ if(!addUnpickedLocsTo.contains(d))
+ addUnpickedLocsTo.add(d);
+ }
+ bestLoc = loc;
best = p;
bestDiff = diff;
if(logMINOR) Logger.minor(this, "New best: "+diff+"
("+p.getLocation().getValue()+" for "+p.getPeer());
}
}
+ if(addUnpickedLocsTo != null)
+ addUnpickedLocsTo.remove(new Double(bestLoc));
return best;
}
Modified: trunk/freenet/src/freenet/node/RequestSender.java
===================================================================
--- trunk/freenet/src/freenet/node/RequestSender.java 2007-06-08 16:21:12 UTC
(rev 13489)
+++ trunk/freenet/src/freenet/node/RequestSender.java 2007-06-08 17:26:51 UTC
(rev 13490)
@@ -132,7 +132,7 @@
// Route it
PeerNode next;
double nextValue;
- next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1);
+ next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null);
if(next != null)
nextValue = next.getLocation().getValue();
else
Modified: trunk/freenet/src/freenet/node/SSKInsertSender.java
===================================================================
--- trunk/freenet/src/freenet/node/SSKInsertSender.java 2007-06-08 16:21:12 UTC
(rev 13489)
+++ trunk/freenet/src/freenet/node/SSKInsertSender.java 2007-06-08 17:26:51 UTC
(rev 13490)
@@ -137,7 +137,7 @@
// Can backtrack, so only route to nodes closer than we are to
target.
double nextValue;
synchronized(node.peers) {
- next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1);
+ next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null);
if(next != null)
nextValue = next.getLocation().getValue();
else
