[Mono-bugs] [Bug 587994] BigInteger.ModPow can get stuck in an infinite loop using up CPU resources

[bugzilla_noreply at novell.com]

http://bugzilla.novell.com/show_bug.cgi?id=587994

http://bugzilla.novell.com/show_bug.cgi?id=587994#c2


--- Comment #2 from Michael Wood <michaelw at dip.co.uk> 2010-03-15 11:58:57 UTC ---
We've been experimenting more and discovered it isn't a problem specific to a
random number or prime set.  After discovering a set of numbers that it
occurred using I found re-doing the method with those numbers did not cause the
infinite loop.  It appears to only occur when the system is at high CPU usage,
whether this is due to other Mod Pows being performed or not. Here is a simple
sample application where the effect occurs most of the time I run it (over 50%
CPU and the code hung on that method):

    class Program
    {
        static void Main(string[] args)
        {
            int num = 300;

            BigIntThread[] bigInts = new BigIntThread[num];

            for (int i = 0; i < num; i++)
            {
                bigInts[i] = new BigIntThread(i);
            }

            for (int i = 0; i < num; i++)
            {
                bigInts[i].Start();
            }
        }

        public class BigIntThread
        {
            BigInteger bigTwo;
            BigInteger bigRandom;
            BigInteger bigPrime;
            Thread t;
            int id;

            public BigIntThread(int id)
            {
                this.id = id;
                bigTwo = BigInteger.Parse("2");

                bigRandom =
BigInteger.Parse("8258688429231270565973030503031952155764594082923760158315539651487325699428433445581150837282627302891508519305772657577848996431519075307578973539562427");

                bigPrime =
BigInteger.Parse("179769313486231590770839156793787453197860296048756011706444423684197180216158519368947833795864925541502180565485980503646440548199239100050792877003355816639229553136239076508735759914822574862575007425302077447712589550957937778424442426617334727629299387668709205606050270810842907692932019128194467627007");
                t = new Thread(new ThreadStart(ModPow));
            }

            public void Start()
            {
                t.Start();
            }

            public void ModPow()
            {
                Console.WriteLine(id + " started");
                BigInteger bigPower = bigTwo.ModPow(bigRandom, bigPrime);
                Console.WriteLine(id + " stopped");
            }
        }
    }


Could this be attributed to the use of unsafe code within Mod Pow?  We've
changed our implementation to use a singleton for performing the ModPow
however, this effect still occurs when the system is busy and it being a
singleton means that it sticks for all subsequent threads that use the method.

It's a requirement for us to be running 500+ threads that could use Mod Pow in
a short time period.



(In reply to comment #1)
> Please provide a tiple of numbers that show this behavior.

-- 
Configure bugmail: http://bugzilla.novell.com/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.