routingzone.cpp

电驴的MAC源代码

void CRoutingZone::WriteFile()
{
	// don't overwrite a bootstrap nodes.dat with an empty one, if we didn't finish probing
	if (!CKademlia::s_bootstrapList.empty() && GetNumContacts() == 0) {
		AddDebugLogLineM(false, logKadRouting, wxT("Skipped storing nodes.dat, because we have an unfinished bootstrap of the nodes.dat version and no contacts in our routing table"));
		return;
	}

	// The bootstrap method gets a very nice sample of contacts to save.
	ContactList contacts;
	GetBootstrapContacts(&contacts, 200);
	ContactList::size_type numContacts = contacts.size();
	numContacts = std::min<ContactList::size_type>(numContacts, CONTACT_FILE_LIMIT); // safety precaution, should not be above
	if (numContacts < 25) {
		AddLogLineM(false, wxString::Format(wxPLURAL("Only %d Kad contact available, nodes.dat not written", "Only %d Kad contacts available, nodes.dat not written", numContacts), numContacts));
		return;
	}
	try {
		unsigned int count = 0;
		CFile file;
		if (file.Open(m_filename, CFile::write)) {
			// Start file with 0 to prevent older clients from reading it.
			file.WriteUInt32(0);
			// Now tag it with a version which happens to be 2.
			file.WriteUInt32(2);
			file.WriteUInt32(numContacts);
			for (ContactList::const_iterator it = contacts.begin(); it != contacts.end(); ++it) {
				CContact *c = *it;
				count++;
				if (count > CONTACT_FILE_LIMIT) {
					// This should never happen
					wxFAIL;
					break;
				}
				file.WriteUInt128(c->GetClientID());
				file.WriteUInt32(c->GetIPAddress());
				file.WriteUInt16(c->GetUDPPort());
				file.WriteUInt16(c->GetTCPPort());
				file.WriteUInt8(c->GetVersion());
				c->GetUDPKey().StoreToFile(file);
				file.WriteUInt8(c->IsIPVerified() ? 1 : 0);
			}
		}
		AddLogLineM(false, wxString::Format(wxPLURAL("Wrote %d Kad contact", "Wrote %d Kad contacts", count), count));
	} catch (const CIOFailureException& e) {
		AddDebugLogLineM(true, logKadRouting, wxT("IO failure in CRoutingZone::writeFile: ") + e.what());
	}
}

bool CRoutingZone::CanSplit() const throw()
{
	// Max levels allowed.
	if (m_level >= 127) {
		return false;
	}

	// Check if this zone is allowed to split.
	return ((m_zoneIndex < KK || m_level < KBASE) && m_bin->GetSize() == K);
}

// Returns true if a contact was added or updated, false if the routing table was not touched.
bool CRoutingZone::Add(const CUInt128& id, uint32_t ip, uint16_t port, uint16_t tport, uint8_t version, const CKadUDPKey& key, bool& ipVerified, bool update, bool fromNodesDat, bool fromHello)
{
	if (IsGoodIPPort(wxUINT32_SWAP_ALWAYS(ip), port)) {
		if (!theApp->ipfilter->IsFiltered(wxUINT32_SWAP_ALWAYS(ip)) && !(port == 53 && version <= 5) /*No DNS Port without encryption*/) {
			return AddUnfiltered(id, ip, port, tport, version, key, ipVerified, update, fromNodesDat, fromHello);
		}
	}
	return false;
}

// Returns true if a contact was added or updated, false if the routing table was not touched.
bool CRoutingZone::AddUnfiltered(const CUInt128& id, uint32_t ip, uint16_t port, uint16_t tport, uint8_t version, const CKadUDPKey& key, bool& ipVerified, bool update, bool fromNodesDat, bool fromHello)
{
	if (id != me) {
		CContact *contact = new CContact(id, ip, port, tport, version, key, ipVerified);
		if (fromNodesDat) {
			contact->CheckIfKad2();	// do not test nodes which we loaded from our nodes.dat for Kad2 again
		} else if (fromHello) {
			contact->SetReceivedHelloPacket();
		}
		if (Add(contact, update, ipVerified)) {
			wxASSERT(!update);
			return true;
		} else {
			delete contact;
			return update;
		}
	}
	return false;
}

bool CRoutingZone::Add(CContact *contact, bool& update, bool& outIpVerified)
{
	// If we're not a leaf, call add on the correct branch.
	if (!IsLeaf()) {
		return m_subZones[contact->GetDistance().GetBitNumber(m_level)]->Add(contact, update, outIpVerified);
	} else {
		// Do we already have a contact with this KadID?
		CContact *contactUpdate = m_bin->GetContact(contact->GetClientID());
		if (contactUpdate) {
			if (update) {
				if (contactUpdate->GetUDPKey().GetKeyValue(theApp->GetPublicIP(false)) != 0 && contactUpdate->GetUDPKey().GetKeyValue(theApp->GetPublicIP(false)) != contact->GetUDPKey().GetKeyValue(theApp->GetPublicIP(false))) {
					// if our existing contact has a UDPSender-Key (which should be the case for all > = 0.49a clients)
					// except if our IP has changed recently, we demand that the key is the same as the key we received
					// from the packet which wants to update this contact in order to make sure this is not a try to
					// hijack this entry
					AddDebugLogLineM(false, logKadRouting, wxT("Sender (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress())) + wxT(") tried to update contact entry but failed to provide the proper sender key (Sent Empty: ") + (contact->GetUDPKey().GetKeyValue(theApp->GetPublicIP(false)) == 0 ? wxT("Yes") : wxT("No")) + wxT(") for the entry (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contactUpdate->GetIPAddress())) + wxT(") - denying update"));
					update = false;
				} else if (contactUpdate->GetVersion() >= 1 && contactUpdate->GetVersion() < 6 && contactUpdate->GetReceivedHelloPacket()) {
					// legacy kad2 contacts are allowed only to update their RefreshTimer to avoid having them hijacked/corrupted by an attacker
					// (kad1 contacts do not have this restriction as they might turn out as kad2 later on)
					// only exception is if we didn't received a HELLO packet from this client yet
					if (contactUpdate->GetIPAddress() == contact->GetIPAddress() && contactUpdate->GetTCPPort() == contact->GetTCPPort() && contactUpdate->GetVersion() == contact->GetVersion() && contactUpdate->GetUDPPort() == contact->GetUDPPort()) {
						wxASSERT(!contact->IsIPVerified());	// legacy kad2 nodes should be unable to verify their IP on a HELLO
						outIpVerified = contactUpdate->IsIPVerified();
						m_bin->SetAlive(contactUpdate);
						AddDebugLogLineM(false, logKadRouting, wxString::Format(wxT("Updated kad contact refreshtimer only for legacy kad2 contact (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contactUpdate->GetIPAddress())) + wxT(", %u)"), contactUpdate->GetVersion()));
					} else {
						AddDebugLogLineM(false, logKadRouting, wxString::Format(wxT("Rejected value update for legacy kad2 contact (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contactUpdate->GetIPAddress())) + wxT(" -> ") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress())) + wxT(", %u -> %u)"), contactUpdate->GetVersion(), contact->GetVersion()));
						update = false;
					}
				} else {
#ifdef __DEBUG__
					// just for outlining, get removed anyway
					//debug logging stuff - remove later
					if (contact->GetUDPKey().GetKeyValue(theApp->GetPublicIP(false)) == 0) {
						if (contact->GetVersion() >= 6 && contact->GetType() < 2) {
							AddDebugLogLineM(false, logKadRouting, wxT("Updating > 0.49a + type < 2 contact without valid key stored ") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress())));
						}
					} else {
						AddDebugLogLineM(false, logKadRouting, wxT("Updating contact, passed key check ") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress())));
					}

					if (contactUpdate->GetVersion() >= 1 && contactUpdate->GetVersion() < 6) {
						wxASSERT(!contactUpdate->GetReceivedHelloPacket());
						AddDebugLogLineM(false, logKadRouting, wxString::Format(wxT("Accepted update for legacy kad2 contact, because of first HELLO (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contactUpdate->GetIPAddress())) + wxT(" -> ") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress())) + wxT(", %u -> %u)"), contactUpdate->GetVersion(), contact->GetVersion()));
					}
#endif
					// All other nodes (Kad1, Kad2 > 0.49a with UDPKey checked or not set, first hello updates) are allowed to do full updates
					// do not let Kad1 responses overwrite Kad2 ones
					if (m_bin->ChangeContactIPAddress(contactUpdate, contact->GetIPAddress()) && contact->GetVersion() >= contactUpdate->GetVersion()) {
						contactUpdate->SetUDPPort(contact->GetUDPPort());
						contactUpdate->SetTCPPort(contact->GetTCPPort());
						contactUpdate->SetVersion(contact->GetVersion());
						contactUpdate->SetUDPKey(contact->GetUDPKey());
						// don't unset the verified flag (will clear itself on ipchanges)
						if (!contactUpdate->IsIPVerified()) {
							contactUpdate->SetIPVerified(contact->IsIPVerified());
						}
						outIpVerified = contactUpdate->IsIPVerified();
						m_bin->SetAlive(contactUpdate);
						if (contact->GetReceivedHelloPacket()) {
							contactUpdate->SetReceivedHelloPacket();
						}
					} else {
						update = false;
					}
				}
			}
			return false;
		} else if (m_bin->GetRemaining()) {
			update = false;
			// This bin is not full, so add the new contact
			return m_bin->AddContact(contact);
		} else if (CanSplit()) {
			// This bin was full and split, call add on the correct branch.
			Split();
			return m_subZones[contact->GetDistance().GetBitNumber(m_level)]->Add(contact, update, outIpVerified);
		} else {
			update = false;
			return false;
		}
	}
}

CContact *CRoutingZone::GetContact(const CUInt128& id) const throw()
{
	if (IsLeaf()) {
		return m_bin->GetContact(id);
	} else {
		CUInt128 distance = CKademlia::GetPrefs()->GetKadID();
		distance ^= id;
		return m_subZones[distance.GetBitNumber(m_level)]->GetContact(id);
	}
}

CContact *CRoutingZone::GetContact(uint32_t ip, uint16_t port, bool tcpPort) const throw()
{
	if (IsLeaf()) {
		return m_bin->GetContact(ip, port, tcpPort);
	} else {
		CContact *contact = m_subZones[0]->GetContact(ip, port, tcpPort);
		return (contact != NULL) ? contact : m_subZones[1]->GetContact(ip, port, tcpPort);
	}
}

CContact *CRoutingZone::GetRandomContact(uint32_t maxType, uint32_t minKadVersion) const throw()
{
	if (IsLeaf()) {
		return m_bin->GetRandomContact(maxType, minKadVersion);
	} else {
		unsigned zone = GetRandomUint16() & 1 /* GetRandomUint16() % 2 */;
		CContact *contact = m_subZones[zone]->GetRandomContact(maxType, minKadVersion);
		return (contact != NULL) ? contact : m_subZones[1 - zone]->GetRandomContact(maxType, minKadVersion);
	}
}

void CRoutingZone::GetClosestTo(uint32_t maxType, const CUInt128& target, const CUInt128& distance, uint32_t maxRequired, ContactMap *result, bool emptyFirst, bool inUse) const
{
	// If leaf zone, do it here
	if (IsLeaf()) {
		m_bin->GetClosestTo(maxType, target, maxRequired, result, emptyFirst, inUse);
		return;
	}

	// otherwise, recurse in the closer-to-the-target subzone first
	int closer = distance.GetBitNumber(m_level);
	m_subZones[closer]->GetClosestTo(maxType, target, distance, maxRequired, result, emptyFirst, inUse);

	// if still not enough tokens found, recurse in the other subzone too
	if (result->size() < maxRequired) {
		m_subZones[1-closer]->GetClosestTo(maxType, target, distance, maxRequired, result, false, inUse);
	}
}

void CRoutingZone::GetAllEntries(ContactList *result, bool emptyFirst) const
{
	if (IsLeaf()) {
		m_bin->GetEntries(result, emptyFirst);
	} else {
		m_subZones[0]->GetAllEntries(result, emptyFirst);
		m_subZones[1]->GetAllEntries(result, false);			
	}
}

void CRoutingZone::TopDepth(int depth, ContactList *result, bool emptyFirst) const
{
	if (IsLeaf()) {
		m_bin->GetEntries(result, emptyFirst);
	} else if (depth <= 0) {
		RandomBin(result, emptyFirst);
	} else {
		m_subZones[0]->TopDepth(depth-1, result, emptyFirst);
		m_subZones[1]->TopDepth(depth-1, result, false);
	}
}

void CRoutingZone::RandomBin(ContactList *result, bool emptyFirst) const
{
	if (IsLeaf()) {
		m_bin->GetEntries(result, emptyFirst);
	} else {
		m_subZones[rand()&1]->RandomBin(result, emptyFirst);
	}
}

uint32_t CRoutingZone::GetMaxDepth() const throw()
{
	if (IsLeaf()) {
		return 0;
	}
	return 1 + std::max(m_subZones[0]->GetMaxDepth(), m_subZones[1]->GetMaxDepth());
}

void CRoutingZone::Split()
{
	StopTimer();
		
	m_subZones[0] = GenSubZone(0);
	m_subZones[1] = GenSubZone(1);

	ContactList entries;
	m_bin->GetEntries(&entries);
	m_bin->m_dontDeleteContacts = true;
	delete m_bin;
	m_bin = NULL;

	for (ContactList::const_iterator it = entries.begin(); it != entries.end(); ++it) {
		if (!m_subZones[(*it)->GetDistance().GetBitNumber(m_level)]->m_bin->AddContact(*it)) {