zzz.i2p

Development discussions
15,087 Posts
 
13 hours ago Pack200 gone as of Java 14 »
zzz
Administrator
Zzz

And here's the first complaint:

http://trac.i2p2.i2p/ticket/2745

16 hours ago Proposal: ECIES-X25519-Ratchet-AEAD »
zzz
Administrator
Zzz

Updates for post-0.9.46 release, working through the list in #26 above:

I implemented the MTU increase (proposal 155) in 0.9.46-3, pushed May 30.

I implemented ratchet-layer responses in 0.9.46-4, pushed today.

18 hours ago Not enough fast peers in 0.9.46 »
zzz
Administrator
Zzz

I'll fix the summary lines for NTCP, but in the future please file a ticket when you find a bug.

w.r.t the fast peers issue, we discussed, reviewed, and tested the change extensively in IRC 3 months ago. low-traffic routers don't need a lot of fast peers. I don't know why you see a shift from SSU to NTCP or why you think it's related. Any ideas?

21 hours ago Not enough fast peers in 0.9.46 »
jogger
I2P Legend

Same issue here:

After longer uptime 6 fast peers on small routers, 12 fast peers for high bandwidth router. High capacity figures never twice as high.

Also there is a major traffic shift from SSU to NTCP. Symptoms:

- Summary figures on /peers are always much higher now for NTCP. (For NTCP you have to look at the idle column, bug introduced with NTCP2)

- Before without con limits majority of cons was SSU. Now NTCP.

- Before one could run SSU-only with only a little slowdown. Now even using i2np.udp.preferred=true chokes my small b/w routers down by 80-90%

- Despite much higher NTCP traffic, retransmissions on the kernel level are down near 50%. This means traffic concentrates on a few highly reliable connections.

21 hours ago Not enough fast peers in 0.9.46 »
echelon
I2P Legend

Hi

Peers are new calculated every minute. On every new connection to a I2P route you get a list of new I2P nodes.
See the i2p paper about peer profiling on geti2p.net

echelon

1 day ago Not enough fast peers in 0.9.46 »
моченый
Lurker

But how often should fast peers change? If this group is relatively stable, attacker could be fetching leaseset of some eepsite for a day or two and he would gather all fast peers of this eepsite.
If attacker wants to check if two eepsites are hosted on the same router, he just gathers fast peers for both of them and then checks the correlation.

In my opinion, it's better to make distinct fast peer groups for each leaseset on a router. This would mitigate correlation attacks.

2 days ago Not enough fast peers in 0.9.46 »
zzz
Administrator
Zzz

Yes, it's true. We fixed a bug in the calculation of the threshold for fast peers.

40 or even 20 is fine. It's good to keep the fast peer group relatively small for anonymity purposes. Also, if the group gets too small, it will use the next group (high capacity).

2 days ago Researching I2P message loss »
zzz
Administrator
Zzz

Also, where is the O(n**2) behavior in reorganize(), as stated in OP item 1? Sounds like something to fix.

2 days ago Not enough fast peers in 0.9.46 »
моченый
Lurker

Before update I had 75 fast peers. Now I have less then 40 fast peers. Even worse: after router restart it found about 40 fast peers. After I started browsing, this number dropped to 20 and it doesn't change.
As far as I understand, peer speed is measured by speed that this peer had in a single tunnel. Do transfer tunnels count too? I have lots of transfer tunnels reaching speeds of 30-40 KBps, but it doesn't affect peer speed in it's profile.
So how can number of fast peers grow if only speed in client tunnels is measured, only 'fast peers' are allowed to participate in client tunnels and other peers are not given a chance to become fast peer?

Mon, 01 Jun 2020, 01:59pm Researching I2P message loss »
zzz
Administrator
Zzz

here's an untested patch to put LockFreeRingCache into TryCache:

#
# old_revision [54a62b9a163762e9d5922d1c509131b863218373]
#
# patch "core/java/src/net/i2p/util/ByteCache.java"
# from [70a276f53b5360c86c71a46e01daaa53b83e2b10]
# to [b7f2479bc8e01e22320aeb34fb6cc93af003459f]
#
# patch "core/java/src/net/i2p/util/TryCache.java"
# from [b846e48eaa9e3ef3378a0157d9e11257b573ad54]
# to [08c7c868283203b3950337dbc835ac99a276dfb8]
#
============================================================
--- core/java/src/net/i2p/util/ByteCache.java 70a276f53b5360c86c71a46e01daaa53b83e2b10
+++ core/java/src/net/i2p/util/ByteCache.java b7f2479bc8e01e22320aeb34fb6cc93af003459f
@@ -168,21 +168,16 @@ public final class ByteCache extends Try

private class Cleanup implements SimpleTimer.TimedEvent {
public void timeReached() {
- int origsz;
- lock.lock();
- try {
- origsz = items.size();
+ int origsz = size();
if (origsz > 1 && System.currentTimeMillis() - _lastUnderflow > EXPIRE_PERIOD) {
// we haven't exceeded the cache size in a few minutes, so lets
// shrink the cache
int toRemove = origsz / 2;
for (int i = 0; i < toRemove; i++) {
- items.remove(items.size() - 1);
+ acquire();
}
}
- } finally {
- lock.unlock();
- }
+
I2PAppContext.getGlobalContext().statManager().addRateData("byteCache.memory." + _entrySize, _entrySize * origsz);
}

============================================================
--- core/java/src/net/i2p/util/TryCache.java b846e48eaa9e3ef3378a0157d9e11257b573ad54
+++ core/java/src/net/i2p/util/TryCache.java 08c7c868283203b3950337dbc835ac99a276dfb8
@@ -1,14 +1,12 @@ package net.i2p.util;
package net.i2p.util;

-import java.util.ArrayList;
-import java.util.List;
-import java.util.concurrent.locks.Lock;
-import java.util.concurrent.locks.ReentrantLock;
+import java.util.concurrent.atomic.AtomicLong;
+import java.util.concurrent.atomic.AtomicReferenceArray;

/**
* An object cache which is safe to use by multiple threads without blocking.
*
- * @author zab
+ * @author zab, jogger
*
* @param <T>
* @since 0.9.36
@@ -27,10 +25,13 @@ public class TryCache<T> {
}

private final ObjectFactory<T> factory;
- protected final int capacity;
- protected final List<T> items;
- protected final Lock lock = new ReentrantLock();
+ private final AtomicReferenceArray<T> items;
protected long _lastUnderflow;
+ /* head pointing at field before first valid */
+ private final AtomicLong head = new AtomicLong();
+ /* tail pointing at last field valid */
+ private final AtomicLong tail = new AtomicLong();
+ private final int mask;

/**
* @param factory to be used for creating new instances
@@ -38,30 +39,49 @@ public class TryCache<T> {
*/
public TryCache(ObjectFactory<T> factory, int capacity) {
this.factory = factory;
- this.capacity = capacity;
- this.items = new ArrayList<>(capacity);
+ if (capacity <= 0)
+ throw new IllegalArgumentException();
+ if (capacity <= 99)
+ capacity = 99;
+ int sz = ceilingNextPowerOfTwo(capacity);
+ mask = sz - 1;
+ items = new AtomicReferenceArray<T>(sz);
}
+
+ private static int ceilingNextPowerOfTwo(int x) {
+ // From Hacker's Delight, Chapter 3, Harry S. Warren Jr.
+ return 1 << (Integer.SIZE - Integer.numberOfLeadingZeros(x - 1));
+ }
+
+ /**
+ * @since 0.9.47
+ */
+ public int size() {
+ return (int) (tail.get() - head.get());
+ }

/**
* @return a cached or newly created item from this cache
*/
public T acquire() {
- T rv = null;
- if (lock.tryLock()) {
- try {
- if (!items.isEmpty()) {
- rv = items.remove(items.size() - 1);
- } else {
- _lastUnderflow = System.currentTimeMillis();
- }
- } finally {
- lock.unlock();
+ long h, old;
+ T rv;
+ int index;
+ do {
+ old = head.get();
+ if (old >= tail.get()) { // empty
+ _lastUnderflow = System.currentTimeMillis();
+ return factory.newInstance();
}
- }
-
- if (rv == null) {
- rv = factory.newInstance();
- }
+ h = old + 1;
+ index = (int)h & mask;
+ if ((rv = items.get(index)) == null)
+ if (head.get() == old)
+ return factory.newInstance(); // offer did not write yet, better than spinlocking
+ else
+ continue; // there was a concurrent poll()
+ } while (!head.compareAndSet(old, h));
+ items.set(index, null);
return rv;
}

@@ -71,40 +91,41 @@ public class TryCache<T> {
* another thread.
*/
public void release(T item) {
- if (lock.tryLock()) {
- try {
- if (DEBUG_DUP) {
- for (int i = 0; i < items.size(); i++) {
- // use == not equals() because ByteArray.equals()
- if (items.get(i) == item) {
- net.i2p.I2PAppContext.getGlobalContext().logManager().getLog(TryCache.class).log(Log.CRIT,
+ if (DEBUG_DUP) {
+ for (long i = tail.get(); i > head.get(); i--) {
+ // use == not equals() because ByteArray.equals()
+ if (items.get((int)i & mask) == item) {
+ net.i2p.I2PAppContext.getGlobalContext().logManager().getLog(TryCache.class).log(Log.CRIT,
"dup release of " + item.getClass(), new Exception("I did it"));
- return;
- }
- }
+ return;
}
- if (items.size() < capacity) {
- if (DEBUG_DUP)
- items.add(0, item);
- else
- items.add(item);
- }
- } finally {
- lock.unlock();
}
}
+
+ long t, old;
+ int index;
+ do {
+ old = tail.get();
+ if (old - head.get() >= items.length())
+ return;
+ t = old + 1;
+ index = (int)t & mask;
+ if (items.get(index) != null)
+ if (tail.get() == old)
+ return; // poll did not clear this one yet
+ else
+ continue; // there was a concurrent set()
+ } while (!tail.compareAndSet(old, t));
+ items.set(index, item);
}

/**
- * Clears all cached items. This is the only method
- * that blocks until it acquires the lock.
+ * Clears all cached items.
*/
public void clear() {
- lock.lock();
- try {
- items.clear();
- } finally {
- lock.unlock();
+ for (long i = tail.get(); i > head.get(); i--) {
+ items.set((int)i & mask, null);
}
+ tail.set(head.get());
}
}

Mon, 01 Jun 2020, 01:12pm Researching I2P message loss »
zzz
Administrator
Zzz

thanks for the responses

I checked in 1) and 5b)

looking more closely at 2) and 6)

Moved fromLong8() and toLong8() to DataHelper for 2)

I also have some unrelated changes to FortunaRandomSource that have been soaking for months, may push those soon

Sun, 31 May 2020, 07:06pm Researching I2P message loss »
jogger
I2P Legend

Remark for LockFreeRingBuffer: Without dup check it behaves like a queue. With dup check it is also like CHS for small quantities. When using poll() you may still get dups, that you want to check for work to do, when handing over work items between threads which is the use case for LockFreeRingBuffer.

Updated source for #5 2.) here: http://i2speed.i2p/

Sun, 31 May 2020, 04:56pm Researching I2P message loss »
jogger
I2P Legend

Happy to submit patches for trac tickets with a fixed target release.

Short remarks:

2.) 3 buffers to reduce frequency of the spinlocks hitting.
nextbytes() works, but discards current buffer if length requested > 16k. Now going directly to fortuna in that case.
Datahelper is better, if IAE for negative gets patched out there.

1.) yes

5b) That is just a one item cache. Given typical traffic patterns those have up to 50% hit rate in I2P.

Sat, 30 May 2020, 05:37pm Researching I2P message loss »
zzz
Administrator
Zzz

6) I like LockFreeRingCache. If we took it I'd probably just drop the code into TryCache.

It would take quite a bit more staring at it to convince myself that poll() could never return the same entry to two callers, because that would be an impossible-to-debug disaster. I'd like to have zlatinb take a look at it also. And I'd like to do my own testing to see if I see the "magnitude" benefit you're promising.

LockFreeRingBuffer makes me nervous due to the comments about dups and code mod required, but it isn't really clear to me what's "imperfect" about it if anything.

2) is like a simple version of 6). I like this one also. Again, would take a little more staring at it to make sure that it can't ever return the same data twice, and would want to do a speed test also.

Not sure if 3 caches is any better than one. Also I'd just use the DataHelper.fromLong() method instead of the object churn of bytebuffer.wrap().

Also, in nextBytes() you need a check for length > CACHE_SIZE and throw IAE I guess, that would infinite loop otherwise.

1) This one looks good also. I looked at the original 2011 checkin to see why I only made some of the calls nonblocking, or if I had a plan to make the rest of them nonblocking later, but I didn't say anything on the subject. I see you didn't change all of them either... that was based on which ones you noted as frequently blocking?

5a) is interesting, would have to look at every place we set a system property in our code and make sure it wouldn't be after something else checks it

5b) looks like an easy change to switch _unreadhableEntries to a concurrent map. Not sure what the point of lastUnreachablePeer is?

It would be a lot easier to review your proposals if you submitted patches. Running the diffs here yields a bunch of extraneous stuff, due to unrelated changes both on your side and on ours.

Sat, 30 May 2020, 04:05pm Proposal: Increase Streaming MTU for ECIES Destinations »
zzz
Administrator
Zzz

In 0.9.46-3, see this post for details. I believe that the recent i2pd 2.32 (0.9.46) release also includes an implementation of this proposal.