Here is a replacement for Freenet/Key.java which I think fixes the 100% CPU bug, which we believe to be grounded in a math bug in the key comparison routine that occasionally makes searching for a reference in the datastore get stuck in an infinite loop.
Update to the latest 0.3 CVS and replace Freeney/Key.java with this. Search your logs for "Key.compare() failed:". You can have your log level on ERROR or anything else for this. If you get any of these messages, please post your log AND the console output of Fred to this list or to me. So please remember to redirect the console output to a file :) This Key.java will produce verbose debugging output and will slow your node down *A LOT*, since I am using BigInteger math in the comparison routine to doublecheck the results of our fast compare routine. -- /* tavin cole * composer of e-mail messages */ -------------- next part -------------- package Freenet; import java.math.BigInteger; import Freenet.support.Loader; import Freenet.support.Logger; import Freenet.support.Fields; import Freenet.support.io.VerifyingInputStream; import Freenet.support.io.DataNotValidIOException; import java.lang.reflect.Constructor; import java.lang.reflect.InvocationTargetException; import java.util.Hashtable; import java.io.Serializable; import java.io.InputStream; import Freenet.keys.KHK; /** * A base implementation of all keys. Used as superclass for other types, * and class for unknown keytypes. * * @author <A HREF="mailto:I.Clarke at strs.co.uk">Ian Clarke</A> * @author oskar (total rewrite) **/ public class Key implements Serializable { private static Hashtable keytypes = new Hashtable(); public static void addKeyType(int typen, Class c) throws ClassCastException { if (!Freenet.Key.class.isAssignableFrom(c)) { throw new ClassCastException(); } try { Constructor con = c.getConstructor(new Class[] {byte[].class}); } catch (NoSuchMethodException e) { throw new ClassCastException(); } Integer type = new Integer(typen); keytypes.put(type,c); } /** * Returns an instance of a key given as a string in the format * <type>/<value> by looking for a class with the type * name in Freenet.keys **/ public static Key readKey(String s) throws KeyException { if ((s.length() & 0x1) == 1) throw new KeyException("Key string did not contain bytes"); byte[] val = new byte[s.length() >> 1]; Fields.hexToBytes(s, val, 0); Integer type = new Integer(val[val.length-2] << 8 | val[val.length - 1]); Class c = (Class) keytypes.get(type); if (c != null) { try { Constructor con = c.getConstructor(new Class[] {byte[].class}); return (Key) con.newInstance(new Object[] {val}); } catch (NoSuchMethodException e) { throw new Error("Key method borked on constructor checks."); } catch (InvocationTargetException e) { Throwable te = e.getTargetException(); if (te instanceof KeyException) { throw (KeyException) te; } // te.printStackTrace(Logger.Lout); throw new RuntimeException(); } catch (Exception e) { // e.printStackTrace(Logger.Lout); throw new RuntimeException(); } } else { Core.logger.log(null,"Got unknown key type : " + Integer.toHexString(type.intValue()),Logger.MINOR); return new Key(val); } } protected byte[] val; /** * General constructor **/ protected Key(byte[] val) { this.val = val; } /** * Wraps a verifying stream around the data stream for a key, so the * data is verified to belong to the key * * The implementation of verifyStream in Key always returns * The implementation of VerifyingInputStream in Key always returns * a stream that does not verify anything. * @param data The data stream. * @param storables Node visable metadata fields. * @param dataLength The length of data that should be verified. **/ public VerifyingInputStream verifyStream(InputStream data, FieldSet storables, long dataLength) throws DataNotValidIOException { Core.logger.log(this,"Warning: Default Key.verify() called. All " + "known keytypes should override this.", Logger.DEBUGGING); return new VerifyingInputStream(data,dataLength); } /** * Returns whether to cache the data for this key on this node. * * The implementation of isCachable in Key always returns false. **/ public boolean isCachable() { return false; } /** Implements the Comparable interface * Returns -1 if this is less than o, 1 if this is greater than o, * and 0 if they are equal. * * @param o the key Object to compare to * @return integer <0, >0, or ==0 * @exception IllegalArgumentException thrown if !(o instanceof Key) */ public final int compareTo(Object o) { if (!(o instanceof Key)) throw new IllegalArgumentException(); int len = Math.max(val.length, ((Key) o).val.length); for (int i=0; i<len; ++i) { if (at(val, i) < at(((Key) o).val, i)) return -1; if (at(val, i) > at(((Key) o).val, i)) return 1; } return 0; } public final int compareTo(Key k) { System.out.println("compareTo(): this=="+this.toString()); System.out.println("compareTo(): k=="+k.toString()); int len = Math.max(val.length, k.val.length); for (int i=0; i<len; ++i) { if (at(val, i) < at(k.val, i)) { System.out.println("compareTo(): this <=> k is -1"); return -1;} if (at(val, i) > at(k.val, i)) { System.out.println("compareTo(): this <=> k is 1") ; return 1;} } System.out.println("compareTo(): this <=> k is 0"); return 0; } public boolean isGreater(Key k) { System.out.println("isGreater(): this == "+this.toString()); System.out.println("isGreater(): k == "+k.toString()); boolean result = (this.compareTo(k) > 0); System.out.println("isGreater(): result == "+result); return result; // return this.compareTo(k) > 0; } public final boolean equals(Object o) { return this.compareTo(o) == 0; } /** Given that this Key is between Key A and Key B, * determines whether A or B is closer. * @return true if A is closer than B */ public final boolean isCloserTo_Ordered(Key A, Key B) { System.out.println("isCloserTo_Ordered():"); System.out.println("A == "+A.toString()); System.out.println("this == "+this.toString()); System.out.println("B == "+B.toString()); int len = Math.max(val.length, Math.max(A.val.length, B.val.length)); int diff = 0; for (int i=0; i<len; ++i) { // incrementally compute the difference in the absolute distance // between this and A and the absolute distance between this and B, // which is given by (this - A) - (B - this) System.out.println("Step "+i+":"); System.out.println("this-A == "+(at(val,i)-at(A.val,i))); System.out.println("B-this == "+(at(B.val,i)-at(val,i))); diff += (at(val,i) - at(A.val,i)) - (at(B.val,i) - at(val,i)); System.out.println("Step "+i+": diff == "+diff); if (diff < -1) return true; if (diff > 1) return false; diff *= 0x100; } return diff < 0; } /** Determines whether A or B is closer. The 3 keys can be in any order. * @return true if A is closer than B */ public final boolean isCloserTo(Key A, Key B) { if (A == null) return false; if (B == null) return true; System.out.println("isCloserTo():"); System.out.println("A == "+A.toString()); System.out.println("this == "+this.toString()); System.out.println("B == "+B.toString()); int ABcmp = A.compareTo(B); if (ABcmp < 0) { System.out.println("isCloserTo(): A < B"); if (this.isGreater(B)) return false; if (this.isGreater(A)) return this.isCloserTo_Ordered(A, B); else return true; } else if (ABcmp > 0) { System.out.println("isCloserTo(): A > B"); if (this.isGreater(A)) return true; if (this.isGreater(B)) return !this.isCloserTo_Ordered(B, A); else return false; } else { return false; } } /** Reduced to a wrapper around isCloserTo() */ public final boolean compare(Key a, Key b) { System.out.println("compare():"); System.out.println("A byte-length == "+a.val.length); System.out.println("this byte-length == "+this.val.length); System.out.println("B byte-length == "+b.val.length); System.out.println("A == "+a.toString()); System.out.println("this == "+this.toString()); System.out.println("B == "+b.toString()); boolean result = isCloserTo(a, b); System.out.println("this.isCloserTo(A,B) == "+result); int len = Math.max(val.length, Math.max(a.val.length, b.val.length)); byte[] temp = new byte[len]; for (int i=0; i<len; ++i) temp[i] = (i<val.length ? val[i] : 0); BigInteger self = new BigInteger(1, temp); for (int i=0; i<len; ++i) temp[i] = (i<a.val.length ? a.val[i] : 0); BigInteger A = new BigInteger(1, temp); for (int i=0; i<len; ++i) temp[i] = (i<b.val.length ? b.val[i] : 0); BigInteger B = new BigInteger(1, temp); BigInteger delA = self.subtract(A).abs(); BigInteger delB = self.subtract(B).abs(); if ((delA.compareTo(delB) < 0) != result) { String str_self = Fields.bytesToHex(self.toByteArray(), 0, self.toByteArray().length); String str_A = Fields.bytesToHex(A.toByteArray(), 0, A.toByteArray().length); String str_B = Fields.bytesToHex(B.toByteArray(), 0, B.toByteArray().length); String msg = "Key.compare() failed: self=="+str_self+" A=="+str_A+" B=="+str_B+" self.compare(A,B)=="+result; System.out.println(msg); Core.logger.log(null, msg, Logger.ERROR ); return delA.compareTo(delB) < 0; } return result; } private final int at(byte[] b, int i) { return (i < b.length ? b[i] : 0) & 0xff; } /** * Returns a correctly calculated length-limit field given * the size you want to allow */ public static final byte lengthLimit(long size) { byte b=0; for (; (1 << b) <= size ; b++); // size bound return b; } /* * For the hashcode, I'll just return the last four numbers * no, I guess I won't, Scott complained. */ public int hashCode() { int h = 0; for (int i = val.length-1; i >= 0 ; i--) { h ^= val[i] << ((i & 3) << 3); } return h; } /** * Returns the Key as a hex string. **/ public String toString() { return Fields.bytesToHex(val,0,val.length); } public byte[] getVal() { return val; } /** Test code */ public static void main(String[] args) { Key a = new Key(new byte[] {00, 00, 00}); Key self = new Key(new byte[] {00, -1, 00}); Key b = new Key(new byte[] {01, -1, -1}); System.out.println(self.compare(a,b)); } }
