//this file is part of eMule 
//Copyright (C)2002-2008 Merkur ( strEmail.Format("%s@%s", "devteam", "emule-project.net") / http://www.emule-project.net )
//
//This program is free software; you can redistribute it and/or
//modify it under the terms of the GNU General Public License
//as published by the Free Software Foundation; either
//version 2 of the License, or (at your option) any later version.
//
//This program is distributed in the hope that it will be useful,
//but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//GNU General Public License for more details.
//
//You should have received a copy of the GNU General Public License
//along with this program; if not, write to the Free Software
//Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
#include "stdafx.h"
#include "emule.h"
#include "Opcodes.h"
#include "LastCommonRouteFinder.h"
#include "Server.h"
#include "OtherFunctions.h"
#include "UpDownClient.h"
#include "Preferences.h"
#include "Pinger.h"
#include "emuledlg.h"
#include <Mmsystem.h>

#include <algorithm>

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif


LastCommonRouteFinder::LastCommonRouteFinder() {
	minUpload = 1;
	maxUpload = _UI32_MAX;
	m_upload = _UI32_MAX;
	m_CurUpload = 1;

	m_iPingToleranceMilliseconds = 200;
	m_bUseMillisecondPingTolerance = false;
	m_iNumberOfPingsForAverage = 0;
	m_pingAverage = 0;
	m_lowestPing = 0;
	m_LowestInitialPingAllowed = 10; // this is overridden by the SetPrefs(...) call
    m_NeedMoreSlots = true;

	m_state = _T("");

	needMoreHosts = false;

	threadEndedEvent = new CEvent(0, 1);
	newTraceRouteHostEvent = new CEvent(0, 0);
	prefsEvent = new CEvent(0, 0);

    m_initiateFastReactionPeriod = false;

	m_enabled = false;
	doRun = true;
	AfxBeginThread(RunProc, (LPVOID)this);
}

LastCommonRouteFinder::~LastCommonRouteFinder() {
	delete threadEndedEvent;
	delete newTraceRouteHostEvent;
	delete prefsEvent;
}

bool LastCommonRouteFinder::AddHostToCheck(uint32 ip) {
    bool gotEnoughHosts = true;

	if(needMoreHosts && IsGoodIP(ip, true)) {
		addHostLocker.Lock();

		if(needMoreHosts) {
            gotEnoughHosts = AddHostToCheckNoLock(ip);
		}

        addHostLocker.Unlock();
    }

    return gotEnoughHosts;
}

bool LastCommonRouteFinder::AddHostToCheckNoLock(uint32 ip) {
    if(needMoreHosts && IsGoodIP(ip, true)) {
	    //hostsToTraceRoute.AddTail(ip);
	    hostsToTraceRoute.SetAt(ip, 0);

        if(hostsToTraceRoute.GetCount() >= 10) {
			needMoreHosts = false;

			// Signal that there's hosts to fetch.
			newTraceRouteHostEvent->SetEvent();
        }
    }

    return !needMoreHosts;
}

bool LastCommonRouteFinder::AddHostsToCheck(CTypedPtrList<CPtrList, CServer*> &list) {
    bool gotEnoughHosts = true;

	if(needMoreHosts) {
		addHostLocker.Lock();

		if(needMoreHosts) {
			POSITION pos = list.GetHeadPosition();

            if(pos) {
				uint32 startPos = rand()/(RAND_MAX/(min(list.GetCount(), 100)));

				for(uint32 skipCounter = 0; skipCounter < startPos && pos != NULL; skipCounter++) {
					list.GetNext(pos);
                }

                if(!pos) {
                    pos = list.GetHeadPosition();
                }

			    uint32 tryCount = 0;
			    while(needMoreHosts && tryCount < (uint32)list.GetCount()) {
				    tryCount++;
				    CServer* server = list.GetNext(pos);
                    if(!pos) {
                        pos = list.GetHeadPosition();
                    }

				    uint32 ip = server->GetIP();

				    AddHostToCheckNoLock(ip);
                }
            }
		}

        gotEnoughHosts = !needMoreHosts;

        addHostLocker.Unlock();
    }

    return gotEnoughHosts;
}

bool LastCommonRouteFinder::AddHostsToCheck(CUpDownClientPtrList &list) {
    bool gotEnoughHosts = true;

	if(needMoreHosts) {
		addHostLocker.Lock();

		if(needMoreHosts) {
			POSITION pos = list.GetHeadPosition();

            if(pos) {
				uint32 startPos = rand()/(RAND_MAX/(min(list.GetCount(), 100)));

				for(uint32 skipCounter = 0; skipCounter < startPos && pos != NULL; skipCounter++) {
					list.GetNext(pos);
                }

                if(!pos) {
                    pos = list.GetHeadPosition();
                }

			    uint32 tryCount = 0;
			    while(needMoreHosts && tryCount < (uint32)list.GetCount()) {
				    tryCount++;
                    CUpDownClient* client = list.GetNext(pos);
                    if(!pos) {
                        pos = list.GetHeadPosition();
                    }

					uint32 ip = client->GetIP();

				    AddHostToCheckNoLock(ip);
                }
            }
		}

        gotEnoughHosts = !needMoreHosts;

        addHostLocker.Unlock();
    }

    return gotEnoughHosts;
}

CurrentPingStruct LastCommonRouteFinder::GetCurrentPing() {
	CurrentPingStruct returnVal;

	if(m_enabled) {
		pingLocker.Lock();
		returnVal.state = m_state;
		returnVal.latency = m_pingAverage;
		returnVal.lowest = m_lowestPing;
        returnVal.currentLimit = m_upload;
		pingLocker.Unlock();
	} else {
		returnVal.state = _T("");
		returnVal.latency = 0;
		returnVal.lowest = 0;
        returnVal.currentLimit = 0;
	}

	return returnVal;
}

bool LastCommonRouteFinder::AcceptNewClient() {

// By Taz - fix coherent coding
/*
	return acceptNewClient || !m_enabled; // if enabled, then return acceptNewClient, otherwise return true
*/
	return !m_enabled || acceptNewClient; // if enabled, then return acceptNewClient, otherwise return true
// <------- fix

}

void LastCommonRouteFinder::SetPrefs(bool pEnabled, uint32 pCurUpload, uint32 pMinUpload, uint32 pMaxUpload, bool pUseMillisecondPingTolerance, double pPingTolerance, uint32 pPingToleranceMilliseconds, uint32 pGoingUpDivider, uint32 pGoingDownDivider, uint32 pNumberOfPingsForAverage, uint32 pLowestInitialPingAllowed, bool pNeedMoreSlots) {
	bool sendEvent = false;

	prefsLocker.Lock();

	if(pMinUpload <= 1024) {
		minUpload = 1024;
	} else {
		minUpload = pMinUpload;
    }

	if(pMaxUpload != 0) {
		maxUpload = pMaxUpload;
		if(maxUpload < minUpload) {
            minUpload = maxUpload;
		}
	} else {
		maxUpload = pCurUpload+10*1024; //_UI32_MAX;
	}

// Contrib - optimization
	bool bStatBarResetted = false; //>>> WiZaRd::Optimization
// <-------- optimization

	if(pEnabled && m_enabled == false) {
		sendEvent = true;
		// this will show the area for ping info in status bar.
		theApp.emuledlg->SetStatusBarPartsSize();

// Contrib - optimization
		bStatBarResetted = true; //>>> WiZaRd::Optimization
// <-------- optimization

	} else if(pEnabled == false) {
		if(m_enabled) {
		    // this will remove the area for ping info in status bar.
			theApp.emuledlg->SetStatusBarPartsSize();

// Contrib - optimization
			bStatBarResetted = true; //>>> WiZaRd::Optimization
// <-------- optimization

        }
		//prefsEvent->ResetEvent();
        sendEvent = true;
	}

	// this will resize the area for ping info in status bar.
	if(m_bUseMillisecondPingTolerance != pUseMillisecondPingTolerance) {

// Contrib - optimization
		if(!bStatBarResetted) //>>> WiZaRd::Optimization
// <-------- optimization

		theApp.emuledlg->SetStatusBarPartsSize();
    }

	m_enabled = pEnabled;
	m_bUseMillisecondPingTolerance = pUseMillisecondPingTolerance;
	m_pingTolerance = pPingTolerance;
	m_iPingToleranceMilliseconds = pPingToleranceMilliseconds;
	m_goingUpDivider = pGoingUpDivider;
	m_goingDownDivider = pGoingDownDivider;
	m_CurUpload = pCurUpload;
	m_iNumberOfPingsForAverage = pNumberOfPingsForAverage;
	m_LowestInitialPingAllowed = pLowestInitialPingAllowed;
    m_NeedMoreSlots = pNeedMoreSlots;

	uploadLocker.Lock();

	if (m_upload > maxUpload || pEnabled == false) {
		m_upload = maxUpload;
    }

	uploadLocker.Unlock();
	prefsLocker.Unlock();

	if(sendEvent) {
		prefsEvent->SetEvent();
    }
}

void LastCommonRouteFinder::InitiateFastReactionPeriod() {
	prefsLocker.Lock();

    m_initiateFastReactionPeriod = true;

    prefsLocker.Unlock();
}

uint32 LastCommonRouteFinder::GetUpload() {
	uint32 returnValue;

	uploadLocker.Lock();

	returnValue = m_upload;

	uploadLocker.Unlock();

	return returnValue;
}

void LastCommonRouteFinder::SetUpload(uint32 newValue) {
	uploadLocker.Lock();

	m_upload = newValue;

	uploadLocker.Unlock();
}

/**
 * Make the thread exit. This method will not return until the thread has stopped
 * looping.
 */
void LastCommonRouteFinder::EndThread() {
	// signal the thread to stop looping and exit.
	doRun = false;

	prefsEvent->SetEvent();
	newTraceRouteHostEvent->SetEvent();

	// wait for the thread to signal that it has stopped looping.
	threadEndedEvent->Lock();
}

/**
 * Start the thread. Called from the constructor in this class.
 *
 * @param pParam
 *
 * @return
 */
UINT AFX_CDECL LastCommonRouteFinder::RunProc(LPVOID pParam) {
	DbgSetThreadName("LastCommonRouteFinder");
	InitThreadLocale();

// Contrib - SafeHash
	// SLUGFILLER: SafeHash
	CReadWriteLock lock(&theApp.m_threadlock);
	if (!lock.ReadLock(0))
		return 0;
	// SLUGFILLER: SafeHash
// <-------- SafeHash

	LastCommonRouteFinder* lastCommonRouteFinder = (LastCommonRouteFinder*)pParam;

	return lastCommonRouteFinder->RunInternal();
}

/**
 * @return always returns 0.
 */
UINT LastCommonRouteFinder::RunInternal() {
	Pinger pinger;
	bool hasSucceededAtLeastOnce = false;

	while(doRun) {
		// wait for updated prefs
		prefsEvent->Lock();

		bool enabled = m_enabled;

		// retry loop. enabled will be set to false in end of this loop, if to many failures (tries too large)
		while(doRun && enabled) {
			bool foundLastCommonHost = false;
			uint32 lastCommonHost = 0;
			uint32 lastCommonTTL = 0;
			uint32 hostToPing = 0;
			bool useUdp = false;

			hostsToTraceRoute.RemoveAll();

            UInt32Clist pingDelays;
			pingDelays.RemoveAll();
			uint64 pingDelaysSum = 0;

			pingLocker.Lock();
			m_pingAverage = 0;
			m_lowestPing = 0;
			m_state = GetResString(IDS_USS_STATE_PREPARING);
			pingLocker.Unlock();

			// Calculate a good starting value for the upload control. If the user has entered a max upload value, we use that. Otherwise 10 KBytes/s
			int startUpload = (maxUpload != _UI32_MAX)?maxUpload:10*1024;

			bool atLeastOnePingSucceded = false;
			while(doRun && enabled && foundLastCommonHost == false) {
				uint32 traceRouteTries = 0;
				while(doRun && enabled && foundLastCommonHost == false && (traceRouteTries < 5 || hasSucceededAtLeastOnce && traceRouteTries < _UI32_MAX) && (hostsToTraceRoute.GetCount() < 10 || hasSucceededAtLeastOnce)) {
					traceRouteTries++;

					lastCommonHost = 0;

// Contrib - fix
					if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

					theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Try #%i. Collecting hosts..."), traceRouteTries);

					addHostLocker.Lock();
					needMoreHosts = true;
					addHostLocker.Unlock();

					// wait for hosts to traceroute
					newTraceRouteHostEvent->Lock();

// Contrib - fix
					if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

					theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Got enough hosts. Listing the hosts that will be tracerouted:"));

					POSITION pos = hostsToTraceRoute.GetStartPosition();
					int counter = 0;
					while(pos != NULL) {
						counter++;
						uint32 hostToTraceRoute, dummy;
                        hostsToTraceRoute.GetNextAssoc(pos, hostToTraceRoute, dummy);
						IN_ADDR stDestAddr;
						stDestAddr.s_addr = hostToTraceRoute;

// Contrib - fix
						if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

						theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Host #%i: %s"), counter, ipstr(stDestAddr));
					}

					// find the last common host, using traceroute

// Contrib - fix
					if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

					theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Starting traceroutes to find last common host."));

					// for the tracerouting phase (preparing...) we need to disable uploads so we get a faster traceroute and better ping values.
					SetUpload(2*1024);
					Sleep(SEC2MS(1));

					if(m_enabled == false) {
						enabled = false;
                    }

					bool failed = false;

					uint32 curHost = 0;
					for(uint32 ttl = 1; doRun && enabled && (curHost != 0 && ttl <= 64 || curHost == 0 && ttl < 10) && foundLastCommonHost == false && failed == false; ttl++) {

// Contrib - fix
						if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

						theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Pinging for TTL %i..."), ttl);

						useUdp = false; // PENDING: Get default value from prefs?

						curHost = 0;
						if(m_enabled == false) {
							enabled = false;
                        }

						uint32 lastSuccedingPingAddress = 0;
                        uint32 lastDestinationAddress = 0;
                        uint32 hostsToTraceRouteCounter = 0;
                        bool failedThisTtl = false;
                        bool unexpectedTimeout = false;
						POSITION pos = hostsToTraceRoute.GetStartPosition();
                        while(doRun && enabled && failed == false && failedThisTtl == false && pos != NULL && !unexpectedTimeout &&
                              ( lastDestinationAddress == 0 || lastDestinationAddress == curHost)) // || pingStatus.success == false && pingStatus.error == IP_REQ_TIMED_OUT ))
						{
    						PingStatus pingStatus = {0};

                            hostsToTraceRouteCounter++;

							// this is the current address we send ping to, in loop below.
							// PENDING: Don't confuse this with curHost, which is unfortunately almost
							// the same name. Will rename one of these variables as soon as possible, to
							// get more different names.
							uint32 curAddress, dummy;
                            hostsToTraceRoute.GetNextAssoc(pos, curAddress, dummy);

							pingStatus.success = false;
							for(int counter = 0; doRun && enabled && counter < 2 && (pingStatus.success == false || pingStatus.success == true && pingStatus.status != IP_SUCCESS && pingStatus.status != IP_TTL_EXPIRED_TRANSIT); counter++) {

// Contrib - fix
/*
								pingStatus = pinger.Ping(curAddress, ttl, true, useUdp);
*/
								pingStatus = pinger.Ping(curAddress, ttl, thePrefs.GetLogUlDlEvents(), useUdp); //>>> WiZaRd::Prevent USS Spam
// <-------- fix

								if(doRun && enabled &&
                                   (
                                    pingStatus.success == false ||
                                    pingStatus.success == true &&
                                    pingStatus.status != IP_SUCCESS &&
                                    pingStatus.status != IP_TTL_EXPIRED_TRANSIT
                                   ) &&
                                   counter < 3-1)
                                {
									IN_ADDR stDestAddr;
									stDestAddr.s_addr = curAddress;

// Contrib - fix
									if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

									{
                                    theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Failure #%i to ping host! (TTL: %i IP: %s error: %i). Sleeping 1 sec before retry. Error info follows."), counter+1, ttl, ipstr(stDestAddr), (pingStatus.success)?pingStatus.status:pingStatus.error);
									pinger.PIcmpErr((pingStatus.success)?pingStatus.status:pingStatus.error);
									}

									Sleep(1000);

									if(m_enabled == false)
										enabled = false;

									// trying other ping method
									useUdp = !useUdp;
								}
							}

							if(pingStatus.success == true && pingStatus.status == IP_TTL_EXPIRED_TRANSIT) {
                                if(curHost == 0) {
									curHost = pingStatus.destinationAddress;

                                    if(hostsToTraceRouteCounter > 1) {
                                        unexpectedTimeout = true;

// Contrib - fix
										if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

    								    theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: First successful ping at this ttl, which is unexpected. Assuming differing responder."));
                                    }
                                }

								atLeastOnePingSucceded = true;
								lastSuccedingPingAddress = curAddress;
                                lastDestinationAddress = pingStatus.destinationAddress;
							} else {
								// failed to ping this host for some reason.
								// Or we reached the actual host we are pinging. We don't want that, since it is too close.
								// Remove it.
								IN_ADDR stDestAddr;
								stDestAddr.s_addr = curAddress;
								if(pingStatus.success == true && pingStatus.status == IP_SUCCESS) {

// Contrib - fix
									if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

									theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Host was too close! Removing this host. (TTL: %i IP: %s status: %i). Removing this host and restarting host collection."), ttl, ipstr(stDestAddr), pingStatus.status);

									hostsToTraceRoute.RemoveKey(curAddress);
								} else if(pingStatus.success == true && pingStatus.status == IP_DEST_HOST_UNREACHABLE) {

// Contrib - fix
									if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

									{
									theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Host unreacheable! (TTL: %i IP: %s status: %i). Removing this host. Status info follows."), ttl, ipstr(stDestAddr), pingStatus.status);
									pinger.PIcmpErr(pingStatus.status);
									}

									hostsToTraceRoute.RemoveKey(curAddress);
                                } else if(pingStatus.success == true) {

// Contrib - fix
									if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

									{
									theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Unknown ping status! (TTL: %i IP: %s status: %i). Reason follows. Changing ping method to see if it helps."), ttl, ipstr(stDestAddr), pingStatus.status);
									pinger.PIcmpErr(pingStatus.status);
									}
									useUdp = !useUdp;
								} else {
									if(pingStatus.error == IP_REQ_TIMED_OUT) {

// Contrib - fix
										if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

										{
										theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Timeout when pinging a host! (TTL: %i IP: %s Error: %i). Keeping host. Error info follows."), ttl, ipstr(stDestAddr), pingStatus.error);
										pinger.PIcmpErr(pingStatus.error);
										}

                                        if(hostsToTraceRouteCounter > 2 && lastSuccedingPingAddress == 0) {
                                            // several pings have timed out on this ttl. Probably we can't ping on this ttl at all
                                            failedThisTtl = true;
                                        } else if(lastSuccedingPingAddress != 0) {
                                            unexpectedTimeout = true;

// Contrib - fix
											if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

    										theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Unexpected timeout."));
                                        }
                                    } else {

// Contrib - fix
										if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

										{
									    theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Unknown pinging error! (TTL: %i IP: %s status: %i). Reason follows. Changing ping method to see if it helps."), ttl, ipstr(stDestAddr), pingStatus.error);
										pinger.PIcmpErr(pingStatus.error);
										}
    									useUdp = !useUdp;
									}
								}

                                if(hostsToTraceRoute.GetSize() <= 8) {

// Contrib - fix
									if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

									theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: To few hosts to traceroute left. Restarting host colletion."));
                                    failed = true;
                                }
							}
						}

						if(failed == false) {
							if(curHost != 0 && lastDestinationAddress != 0) {
								if(lastDestinationAddress == curHost && !unexpectedTimeout) {
									IN_ADDR stDestAddr;
									stDestAddr.s_addr = curHost;

// Contrib - fix
									if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

									theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Host at TTL %i: %s"), ttl, ipstr(stDestAddr));

									lastCommonHost = curHost;
									lastCommonTTL = ttl;
								} else /*if(lastSuccedingPingAddress != 0)*/ {
									foundLastCommonHost = true;
									hostToPing = lastSuccedingPingAddress;

									CString hostToPingString = ipstr(hostToPing);

                                    if(unexpectedTimeout) {

// Contrib - fix
										if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

                                        theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Unexpected timeout at TTL %i: Assuming it means responder differs. This will be the host to ping: %s"), ttl, hostToPingString);
                                    }

									if(lastCommonHost != 0) {

// Contrib - fix
										if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

										theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Found differing host at TTL %i: %s. This will be the host to ping."), ttl, hostToPingString);
									} else {

// Contrib - optimization
/*
										CString lastCommonHostString = ipstr(lastDestinationAddress);
*/
// <-------- optimization

										lastCommonHost = lastDestinationAddress;
										lastCommonTTL = ttl;

// Contrib - fix
										if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix
										{

// Contrib - optimization
										CString lastCommonHostString = ipstr(lastDestinationAddress);
// <-------- optimization

										theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Found differing host at TTL %i, but last ttl couldn't be pinged so we don't know last common host. Taking a chance and using first differing ip as last commonhost. Host to ping: %s. Faked LastCommonHost: %s"), ttl, hostToPingString, lastCommonHostString);
										}
									}
								}
							} else {

// Contrib - fix
								if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

								{
								if(ttl < 4) {
									theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Could perform no ping at all at TTL %i. Trying next ttl."), ttl);
								} else {
									theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Could perform no ping at all at TTL %i. Giving up."), ttl);
                                }
								}
								lastCommonHost = 0;
							}
						}
					}

					if(foundLastCommonHost == false && traceRouteTries >= 3) {

// Contrib - fix
						if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

						theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Tracerouting failed several times. Waiting a few minutes before trying again."));

                        SetUpload(maxUpload);

						pingLocker.Lock();
						m_state = GetResString(IDS_USS_STATE_WAITING);
						pingLocker.Unlock();

						prefsEvent->Lock(3*60*1000);

                        pingLocker.Lock();
						m_state = GetResString(IDS_USS_STATE_PREPARING);
                        pingLocker.Unlock();
					}

			        if(m_enabled == false) {
				        enabled = false;
                    }
				}

                if(enabled) {

// Contrib - fix
					if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

				    theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Done tracerouting. Evaluating results."));

				    if(foundLastCommonHost == true) {
					    IN_ADDR stLastCommonHostAddr;
					    stLastCommonHostAddr.s_addr = lastCommonHost;

					    // log result

// Contrib - fix
						if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

					    theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Found last common host. LastCommonHost: %s @ TTL: %i"), ipstr(stLastCommonHostAddr), lastCommonTTL);

					    IN_ADDR stHostToPingAddr;
					    stHostToPingAddr.s_addr = hostToPing;

// Contrib - fix
						if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

					    theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Found last common host. HostToPing: %s"), ipstr(stHostToPingAddr));
				    } else {

// Contrib - fix
						if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

						{
					    theApp.QueueDebugLogLine(false,GetResString(IDS_USS_TRACEROUTEOFTENFAILED));
						theApp.QueueLogLine(true, GetResString(IDS_USS_TRACEROUTEOFTENFAILED));
						}
					    enabled = false;

					    pingLocker.Lock();
						m_state = GetResString(IDS_USS_STATE_ERROR);
					    pingLocker.Unlock();

					    // PENDING: this may not be thread safe
					    thePrefs.SetDynUpEnabled(false);
				    }
                }
			}

			if(m_enabled == false) {
				enabled = false;
            }

			if(doRun && enabled) {

// Contrib - fix
				if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

				theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Finding a start value for lowest ping..."));
            }

			// PENDING:
			prefsLocker.Lock();
			uint32 lowestInitialPingAllowed = m_LowestInitialPingAllowed;
			prefsLocker.Unlock();

			uint32 initial_ping = _UI32_MAX;

			bool foundWorkingPingMethod = false;
			// finding lowest ping
			for(int initialPingCounter = 0; doRun && enabled && initialPingCounter < 10; initialPingCounter++) {
				Sleep(200);

// Contrib - fix
/*
				PingStatus pingStatus = pinger.Ping(hostToPing, lastCommonTTL, true, useUdp);
*/
				PingStatus pingStatus = pinger.Ping(hostToPing, lastCommonTTL, thePrefs.GetLogUlDlEvents(), useUdp); //>>> WiZaRd::Prevent USS Spam
// <-------- fix

				if (pingStatus.success && pingStatus.status == IP_TTL_EXPIRED_TRANSIT) {
					foundWorkingPingMethod = true;

					if(pingStatus.delay > 0 && pingStatus.delay < initial_ping) {
						initial_ping = (uint32)pingStatus.delay;
                    }
				} else {

// Contrib - fix
					if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

					{
					theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: %s-Ping #%i failed. Reason follows"), useUdp?_T("UDP"):_T("ICMP"), initialPingCounter);
					pinger.PIcmpErr(pingStatus.error);
					}

					// trying other ping method
					if(!pingStatus.success && !foundWorkingPingMethod) {
						useUdp = !useUdp;
                    }
				}

				if(m_enabled == false) {
					enabled = false;
                }
			}

			// Set the upload to a good starting point
			SetUpload(startUpload);
			Sleep(SEC2MS(1));
			DWORD initTime = ::GetTickCount();

			// if all pings returned 0, initial_ping will not have been changed from default value.
			// then set initial_ping to lowestInitialPingAllowed
            if(initial_ping == _UI32_MAX) {
                initial_ping = lowestInitialPingAllowed;
            } else if(initial_ping < lowestInitialPingAllowed) {
                initial_ping = lowestInitialPingAllowed;
            } else if(initial_ping % 10 == 0 && initial_ping < 30) {
                // workaround for some OS:es where realtime measurement doesn't work, and ping times are always multiples of 10
                initial_ping += 5;
                lowestInitialPingAllowed = initial_ping;
            }

			uint32 upload = 0;

			hasSucceededAtLeastOnce = true;

			if(doRun && enabled) {

// Contrib - fix
				if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

				{
				if(initial_ping != lowestInitialPingAllowed) {
					theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Lowest ping: %i ms"), initial_ping);
				} else {
					theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Lowest ping: %i ms. (Filtered lower values. Lowest ping is not allowed to go under %i ms)"), initial_ping, lowestInitialPingAllowed);
				}
                }
				prefsLocker.Lock();
				upload = m_CurUpload;

				if(upload < minUpload) {
					upload = minUpload;
                }
				if(upload > maxUpload) {
					upload = maxUpload;
                }
				prefsLocker.Unlock();
			}

			if(m_enabled == false) {
				enabled = false;
            }

			if(doRun && enabled) {

// Contrib - fix
				if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

				{
				theApp.QueueDebugLogLine(false, GetResString(IDS_USS_STARTING));
				theApp.QueueLogLine(true, GetResString(IDS_USS_STARTING)  );
				}
            }

			pingLocker.Lock();
			m_state = _T("");
			pingLocker.Unlock();

            sint64 integral = 0;
            CList<sint64,sint64> oldErrors;

			//CArray<uint64,uint64> lowestPingValuesPerSpeed;
			//CArray<double,double> averagePingValuesPerSpeed;
			//CArray<uint64,uint64> pingCountPerSpeed;
			//uint64 maxSpeedLogged = 0;

			//lowestPingValuesPerSpeed.SetSize(512);
			//averagePingValuesPerSpeed.SetSize(512);
			//pingCountPerSpeed.SetSize(512);

			//DWORD lastTickLoggedPingArrays = timeGetTime();

			// There may be several reasons to start over with tracerouting again.
			// Currently we only restart if we get an unexpected ip back from the
			// ping at the set TTL.
			bool restart = false;

			DWORD lastLoopTick = ::GetTickCount();
			DWORD lastUploadReset = 0;
            sint32 damper = 0;
            uint32 damperCounter = 0;

			while(doRun && enabled && restart == false) {
				DWORD ticksBetweenPings = 1000;
				if(maxUpload > 0) {
					// ping packages being 64 bytes, this should use 1% of bandwidth (one hundredth of bw).
					ticksBetweenPings = (64*100*1000)/maxUpload;

					if(ticksBetweenPings < 125) {
					    // never ping more than 8 packages a second
						ticksBetweenPings = 125;
					} else if(ticksBetweenPings > 1000) {
						ticksBetweenPings = 1000;
                    }
				}

				DWORD curTick = ::GetTickCount();

				DWORD timeSinceLastLoop = curTick-lastLoopTick;
				if(timeSinceLastLoop < ticksBetweenPings) {
					//theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Sleeping %i ms, timeSinceLastLoop %i ms ticksBetweenPings %i ms"), ticksBetweenPings-timeSinceLastLoop, timeSinceLastLoop, ticksBetweenPings);
					Sleep(ticksBetweenPings-timeSinceLastLoop);
				}

				lastLoopTick = curTick;

				prefsLocker.Lock();
				double pingTolerance = m_pingTolerance;
				uint32 pingToleranceMilliseconds = m_iPingToleranceMilliseconds;
				bool useMillisecondPingTolerance = m_bUseMillisecondPingTolerance;
				uint32 goingUpDivider = m_goingUpDivider;
				uint32 goingDownDivider = m_goingDownDivider;
				uint32 numberOfPingsForAverage = m_iNumberOfPingsForAverage;
				lowestInitialPingAllowed = m_LowestInitialPingAllowed; // PENDING
                uint32 curUpload = m_CurUpload;

                bool initiateFastReactionPeriod = m_initiateFastReactionPeriod;
                m_initiateFastReactionPeriod = false;
				prefsLocker.Unlock();

                if(initiateFastReactionPeriod) {

// Contrib - fix
					if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

					{
                    theApp.QueueDebugLogLine(false, GetResString(IDS_USS_MANUALUPLOADLIMITDETECTED));
					theApp.QueueLogLine(true, GetResString(IDS_USS_MANUALUPLOADLIMITDETECTED) );
					}

                    // the first 60 seconds will use hardcoded up/down slowness that is faster
                    initTime = ::GetTickCount();
                }

				DWORD tempTick = ::GetTickCount();

				if(tempTick - initTime < SEC2MS(1)) {
					goingUpDivider = 1;
					goingDownDivider = 1;
                } else if(tempTick - initTime < SEC2MS(60)) {
                    // slide from 1 to the target divider value over 60 seconds. (dividerNow = (maxDivider-1)/(60secs-1sec)*(currentTime-starTime)+1)
                    goingUpDivider = (UINT)(((double)max(goingUpDivider, 1)-1)/(SEC2MS(60)-SEC2MS(1))*((tempTick-initTime)-SEC2MS(1)) + 1);
                    goingDownDivider = (UINT)(((double)max(goingDownDivider, 1)-1)/(SEC2MS(60)-SEC2MS(1))*((tempTick-initTime)-SEC2MS(1)) + 1);
                    //theApp.QueueDebugLogLine(false, _T("tempTick-initTime: %i, goingUpDivider: %i, goingDownDivider: %i"), tempTick-initTime, goingUpDivider, goingDownDivider);
				} else if(tempTick - initTime < SEC2MS(61)) {
					lastUploadReset = tempTick;
					prefsLocker.Lock();
					upload = m_CurUpload;
					prefsLocker.Unlock();
				}

                goingDownDivider = max(goingDownDivider, 1);
                goingUpDivider = max(goingUpDivider, 1);

				uint32 target_ping = (UINT)(initial_ping*pingTolerance);
				if (useMillisecondPingTolerance) {
					target_ping = pingToleranceMilliseconds; 
				} else {
					target_ping = (UINT)(initial_ping*pingTolerance);
                }

				uint32 raw_ping = target_ping; // this value will cause the upload speed not to change at all.

				bool pingFailure = false;        
				for(uint64 pingTries = 0; doRun && enabled && (pingTries == 0 || pingFailure) && pingTries < 60; pingTries++) {
                    if(m_enabled == false) {
                        enabled = false;
                    }

					// ping the host to ping
					PingStatus pingStatus = pinger.Ping(hostToPing, lastCommonTTL, false, useUdp);

					if(pingStatus.success && pingStatus.status == IP_TTL_EXPIRED_TRANSIT) {
						if(pingStatus.destinationAddress != lastCommonHost) {
							// something has changed about the topology! We got another ip back from this ttl than expected.
							// Do the tracerouting again to figure out new topology
							CString lastCommonHostAddressString = ipstr(lastCommonHost);
							CString destinationAddressString = ipstr(pingStatus.destinationAddress);

// Contrib - fix
							if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

							theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Network topology has changed. TTL: %i Expected ip: %s Got ip: %s Will do a new traceroute."), lastCommonTTL, lastCommonHostAddressString, destinationAddressString);
							restart = true;
						}

						raw_ping = (uint32)pingStatus.delay;

						if(pingFailure) {
							// only several pings in row should fails, the total doesn't count, so reset for each successful ping
							pingFailure = false;

							//theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Ping #%i successful. Continuing."), pingTries);
						}
					} else {
						raw_ping = target_ping*3+initial_ping*3; // this value will cause the upload speed be lowered.

						pingFailure = true;

                        if(m_enabled == false) {
				            enabled = false;
                        } else if(pingTries > 3) {
							prefsEvent->Lock(1000);
                        }

						//theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: %s-Ping #%i failed. Reason follows"), useUdp?_T("UDP"):_T("ICMP"), pingTries);
						//pinger.PIcmpErr(pingStatus.error);
					}

                    if(m_enabled == false) {
				        enabled = false;
                    }
				}

				if(pingFailure) {
                    if(enabled) {

// Contrib - fix
						if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

					    theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: No response to pings for a long time. Restarting..."));
                    }
					restart = true;
				}

				if(restart == false) {
					if(raw_ping > 0 && raw_ping < initial_ping && initial_ping > lowestInitialPingAllowed) {

// Contrib - fix
						if (thePrefs.GetLogUlDlEvents()) //>>> WiZaRd::Prevent USS Spam
// <-------- fix

						theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: New lowest ping: %i ms. Old: %i ms"), max(raw_ping,lowestInitialPingAllowed), initial_ping);
						initial_ping = (UINT)max(raw_ping, lowestInitialPingAllowed);
					}

					pingDelaysSum += raw_ping;
					pingDelays.AddTail(raw_ping);
					while(!pingDelays.IsEmpty() && (uint32)pingDelays.GetCount() > numberOfPingsForAverage) {
						uint32 pingDelay = pingDelays.RemoveHead();
						pingDelaysSum -= pingDelay;
					}

                    uint32 pingAverage = Median(pingDelays); //(pingDelaysSum/pingDelays.GetCount());

					//{
					//	INT_PTR speedInKBPS = (curUpload/1024);
					//	if(lowestPingValuesPerSpeed.GetAt(speedInKBPS) == NULL || lowestPingValuesPerSpeed.GetAt(speedInKBPS) > raw_ping) {
					//		lowestPingValuesPerSpeed.SetAtGrow(speedInKBPS, raw_ping);
					//	}

					//	if(pingCountPerSpeed.GetAt(speedInKBPS) == NULL) {
     //                     pingCountPerSpeed.SetAtGrow(speedInKBPS, 0);
					//	}

					//	if(averagePingValuesPerSpeed.GetAt(speedInKBPS) == NULL || pingCountPerSpeed.GetAt(speedInKBPS) == 0) {
					//		averagePingValuesPerSpeed.SetAtGrow(speedInKBPS, raw_ping);
					//	} else {
     //                       uint64 oldWeight = min(10, pingCountPerSpeed.GetAt(speedInKBPS));

					//		double newAveragePingValue = (averagePingValuesPerSpeed.GetAt(speedInKBPS)*oldWeight+raw_ping)/(oldWeight+1);
     //                       averagePingValuesPerSpeed.SetAtGrow(speedInKBPS, newAveragePingValue);
					//	}

					//	if(pingCountPerSpeed.GetAt(speedInKBPS) < 10) {
					//		pingCountPerSpeed.SetAtGrow(speedInKBPS, pingCountPerSpeed.GetAt(speedInKBPS)+1);
					//	}

					//	if(speedInKBPS > maxSpeedLogged) {
					//		maxSpeedLogged = speedInKBPS;
					//	}

					//	if(timeGetTime() - lastTickLoggedPingArrays > 60*1000) {
					//		lastTickLoggedPingArrays = timeGetTime();

					//		theApp.QueueDebugLogLine(false, _T("Logging ping times for speeds (speed, avg, lowest, count, percent of lowest):"));

					//		for(int logCounter = 0; logCounter < maxSpeedLogged; logCounter++) {
					//			theApp.QueueDebugLogLine(false, _T("%i, %3.2f, %I64i, %I64i, %3.2f%%"), logCounter, averagePingValuesPerSpeed.GetAt(logCounter), lowestPingValuesPerSpeed.GetAt(logCounter), pingCountPerSpeed.GetAt(logCounter), (averagePingValuesPerSpeed.GetAt(logCounter)/max(1,initial_ping))*100);
					//		}
					//	}
					//}

                    //{
                    //    prefsLocker.Lock();
                    //    uint32 tempCurUpload = m_CurUpload;
                    //    prefsLocker.Unlock();

                    //    theApp.QueueDebugLogLine(false, _T("USS-Debug: %i %i %i"), raw_ping, upload, tempCurUpload);
                    //}

					pingLocker.Lock();
					m_pingAverage = (UINT)pingAverage;
					m_lowestPing = initial_ping;
					pingLocker.Unlock();

					// Calculate Waiting Time
					sint64 error = ((int)target_ping) - (int)pingAverage;

                    //theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: ----- Ping cur %3i ms. Median: %3i ms %2i values. Error: %3I64i Integral: %5I64i"), raw_ping, pingAverage, pingDelays.GetCount(), error, integral);
                    //theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: ----- Ping cur %3i %u"), raw_ping, timeGetTime());

                    // Some kind of PID-controller.
                    // To get the same behaviour as old code, set pconst = 1.0f and the others to 0
                    // Someone may want to expose these to prefs to enable easier experimentation with the values
                    const float pconst = 0.90f;
                    const float iconst = 0.10f;
                    const float dconst = 0.30f;
                    const uint32 numberOfOldErrors = 30*1000/ticksBetweenPings;

                    //if(error < -(sint32)target_ping) {
                    //    error = -(sint32)target_ping;
                    //}

                    sint64 lastError = error;
                    if(!oldErrors.IsEmpty()) {
                        lastError = oldErrors.GetTail();
                    }

                    sint64 derivate = error-lastError;

                    integral += error;
                    oldErrors.AddTail(error);
					while(oldErrors.GetCount() > 1 && (m_NeedMoreSlots || (uint32)oldErrors.GetCount() > numberOfOldErrors)) {
						sint64 oldError = oldErrors.RemoveHead();
						integral -= oldError;
					}

					// calculate the change of speed
					sint64 ulDeltaTemp = (sint64)(pconst*error + iconst*(integral/oldErrors.GetCount()) + dconst*derivate); //*1024*10 / (sint64)(goingDownDivider*initial_ping);

                    damperCounter++;

                    // Calculate change of upload speed
					if(ulDeltaTemp < 0) {
						//Ping too high
						acceptNewClient = false;

                        damper++;

                        if(damper > 10) {
                            damper = -10;
						    // lower the speed
                            sint64 ulDelta = min(ulDeltaTemp*1024*10*20*20 / (sint64)(goingDownDivider*initial_ping*max(damperCounter,20)), -1);

                            damperCounter = 0;

                            uint32 newUpload;

						    // prevent underflow
						    if(upload > -ulDelta) {
							    newUpload = (UINT)(upload + ulDelta);
						    } else {
							    newUpload = 0;
						    }

                            //theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Down! Ping cur %3i ms. Median: %3i ms %2i values. Error: %3I64i Integral: %5I64i New Upload %6i + %4I64i = %6i"), raw_ping, pingAverage, pingDelays.GetCount(), error, integral, upload, ulDelta, newUpload);

                            upload = newUpload;
                        }
					} else if(ulDeltaTemp > 0) {
						//Ping lower than max allowed
						acceptNewClient = true;

						if(curUpload+10*1024 > upload && !m_NeedMoreSlots) {
                            damper--;

                            if(damper < -10) {
                                damper = 10;

						        // raise the speed
                                uint64 ulDelta = max(ulDeltaTemp*1024*10*20*20 / (uint64)(goingUpDivider*initial_ping*max(damperCounter,20)), 1);

                                damperCounter = 0;

                                uint32 newUpload;

                                // prevent overflow
						        if(_I32_MAX-upload > ulDelta) {
							        newUpload = (UINT)(upload + ulDelta);
						        } else {
							        newUpload = _I32_MAX;
                                }

                                //theApp.QueueDebugLogLine(false,_T("UploadSpeedSense: Up!   Ping cur %3i ms. Median: %3i ms %2i values. Error: %3I64i Integral: %5I64i New Upload %6i + %4I64i = %6i"), raw_ping, pingAverage, pingDelays.GetCount(), error, integral, upload, ulDelta, newUpload);

                                upload = newUpload;
                            }
						}
					}
					prefsLocker.Lock();
                    //if (m_NeedMoreSlots && upload > curUpload) {
                    //    upload = curUpload;
                    //}

					if (upload < minUpload) {
						upload = minUpload;
						//acceptNewClient = true;
					}
					if (upload > maxUpload) {
						upload = maxUpload;
                    }
					prefsLocker.Unlock();
					SetUpload(upload);
                    if(m_enabled == false) {
						enabled = false;
                    }
				}
			}
		}
	}

	// Signal that we have ended.
	threadEndedEvent->SetEvent();

	return 0;
}

uint32 LastCommonRouteFinder::Median(UInt32Clist& list) {
    uint32 size = list.GetCount();

    if(size == 1) {
        return list.GetHead();
    } else if(size == 2) {
        return max(list.GetHead(), list.GetTail());
    } else if(size > 2) {
        uint32 maxVal = 0;

        for(POSITION pos = list.GetHeadPosition(); pos; list.GetNext(pos)) {
            maxVal = max(maxVal, list.GetAt(pos));
        }

        return maxVal;
    } else {
        // Undefined! Shouldn't be called with no elements in list.
        return 0;
    }
}

//uint32 LastCommonRouteFinder::Median(UInt32Clist& list) {
//    uint32 size = list.GetCount();
//
//    if(size == 1) {
//        return list.GetHead();
//    } else if(size == 2) {
//        return (list.GetHead()+list.GetTail())/2;
//    } else if(size > 2) {
//        // if more than 2 elements, we need to sort them to find the middle.
//        uint32* arr = new uint32[size];
//
//        uint32 counter = 0;
//        for(POSITION pos = list.GetHeadPosition(); pos; list.GetNext(pos)) {
//            arr[counter] = list.GetAt(pos);
//            counter++;
//        }
//
//        std::sort(arr, arr+size);
//
//        double returnVal;
//
//        if(size%2)
//            returnVal = arr[size/2];
//        else
//            returnVal = (arr[size/2-1] + arr[size/2])/2;
//
//        delete[] arr;
//
//        return (UINT)returnVal;
//    } else {
//        // Undefined! Shouldn't be called with no elements in list.
//        return 0;
//    }
//}