7 Replies Latest reply on Nov 1, 2017 1:23 PM by William Burns

    RemoteCache.replaceAll infinite loop

    Yog Sothoth Newbie

      In certain cases replaceAll method on RemoteCache descends into infinite loops. Here's a JUnit test that proves it.

       

      package com.test;
      
      import java.util.HashMap;
      import java.util.HashSet;
      import java.util.Map;
      import java.util.Properties;
      import java.util.Set;
      
      import org.infinispan.client.hotrod.RemoteCacheManager;
      import org.infinispan.client.hotrod.configuration.ConfigurationBuilder;
      import org.infinispan.client.hotrod.exceptions.HotRodClientException;
      import org.infinispan.client.hotrod.impl.ConfigurationProperties;
      import org.junit.Before;
      import org.junit.Test;
      import org.junit.runner.RunWith;
      import org.junit.runners.BlockJUnit4ClassRunner;
      
      @RunWith(BlockJUnit4ClassRunner.class)
      public class InfinispanTest {
         RemoteCacheManager cacheManager;
      
         @Before
         public void before() {
            Properties hotrodProps = new Properties();
            hotrodProps.setProperty(ConfigurationProperties.SERVER_LIST, "localhost:11222");
            cacheManager = new RemoteCacheManager(new ConfigurationBuilder().withProperties(hotrodProps).build());
         }
      
         @Test
         public void testRemoveAll() {
            Map<String, Set> localMap = new HashMap<>();
            Map<String, Set> remoteMap = createStorage("test");
            remoteMap.clear();
            populate(localMap);
            populate(remoteMap);
            localMap.replaceAll((k, v) -> {
               v.remove("v3");
               System.out.println(k);
               return v;
            });
            remoteMap.replaceAll((k, v) -> {
               v.remove("v3");
               System.out.println(k);
               return v;
            });
            System.out.println(localMap);
            System.out.println(remoteMap);
         }
      
         private <T, U> Map<T, U> createStorage(String arg0) {
            try {
               cacheManager.administration().createCache(arg0, null);
            } catch (HotRodClientException hrce) {
               hrce.printStackTrace(System.err);
            }
            return cacheManager.getCache(arg0);
         }
      
         private static void populate(Map<String, Set> arg0) {
            Set s = new HashSet();
            s.add("v1");
            s.add("v2");
            s.add("v3");
            s.add("v4");
            s.add("v5");
            s.add("v6");
            arg0.put("k1", s);
            arg0.put("k2", s);
            arg0.put("k3", s);
            arg0.put("k4", s);
            arg0.put("k5", s);
            arg0.put("k6", s);
         }
      } 
      
      

      The test will print "k6" endlessly. It reproduces on Set, List and Map sub-values.

        • 1. Re: RemoteCache.replaceAll infinite loop
          Radim Vansa Master

          I don't think this is a problem on Infinispan side; the function passed to replaceAll should not modify its argument(s). See the default implementation in ConcurrentMap; this calls conditional replace(k, v, function.apply(k, v)). As you've modified the v in the function, the conditional replace assumes that the old value is already the modified one, and replace fails.

          • 2. Re: RemoteCache.replaceAll infinite loop
            Yog Sothoth Newbie

            Map.replaceAll javadoc states "Replaces each entry's value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.". It literally implies that the v-argument will change, which is furthermore supported by its default implementation example in those javadocs. Besides, it does work on a HashMap, so it should on a RemoteCache as well, as they claim to implement Map interface.

            • 3. Re: RemoteCache.replaceAll infinite loop
              William Burns Expert

              What rvansa mentioned is exactly what the issue is. The problem is that the HashMap can use identity equivalence since it is on the same JVM. Unfortunately in a Remote client like this we can only rely on object equality. The easiest way to fix this would just be to make a copy of the Set in the lambda (if changes are required) and return that instead. You can log a JIRA at https://issues.jboss.org/projects/ISPN, so that we override the default interface impl and allow for the value to be modified in place. But to be honest this isn't feasible until we allow for lambdas to be sent to the remote node, which I hope will be added sometime, but I have no idea when it will.

              • 4. Re: RemoteCache.replaceAll infinite loop
                Yog Sothoth Newbie

                >>a copy of the Set in the lambda (if changes are required) and return that instead

                Ah, i see what you mean now, but still i don't get how would it ever explain the effect of iterating endlessly on the last element only?

                 

                >>we can only rely on object equality

                Please educate yourself with List.equals(), Set.equals() and Map.equals() (the latter being technically equals to that of Set, no pun intended) javadocs. In the above test initial sets and resulting sets are not equal _by definition_ and it has nothing to do with their identity (hint: but rather their size). I understand why you mention identity, but i refuse to accept its relevance in this particular case.

                 

                >>we override the default interface impl

                I would expect Map to have been implemented properly, or otherwise stated using profanely red letters in the RemoteCache's methods javadocs where default behaviour is not supported. Again, Map.replaceAll javadocs clearly explains how it must work and therefore section 3.2 of User guide for Infinispan 9.1 is totally misleading: migrating is a huge pain in the back and people like me must test thousands lines of code like that in the test, to see if your SPI complies with what it's supposed to do.

                PS. I will accept my comment as a correct answer, because i needed to know for sure if it's a bug or intended behaviour and i have got that question answered .

                • 5. Re: RemoteCache.replaceAll infinite loop
                  Radim Vansa Master

                  You keep referencing Map, but RemoteCache is a ConcurrentMap, and overriden method in implemented interface takes precedence (we could say that JDK itself does break/twist the contract). Any ConcurrentMap that does not implement replaceAll on its own will suffer this problem. What you passed in is not a (pure) function but a mutator.

                   

                  While Will is wrong regarding the identity (Map.replaceAll does not compare the old vs. new value at all and ConcurrentMap will use equals even in single VM) a phrase "Please educate yourself" sounds very arrogant; please consider your wording more carefully next time.

                  • 6. Re: RemoteCache.replaceAll infinite loop
                    Dan Berindei Expert

                    To be fair, the replaceAll documentation doesn't mention that the function parameter is not allowed to modify the value in-place. In fact, modifying the values in-place seems to be supported in all the JDK implementations, so Infinispan should really have a warning about that.

                    • 7. Re: RemoteCache.replaceAll infinite loop
                      William Burns Expert

                      Please educate yourself with List.equals(), Set.equals() and Map.equals() (the latter being technically equals to that of Set, no pun intended) javadocs. In the above test initial sets and resulting sets are not equal _by definition_ and it has nothing to do with their identity (hint: but rather their size). I understand why you mention identity, but i refuse to accept its relevance in this particular case.

                      I am more than aware of how collection equals are implemented And actually the Set is always equal to itself (it doesn't matter how many times you change it). If it was this would break the reflexive property. The lambda is never creating a new Set.

                       

                      If you dig a little deeper you will see some more details. First off what I said is technically implementation specific, but most implementations of Map will check object identity first and then use object equality if the first doesn't pass. And even most equality methods are implemented in a similar fashion checking if it equals this.

                       

                      Looking at ConcurrentHashMap.java when it looks at a node it will do identity equality check which will be true in a local JVM when the object is the same between replace calls

                       

                      if (cv == null || cv == ev ||
                        (ev != null && cv.equals(ev))) {
                      

                       

                      In this case on the local JVM it will not get to the object equals invocation with your lamba unless it fails, since you always return the same object.

                       

                      The remote case is different though as the Set is deserialized remotely and the object instance is never the same. Thus it always relies on object identity. Which means the replace value has to be exactly the same, which unfortunately using your lambda it isn't:

                       

                      default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
                        Objects.requireNonNull(function);
                        forEach((k,v) -> {
                         while(!replace(k, v, function.apply(k, v))) {
                         // v changed or k is gone
                         if ( (v = get(k)) == null) {
                         // k is no longer in the map.
                         break;
                        }
                        }
                        });
                      }
                      

                      Note how on line 4 the same value is always passed to the replace method and the function is applied before invoking the replace. This means it is essentially invoking the following every time

                       

                      replace(k, modifiedv, modifiedv);
                      

                       

                      Which as you would expect would always fail. This means it will then get stuck in a loop, because the value is never queued again.

                       

                      As dan.berindei mentioned the next best thing we could do besides what I already mentioned about creating a JIRA to actually implement this the same way is just to update the Javadoc or possibly log a warning etc.

                       

                      Unfortunately RemoteCache implemented ConcurrentMap before it had the replaceAll method (Java 1.8) and it hasn't been updated since then.