search.cpp

电驴的MAC源代码

//
// This file is part of the aMule Project.
//
// Copyright (c) 2004-2008 Angel Vidal (Kry) ( [e-mail] )
// Copyright (c) 2004-2008 aMule Team ( [e-mail] / http://www.amule.org )
// Copyright (c) 2003 Barry Dunne (http://www.emule-project.net)
//
// Any parts of this program derived from the xMule, lMule or eMule project,
// or contributed by third-party developers are copyrighted by their
// respective authors.
//
// 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., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
//

// Note To Mods //
/*
Please do not change anything here and release it..
There is going to be a new forum created just for the Kademlia side of the client..
If you feel there is an error or a way to improve something, please
post it in the forum first and let us look at it.. If it is a real improvement,
it will be added to the offical client.. Changing something without knowing
what all it does can cause great harm to the network if released in mass form..
Any mod that changes anything within the Kademlia side will not be allowed to advertise
there client on the eMule forum..
*/

#include "Search.h"

#include <protocol/Protocols.h>
#include <protocol/kad/Client2Client/UDP.h>
#include <protocol/kad/Constants.h>
#include <protocol/kad2/Client2Client/UDP.h>
#include <tags/FileTags.h>

#include "Defines.h"
#include "UDPFirewallTester.h"
#include "../routing/RoutingZone.h"
#include "../routing/Contact.h"
#include "../net/KademliaUDPListener.h"
#include "../utils/KadClientSearcher.h"
#include "../../amule.h"
#include "../../SharedFileList.h"
#include "../../DownloadQueue.h"
#include "../../PartFile.h"
#include "../../SearchList.h"
#include "../../MemFile.h"
#include "../../ClientList.h"
#include "../../updownclient.h"
#include "../../Logger.h"
#include "../../Preferences.h"
#include "../../GuiEvents.h"

////////////////////////////////////////
using namespace Kademlia;
////////////////////////////////////////

CSearch::CSearch()
{
	m_created = time(NULL);
	m_type = (uint32_t)-1;
	m_answers = 0;
	m_totalRequestAnswers = 0;
	m_searchID = (uint32_t)-1;
	m_stopping = false;
	m_totalLoad = 0;
	m_totalLoadResponses = 0;
	m_lastResponse = m_created;
	m_searchTermsData = NULL;
	m_searchTermsDataSize = 0;
	m_nodeSpecialSearchRequester = NULL;
}

CSearch::~CSearch()
{
	if (m_nodeSpecialSearchRequester != NULL) {
		// inform requester that our search failed
		m_nodeSpecialSearchRequester->KadSearchIPByNodeIDResult(KCSR_NOTFOUND, 0, 0);
	}

	// Check if a source search is currently being done.
	CPartFile* temp = theApp->downloadqueue->GetFileByKadFileSearchID(GetSearchID());

	// Reset the searchID if a source search is currently being done.
	if (temp) {
		temp->SetKadFileSearchID(0);
	}

	// Decrease the use count for any contacts that are in our contact list.
	for (ContactMap::iterator it = m_inUse.begin(); it != m_inUse.end(); ++it) {
		it->second->DecUse();
	}

	// Delete any temp contacts...
	for (ContactList::const_iterator it = m_delete.begin(); it != m_delete.end(); ++it) {
		delete *it;
	}

	// Check if this search was containing an overload node and adjust time of next time we use that node.
	if (CKademlia::IsRunning() && GetNodeLoad() > 20) {
		switch(GetSearchTypes()) {
			case CSearch::STOREKEYWORD:
				Kademlia::CKademlia::GetIndexed()->AddLoad(GetTarget(), ((uint32_t)(DAY2S(7)*((double)GetNodeLoad()/100.0))+(uint32_t)time(NULL)));
				break;
		}
	}

	if (m_searchTermsData) {
		delete [] m_searchTermsData;
	}

	switch (m_type) {
		case KEYWORD:
			Notify_KadSearchEnd(m_searchID);
			break;
	}
}

void CSearch::Go()
{
	// Start with a lot of possible contacts, this is a fallback in case search stalls due to dead contacts
	if (m_possible.empty()) {
		CUInt128 distance(CKademlia::GetPrefs()->GetKadID() ^ m_target);
		CKademlia::GetRoutingZone()->GetClosestTo(3, m_target, distance, 50, &m_possible, true, true);
	}

	if (!m_possible.empty()) {
		//Lets keep our contact list entries in mind to dec the inUse flag.
		for (ContactMap::iterator it = m_possible.begin(); it != m_possible.end(); ++it) {
			m_inUse[it->first] = it->second;
		}

		wxASSERT(m_possible.size() == m_inUse.size());

		// Take top ALPHA_QUERY to start search with.
		int count = m_type == NODE ? 1 : min(ALPHA_QUERY, (int)m_possible.size());

		// Send initial packets to start the search.
		ContactMap::iterator it = m_possible.begin();
		for (int i = 0; i < count; i++) {
			CContact *c = it->second;
			// Move to tried
			m_tried[it->first] = c;
			// Send the KadID so other side can check if I think it has the right KadID.
			// Send request
			SendFindValue(c);
			++it;
		}
	}
}

//If we allow about a 15 sec delay before deleting, we won't miss a lot of delayed returning packets.
void CSearch::PrepareToStop() throw()
{
	// Check if already stopping.
	if (m_stopping) {
		return;
	}

	// Set basetime by search type.
	uint32_t baseTime = 0;
	switch (m_type) {
		case NODE:
		case NODECOMPLETE:
		case NODESPECIAL:
		case NODEFWCHECKUDP:
			baseTime = SEARCHNODE_LIFETIME;
			break;
		case FILE:
			baseTime = SEARCHFILE_LIFETIME;
			break;
		case KEYWORD:
			baseTime = SEARCHKEYWORD_LIFETIME;
			break;
		case NOTES:
			baseTime = SEARCHNOTES_LIFETIME;
			break;
		case STOREFILE:
			baseTime = SEARCHSTOREFILE_LIFETIME;
			break;
		case STOREKEYWORD:
			baseTime = SEARCHSTOREKEYWORD_LIFETIME;
			break;
		case STORENOTES:
			baseTime = SEARCHSTORENOTES_LIFETIME;
			break;
		case FINDBUDDY:
			baseTime = SEARCHFINDBUDDY_LIFETIME;
			break;
		case FINDSOURCE:
			baseTime = SEARCHFINDSOURCE_LIFETIME;
			break;
		default:
			baseTime = SEARCH_LIFETIME;
	}

	// Adjust created time so that search will delete within 15 seconds.
	// This gives late results time to be processed.
	m_created = time(NULL) - baseTime + SEC(15);
	m_stopping = true;	
}

void CSearch::JumpStart()
{
	// If we ran out of contacts, stop search.
	if (m_possible.empty()) {
		PrepareToStop();
		return;
	}

	// If we had a response within the last 3 seconds, no need to jumpstart the search.
	if ((time_t)(m_lastResponse + SEC(3)) > time(NULL)) {
		return;
	}

	// Search for contacts that can be used to jumpstart a stalled search.
	while (!m_possible.empty()) {
		// Get a contact closest to our target.
		CContact *c = m_possible.begin()->second;
	
		// Have we already tried to contact this node.
		if (m_tried.count(m_possible.begin()->first) > 0) {
			// Did we get a response from this node, if so, try to store or get info.
			if (m_responded.count(m_possible.begin()->first) > 0) {
				StorePacket();
			}
			// Remove from possible list.
			m_possible.erase(m_possible.begin());
		} else {
			// Add to tried list.
			m_tried[m_possible.begin()->first] = c;
			// Send the KadID so other side can check if I think it has the right KadID.
			// Send request
			SendFindValue(c);
			break;
		}
	}
	
}

void CSearch::ProcessResponse(uint32_t fromIP, uint16_t fromPort, ContactList *results)
{
	AddDebugLogLineM(false, logKadSearch, wxT("Processing search response from ") + Uint32_16toStringIP_Port(wxUINT32_SWAP_ALWAYS(fromIP), fromPort));

	if (results) {
		m_lastResponse = time(NULL);
	}

	ContactList::iterator response;
	// Remember the contacts to be deleted when finished
	for (response = results->begin(); response != results->end(); ++response) {
		m_delete.push_back(*response);
	}

	if (m_type == NODEFWCHECKUDP) {
		m_answers++;
		delete results;
		return;
	}

	// Not interested in responses for FIND_NODE, will be added to contacts by udp listener
	if (m_type == NODE) {
		AddDebugLogLineM(false, logKadSearch, wxT("Node type search result, discarding."));
		// Note that we got an answer.
		m_answers++;
		// We clear the possible list to force the search to stop.
		m_possible.clear();
		delete results;
		return;
	}

	// Find contact that is responding.
	for (ContactMap::const_iterator tried = m_tried.begin(); tried != m_tried.end(); ++tried) {
		CUInt128 fromDistance(tried->first);
		CContact *from = tried->second;

		if ((from->GetIPAddress() == fromIP) && (from->GetUDPPort() == fromPort)) {
			// Add to list of people who responded
			m_responded[fromDistance] = from;

			std::map<uint32_t, uint32_t> mapReceivedIPs;
			// Loop through their responses
			for (response = results->begin(); response != results->end(); ++response) {
				CContact *c = *response;
				CUInt128 distance(c->GetClientID() ^ m_target);

				// Ignore this contact if already known or tried it.
				if (m_possible.count(distance) > 0) {
					// AddDebugLogLineM(false, logKadSearch, wxT("Search result from already known client: ignore"));
					continue;
				}
				if (m_tried.count(distance) > 0) {
					// AddDebugLogLineM(false, logKadSearch, wxT("Search result from already tried client: ignore"));
					continue;
				}

				// We only accept unique IPs in the answer, having multiple IDs pointing to one IP in the routing tables
				// is no longer allowed since eMule0.49a, aMule-2.2.1 anyway
				if (mapReceivedIPs.count(c->GetIPAddress()) > 0) {
					AddDebugLogLineM(false, logKadSearch, wxT("Multiple KadIDs pointing to same IP(") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(c->GetIPAddress())) + wxT(") in Kad(2)Res answer - ignored, sent by ") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(from->GetIPAddress())));
					continue;
				} else {
					mapReceivedIPs[c->GetIPAddress()] = 1;
				}

				// Add to possible
				m_possible[distance] = c;

				// Verify if the result is closer to the target than the one we just checked.
				if (distance < fromDistance) {
					// The top ALPHA_QUERY of results are used to determin if we send a request.
					bool top = false;
					if (m_best.size() < ALPHA_QUERY) {
						top = true;
						m_best[distance] = c;
					} else {
						ContactMap::iterator it = m_best.end();
						--it;
						if (distance < it->first) {
							// Prevent having more than ALPHA_QUERY within the Best list.
							m_best.erase(it);
							m_best[distance] = c;
							top = true;
						}
					}

					if (top) {
						// We determined this contact is a candidate for a request.
						// Add to tried
						m_tried[distance] = c;
						// Send the KadID so other side can check if I think it has the right KadID.
						// Send request
						SendFindValue(c);
					}
				}
			}

			// Complete node search, just increment the counter.
			if (m_type == NODECOMPLETE || m_type == NODESPECIAL) {
				AddDebugLogLineM(false, logKadSearch, wxString(wxT("Search result type: Node")) + (m_type == NODECOMPLETE ? wxT("Complete") : wxT("Special")));
				m_answers++;
			}
			break;
		}
	}
	delete results;
}

void CSearch::StorePacket()
{
	wxASSERT(!m_possible.empty());

	// This method is currently only called by jumpstart so only use best possible.
	ContactMap::const_iterator possible = m_possible.begin();
	CUInt128 fromDistance(possible->first);
	CContact *from = possible->second;

	// Make sure this is a valid node to store.
	if(thePrefs::FilterLanIPs() && fromDistance.Get32BitChunk(0) > SEARCHTOLERANCE) {
		AddDebugLogLineM(false, logKadSearch, wxT("Not stored: filtered lan ip"));
		return;
	}

	// What kind of search are we doing?
	switch (m_type) {
		case FILE: {
			AddDebugLogLineM(false, logKadSearch, wxT("Search request type: File"));
			CMemFile searchTerms;
			searchTerms.WriteUInt128(m_target);
			if (from->GetVersion() >= 3) {
				// Find file we are storing info about.
				uint8_t fileid[16];
				m_target.ToByteArray(fileid);
				CKnownFile *file = theApp->downloadqueue->GetFileByID(CMD4Hash(fileid));
				if (file) {
					// Start position range (0x0 to 0x7FFF)
					searchTerms.WriteUInt16(0);
					searchTerms.WriteUInt64(file->GetFileSize());
					DebugSend(Kad2SearchSourceReq, from->GetIPAddress(), from->GetUDPPort());
					if (from->GetVersion() >= 6) {
						CUInt128 clientID = from->GetClientID();
						CKademlia::GetUDPListener()->SendPacket(searchTerms, KADEMLIA2_SEARCH_SOURCE_REQ, from->GetIPAddress(), from->GetUDPPort(), from->GetUDPKey(), &clientID);
					} else {
						CKademlia::GetUDPListener()->SendPacket(searchTerms, KADEMLIA2_SEARCH_SOURCE_REQ, from->GetIPAddress(), from->GetUDPPort(), 0, NULL);
						wxASSERT(from->GetUDPKey() == CKadUDPKey(0));
					}
				} else {
					PrepareToStop();
					break;
				}
			} else {
				searchTerms.WriteUInt8(1);
				DebugSendF(wxT("KadSearchReq(File)"), from->GetIPAddress(), from->GetUDPPort());
				CKademlia::GetUDPListener()->SendPacket(searchTerms, KADEMLIA_SEARCH_REQ, from->GetIPAddress(), from->GetUDPPort(), 0, NULL);
			}
			m_totalRequestAnswers++;
			break;
		}
		case KEYWORD: {
			AddDebugLogLineM(false, logKadSearch, wxT("Search request type: Keyword"));
			CMemFile searchTerms;
			searchTerms.WriteUInt128(m_target);
			if (from->GetVersion() >= 3) {
				if (m_searchTermsDataSize == 0) {
					// Start position range (0x0 to 0x7FFF)