src/core/thread/router_table.cpp - third_party/openthread - Git at Google

 /*
  *  Copyright (c) 2018, The OpenThread Authors.
  *  All rights reserved.
  *
  *  Redistribution and use in source and binary forms, with or without
  *  modification, are permitted provided that the following conditions are met:
  *  1. Redistributions of source code must retain the above copyright
  *     notice, this list of conditions and the following disclaimer.
  *  2. Redistributions in binary form must reproduce the above copyright
  *     notice, this list of conditions and the following disclaimer in the
  *     documentation and/or other materials provided with the distribution.
  *  3. Neither the name of the copyright holder nor the
  *     names of its contributors may be used to endorse or promote products
  *     derived from this software without specific prior written permission.
  *
  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  *  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  *  ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  *  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  *  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  *  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  *  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  *  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  *  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  *  POSSIBILITY OF SUCH DAMAGE.
  */

 #include "router_table.hpp"

 #if OPENTHREAD_FTD

 #include "common/code_utils.hpp"
 #include "common/instance.hpp"
 #include "common/locator-getters.hpp"
 #include "common/logging.hpp"
 #include "common/timer.hpp"
 #include "thread/mle.hpp"
 #include "thread/mle_router.hpp"
 #include "thread/network_data_leader.hpp"
 #include "thread/thread_netif.hpp"

 namespace ot {

 RouterTable::Iterator::Iterator(Instance &aInstance)
     : InstanceLocator(aInstance)
     , mRouter(NULL)
 {
     Reset();
 }

 void RouterTable::Iterator::Reset(void)
 {
     mRouter = Get<RouterTable>().GetFirstEntry();
 }

 void RouterTable::Iterator::Advance(void)
 {
     mRouter = Get<RouterTable>().GetNextEntry(mRouter);
 }

 RouterTable::RouterTable(Instance &aInstance)
     : InstanceLocator(aInstance)
     , mRouterIdSequenceLastUpdated(0)
     , mRouterIdSequence(Random::NonCrypto::GetUint8())
     , mActiveRouterCount(0)
 {
     Clear();
 }

 const Router *RouterTable::GetFirstEntry(void) const
 {
     const Router *router = &mRouters[0];
     VerifyOrExit(router->GetRloc16() != 0xffff, router = NULL);

 exit:
     return router;
 }

 const Router *RouterTable::GetNextEntry(const Router *aRouter) const
 {
     VerifyOrExit(aRouter != NULL);
     aRouter++;
     VerifyOrExit(aRouter < &mRouters[Mle::kMaxRouters], aRouter = NULL);
     VerifyOrExit(aRouter->GetRloc16() != 0xffff, aRouter = NULL);

 exit:
     return aRouter;
 }

 void RouterTable::Clear(void)
 {
     mAllocatedRouterIds.Clear();
     memset(mRouterIdReuseDelay, 0, sizeof(mRouterIdReuseDelay));
     UpdateAllocation();
 }

 void RouterTable::ClearNeighbors(void)
 {
     for (uint8_t index = 0; index < Mle::kMaxRouters; index++)
     {
         Router &router = mRouters[index];

         if (router.IsStateValid())
         {
             Get<Mle::MleRouter>().Signal(OT_NEIGHBOR_TABLE_EVENT_ROUTER_REMOVED, router);
         }

         router.SetState(Neighbor::kStateInvalid);
     }
 }

 bool RouterTable::IsAllocated(uint8_t aRouterId) const
 {
     return mAllocatedRouterIds.Contains(aRouterId);
 }

 void RouterTable::UpdateAllocation(void)
 {
     uint8_t indexMap[Mle::kMaxRouterId + 1];

     mActiveRouterCount = 0;

     // build index map
     for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
     {
         if (IsAllocated(routerId) && mActiveRouterCount < Mle::kMaxRouters)
         {
             indexMap[routerId] = mActiveRouterCount++;
         }
         else
         {
             indexMap[routerId] = Mle::kInvalidRouterId;
         }
     }

     // shift entries forward
     for (int index = Mle::kMaxRouters - 2; index >= 0; index--)
     {
         uint8_t routerId = mRouters[index].GetRouterId();
         uint8_t newIndex;

         if (routerId > Mle::kMaxRouterId || indexMap[routerId] == Mle::kInvalidRouterId)
         {
             continue;
         }

         newIndex = indexMap[routerId];

         if (newIndex > index)
         {
             mRouters[newIndex] = mRouters[index];
         }
     }

     // shift entries backward
     for (uint8_t index = 1; index < Mle::kMaxRouters; index++)
     {
         uint8_t routerId = mRouters[index].GetRouterId();
         uint8_t newIndex;

         if (routerId > Mle::kMaxRouterId || indexMap[routerId] == Mle::kInvalidRouterId)
         {
             continue;
         }

         newIndex = indexMap[routerId];

         if (newIndex < index)
         {
             mRouters[newIndex] = mRouters[index];
         }
     }

     // fix replaced entries
     for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
     {
         uint8_t index = indexMap[routerId];

         if (index != Mle::kInvalidRouterId)
         {
             Router &router = mRouters[index];

             if (router.GetRouterId() != routerId)
             {
                 router.Clear();
                 router.SetRloc16(Mle::Mle::Rloc16FromRouterId(routerId));
                 router.SetNextHop(Mle::kInvalidRouterId);
             }
         }
     }

     // clear unused entries
     for (uint8_t index = mActiveRouterCount; index < Mle::kMaxRouters; index++)
     {
         Router &router = mRouters[index];
         router.Clear();
         router.SetRloc16(0xffff);
     }
 }

 Router *RouterTable::Allocate(void)
 {
     Router *rval         = NULL;
     uint8_t numAvailable = 0;
     uint8_t freeBit;

     // count available router ids
     for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
     {
         if (!IsAllocated(routerId) && mRouterIdReuseDelay[routerId] == 0)
         {
             numAvailable++;
         }
     }

     VerifyOrExit(mActiveRouterCount < Mle::kMaxRouters && numAvailable > 0);

     // choose available router id at random
     freeBit = Random::NonCrypto::GetUint8InRange(0, numAvailable);

     // allocate router
     for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
     {
         if (IsAllocated(routerId) || mRouterIdReuseDelay[routerId] > 0)
         {
             continue;
         }

         if (freeBit == 0)
         {
             rval = Allocate(routerId);
             assert(rval != NULL);
             ExitNow();
         }

         freeBit--;
     }

 exit:
     return rval;
 }

 Router *RouterTable::Allocate(uint8_t aRouterId)
 {
     Router *rval = NULL;

     VerifyOrExit(aRouterId <= Mle::kMaxRouterId && mActiveRouterCount < Mle::kMaxRouters && !IsAllocated(aRouterId) &&
                  mRouterIdReuseDelay[aRouterId] == 0);

     mAllocatedRouterIds.Add(aRouterId);
     UpdateAllocation();

     rval = GetRouter(aRouterId);
     rval->SetLastHeard(TimerMilli::GetNow());

     mRouterIdSequence++;
     mRouterIdSequenceLastUpdated = TimerMilli::GetNow();
     Get<Mle::MleRouter>().ResetAdvertiseInterval();

     otLogNoteMle("Allocate router id %d", aRouterId);

 exit:
     return rval;
 }

 otError RouterTable::Release(uint8_t aRouterId)
 {
     otError  error  = OT_ERROR_NONE;
     uint16_t rloc16 = Mle::Mle::Rloc16FromRouterId(aRouterId);

     assert(aRouterId <= Mle::kMaxRouterId);

     VerifyOrExit(Get<Mle::MleRouter>().GetRole() == OT_DEVICE_ROLE_LEADER, error = OT_ERROR_INVALID_STATE);
     VerifyOrExit(IsAllocated(aRouterId), error = OT_ERROR_NOT_FOUND);

     mAllocatedRouterIds.Remove(aRouterId);
     UpdateAllocation();

     mRouterIdReuseDelay[aRouterId] = Mle::kRouterIdReuseDelay;

     for (Router *router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
     {
         if (router->GetNextHop() == rloc16)
         {
             router->SetNextHop(Mle::kInvalidRouterId);
             router->SetCost(0);
         }
     }

     mRouterIdSequence++;
     mRouterIdSequenceLastUpdated = TimerMilli::GetNow();

     Get<AddressResolver>().Remove(aRouterId);
     Get<NetworkData::Leader>().RemoveBorderRouter(rloc16, NetworkData::Leader::kMatchModeRouterId);
     Get<Mle::MleRouter>().ResetAdvertiseInterval();

     otLogNoteMle("Release router id %d", aRouterId);

 exit:
     return error;
 }

 void RouterTable::RemoveNeighbor(Router &aRouter)
 {
     aRouter.SetLinkQualityOut(0);
     aRouter.SetLastHeard(TimerMilli::GetNow());

     for (Router *cur = GetFirstEntry(); cur != NULL; cur = GetNextEntry(cur))
     {
         if (cur->GetNextHop() == aRouter.GetRouterId())
         {
             cur->SetNextHop(Mle::kInvalidRouterId);
             cur->SetCost(0);

             if (GetLinkCost(*cur) >= Mle::kMaxRouteCost)
             {
                 Get<Mle::MleRouter>().ResetAdvertiseInterval();
             }
         }
     }

     if (aRouter.GetNextHop() == Mle::kInvalidRouterId)
     {
         Get<Mle::MleRouter>().ResetAdvertiseInterval();

         // Clear all EID-to-RLOC entries associated with the router.
         Get<AddressResolver>().Remove(aRouter.GetRouterId());
     }
 }

 uint8_t RouterTable::GetActiveLinkCount(void) const
 {
     uint8_t activeLinks = 0;

     for (const Router *router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
     {
         if (router->IsStateValid())
         {
             activeLinks++;
         }
     }

     return activeLinks;
 }

 Router *RouterTable::GetNeighbor(uint16_t aRloc16)
 {
     Router *router = NULL;

     VerifyOrExit(aRloc16 != Get<Mle::MleRouter>().GetRloc16());

     for (router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
     {
         if (router->IsStateValid() && router->GetRloc16() == aRloc16)
         {
             ExitNow();
         }
     }

 exit:
     return router;
 }

 Router *RouterTable::GetNeighbor(const Mac::ExtAddress &aExtAddress)
 {
     Router *router = NULL;

     VerifyOrExit(aExtAddress != Get<Mac::Mac>().GetExtAddress());

     for (router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
     {
         if (router->IsStateValid() && router->GetExtAddress() == aExtAddress)
         {
             ExitNow();
         }
     }

 exit:
     return router;
 }

 const Router *RouterTable::GetRouter(uint8_t aRouterId) const
 {
     const Router *router = NULL;
     uint16_t      rloc16 = Mle::Mle::Rloc16FromRouterId(aRouterId);

     for (router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
     {
         if (router->GetRloc16() == rloc16)
         {
             break;
         }
     }

     return router;
 }

 Router *RouterTable::GetRouter(const Mac::ExtAddress &aExtAddress)
 {
     Router *router = NULL;

     for (router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
     {
         if (router->GetExtAddress() == aExtAddress)
         {
             break;
         }
     }

     return router;
 }

 otError RouterTable::GetRouterInfo(uint16_t aRouterId, otRouterInfo &aRouterInfo)
 {
     otError error = OT_ERROR_NONE;
     Router *router;
     uint8_t routerId;

     if (aRouterId <= Mle::kMaxRouterId)
     {
         routerId = static_cast<uint8_t>(aRouterId);
     }
     else
     {
         VerifyOrExit(Mle::Mle::IsActiveRouter(aRouterId), error = OT_ERROR_INVALID_ARGS);
         routerId = Mle::Mle::RouterIdFromRloc16(aRouterId);
         VerifyOrExit(routerId <= Mle::kMaxRouterId, error = OT_ERROR_INVALID_ARGS);
     }

     router = GetRouter(routerId);
     VerifyOrExit(router != NULL, error = OT_ERROR_NOT_FOUND);

     memset(&aRouterInfo, 0, sizeof(aRouterInfo));
     aRouterInfo.mRouterId        = routerId;
     aRouterInfo.mRloc16          = Mle::Mle::Rloc16FromRouterId(routerId);
     aRouterInfo.mExtAddress      = router->GetExtAddress();
     aRouterInfo.mAllocated       = true;
     aRouterInfo.mNextHop         = router->GetNextHop();
     aRouterInfo.mLinkEstablished = router->IsStateValid();
     aRouterInfo.mPathCost        = router->GetCost();
     aRouterInfo.mLinkQualityIn   = router->GetLinkInfo().GetLinkQuality();
     aRouterInfo.mLinkQualityOut  = router->GetLinkQualityOut();
     aRouterInfo.mAge             = static_cast<uint8_t>(Time::MsecToSec(TimerMilli::GetNow() - router->GetLastHeard()));

 exit:
     return error;
 }

 Router *RouterTable::GetLeader(void)
 {
     return GetRouter(Get<Mle::MleRouter>().GetLeaderId());
 }

 uint32_t RouterTable::GetLeaderAge(void) const
 {
     return (mActiveRouterCount > 0) ? Time::MsecToSec(TimerMilli::GetNow() - mRouterIdSequenceLastUpdated) : 0xffffffff;
 }

 uint8_t RouterTable::GetNeighborCount(void) const
 {
     uint8_t count = 0;

     for (const Router *router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
     {
         if (router->IsStateValid())
         {
             count++;
         }
     }

     return count;
 }

 uint8_t RouterTable::GetLinkCost(Router &aRouter)
 {
     uint8_t rval = Mle::kMaxRouteCost;

     VerifyOrExit(aRouter.GetRloc16() != Get<Mle::MleRouter>().GetRloc16() && aRouter.IsStateValid());

     rval = aRouter.GetLinkInfo().GetLinkQuality();

     if (rval > aRouter.GetLinkQualityOut())
     {
         rval = aRouter.GetLinkQualityOut();
     }

     rval = Mle::MleRouter::LinkQualityToCost(rval);

 exit:
     return rval;
 }

 void RouterTable::ProcessTlv(const Mle::RouteTlv &aTlv)
 {
     bool allocationChanged = false;

     mRouterIdSequence            = aTlv.GetRouterIdSequence();
     mRouterIdSequenceLastUpdated = TimerMilli::GetNow();

     for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
     {
         if (aTlv.IsRouterIdSet(routerId) == IsAllocated(routerId))
         {
             continue;
         }

         allocationChanged = true;

         if (aTlv.IsRouterIdSet(routerId))
         {
             mAllocatedRouterIds.Add(routerId);
         }
         else
         {
             Router *router = GetRouter(routerId);

             assert(router != NULL);
             router->SetNextHop(Mle::kInvalidRouterId);
             RemoveNeighbor(*router);

             mAllocatedRouterIds.Remove(routerId);
         }
     }

     if (allocationChanged)
     {
         UpdateAllocation();
         Get<Mle::MleRouter>().ResetAdvertiseInterval();
     }
 }

 void RouterTable::ProcessTlv(const ThreadRouterMaskTlv &aTlv)
 {
     bool allocationChanged = false;

     mRouterIdSequence            = aTlv.GetIdSequence();
     mRouterIdSequenceLastUpdated = TimerMilli::GetNow();

     for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
     {
         if (aTlv.IsAssignedRouterIdSet(routerId) == IsAllocated(routerId))
         {
             continue;
         }

         allocationChanged = true;

         if (aTlv.IsAssignedRouterIdSet(routerId))
         {
             mAllocatedRouterIds.Add(routerId);
         }
         else
         {
             mAllocatedRouterIds.Remove(routerId);
         }
     }

     if (allocationChanged)
     {
         UpdateAllocation();
         Get<Mle::MleRouter>().ResetAdvertiseInterval();
     }
 }

 void RouterTable::ProcessTimerTick(void)
 {
     Mle::MleRouter &mle = Get<Mle::MleRouter>();

     if (mle.GetRole() == OT_DEVICE_ROLE_LEADER)
     {
         // update router id sequence
         if (GetLeaderAge() >= Mle::kRouterIdSequencePeriod)
         {
             mRouterIdSequence++;
             mRouterIdSequenceLastUpdated = TimerMilli::GetNow();
         }

         for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
         {
             if (mRouterIdReuseDelay[routerId] > 0)
             {
                 mRouterIdReuseDelay[routerId]--;
             }
         }
     }
 }

 } // namespace ot

 #endif // OPENTHREAD_FTD
	/*
	* Copyright (c) 2018, The OpenThread Authors.
	* All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	* 3. Neither the name of the copyright holder nor the
	* names of its contributors may be used to endorse or promote products
	* derived from this software without specific prior written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
	* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
	* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
	* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
	* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
	* POSSIBILITY OF SUCH DAMAGE.
	*/

	#include "router_table.hpp"

	#if OPENTHREAD_FTD

	#include "common/code_utils.hpp"
	#include "common/instance.hpp"
	#include "common/locator-getters.hpp"
	#include "common/logging.hpp"
	#include "common/timer.hpp"
	#include "thread/mle.hpp"
	#include "thread/mle_router.hpp"
	#include "thread/network_data_leader.hpp"
	#include "thread/thread_netif.hpp"

	namespace ot {

	RouterTable::Iterator::Iterator(Instance &aInstance)
	: InstanceLocator(aInstance)
	, mRouter(NULL)
	{
	Reset();
	}

	void RouterTable::Iterator::Reset(void)
	{
	mRouter = Get<RouterTable>().GetFirstEntry();
	}

	void RouterTable::Iterator::Advance(void)
	{
	mRouter = Get<RouterTable>().GetNextEntry(mRouter);
	}

	RouterTable::RouterTable(Instance &aInstance)
	: InstanceLocator(aInstance)
	, mRouterIdSequenceLastUpdated(0)
	, mRouterIdSequence(Random::NonCrypto::GetUint8())
	, mActiveRouterCount(0)
	{
	Clear();
	}

	const Router *RouterTable::GetFirstEntry(void) const
	{
	const Router *router = &mRouters[0];
	VerifyOrExit(router->GetRloc16() != 0xffff, router = NULL);

	exit:
	return router;
	}

	const Router RouterTable::GetNextEntry(const Router aRouter) const
	{
	VerifyOrExit(aRouter != NULL);
	aRouter++;
	VerifyOrExit(aRouter < &mRouters[Mle::kMaxRouters], aRouter = NULL);
	VerifyOrExit(aRouter->GetRloc16() != 0xffff, aRouter = NULL);

	exit:
	return aRouter;
	}

	void RouterTable::Clear(void)
	{
	mAllocatedRouterIds.Clear();
	memset(mRouterIdReuseDelay, 0, sizeof(mRouterIdReuseDelay));
	UpdateAllocation();
	}

	void RouterTable::ClearNeighbors(void)
	{
	for (uint8_t index = 0; index < Mle::kMaxRouters; index++)
	{
	Router &router = mRouters[index];

	if (router.IsStateValid())
	{
	Get<Mle::MleRouter>().Signal(OT_NEIGHBOR_TABLE_EVENT_ROUTER_REMOVED, router);
	}

	router.SetState(Neighbor::kStateInvalid);
	}
	}

	bool RouterTable::IsAllocated(uint8_t aRouterId) const
	{
	return mAllocatedRouterIds.Contains(aRouterId);
	}

	void RouterTable::UpdateAllocation(void)
	{
	uint8_t indexMap[Mle::kMaxRouterId + 1];

	mActiveRouterCount = 0;

	// build index map
	for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
	{
	if (IsAllocated(routerId) && mActiveRouterCount < Mle::kMaxRouters)
	{
	indexMap[routerId] = mActiveRouterCount++;
	}
	else
	{
	indexMap[routerId] = Mle::kInvalidRouterId;
	}
	}

	// shift entries forward
	for (int index = Mle::kMaxRouters - 2; index >= 0; index--)
	{
	uint8_t routerId = mRouters[index].GetRouterId();
	uint8_t newIndex;

	if (routerId > Mle::kMaxRouterId \|\| indexMap[routerId] == Mle::kInvalidRouterId)
	{
	continue;
	}

	newIndex = indexMap[routerId];

	if (newIndex > index)
	{
	mRouters[newIndex] = mRouters[index];
	}
	}

	// shift entries backward
	for (uint8_t index = 1; index < Mle::kMaxRouters; index++)
	{
	uint8_t routerId = mRouters[index].GetRouterId();
	uint8_t newIndex;

	if (routerId > Mle::kMaxRouterId \|\| indexMap[routerId] == Mle::kInvalidRouterId)
	{
	continue;
	}

	newIndex = indexMap[routerId];

	if (newIndex < index)
	{
	mRouters[newIndex] = mRouters[index];
	}
	}

	// fix replaced entries
	for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
	{
	uint8_t index = indexMap[routerId];

	if (index != Mle::kInvalidRouterId)
	{
	Router &router = mRouters[index];

	if (router.GetRouterId() != routerId)
	{
	router.Clear();
	router.SetRloc16(Mle::Mle::Rloc16FromRouterId(routerId));
	router.SetNextHop(Mle::kInvalidRouterId);
	}
	}
	}

	// clear unused entries
	for (uint8_t index = mActiveRouterCount; index < Mle::kMaxRouters; index++)
	{
	Router &router = mRouters[index];
	router.Clear();
	router.SetRloc16(0xffff);
	}
	}

	Router *RouterTable::Allocate(void)
	{
	Router *rval = NULL;
	uint8_t numAvailable = 0;
	uint8_t freeBit;

	// count available router ids
	for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
	{
	if (!IsAllocated(routerId) && mRouterIdReuseDelay[routerId] == 0)
	{
	numAvailable++;
	}
	}

	VerifyOrExit(mActiveRouterCount < Mle::kMaxRouters && numAvailable > 0);

	// choose available router id at random
	freeBit = Random::NonCrypto::GetUint8InRange(0, numAvailable);

	// allocate router
	for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
	{
	if (IsAllocated(routerId) \|\| mRouterIdReuseDelay[routerId] > 0)
	{
	continue;
	}

	if (freeBit == 0)
	{
	rval = Allocate(routerId);
	assert(rval != NULL);
	ExitNow();
	}

	freeBit--;
	}

	exit:
	return rval;
	}

	Router *RouterTable::Allocate(uint8_t aRouterId)
	{
	Router *rval = NULL;

	VerifyOrExit(aRouterId <= Mle::kMaxRouterId && mActiveRouterCount < Mle::kMaxRouters && !IsAllocated(aRouterId) &&
	mRouterIdReuseDelay[aRouterId] == 0);

	mAllocatedRouterIds.Add(aRouterId);
	UpdateAllocation();

	rval = GetRouter(aRouterId);
	rval->SetLastHeard(TimerMilli::GetNow());

	mRouterIdSequence++;
	mRouterIdSequenceLastUpdated = TimerMilli::GetNow();
	Get<Mle::MleRouter>().ResetAdvertiseInterval();

	otLogNoteMle("Allocate router id %d", aRouterId);

	exit:
	return rval;
	}

	otError RouterTable::Release(uint8_t aRouterId)
	{
	otError error = OT_ERROR_NONE;
	uint16_t rloc16 = Mle::Mle::Rloc16FromRouterId(aRouterId);

	assert(aRouterId <= Mle::kMaxRouterId);

	VerifyOrExit(Get<Mle::MleRouter>().GetRole() == OT_DEVICE_ROLE_LEADER, error = OT_ERROR_INVALID_STATE);
	VerifyOrExit(IsAllocated(aRouterId), error = OT_ERROR_NOT_FOUND);

	mAllocatedRouterIds.Remove(aRouterId);
	UpdateAllocation();

	mRouterIdReuseDelay[aRouterId] = Mle::kRouterIdReuseDelay;

	for (Router *router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
	{
	if (router->GetNextHop() == rloc16)
	{
	router->SetNextHop(Mle::kInvalidRouterId);
	router->SetCost(0);
	}
	}

	mRouterIdSequence++;
	mRouterIdSequenceLastUpdated = TimerMilli::GetNow();

	Get<AddressResolver>().Remove(aRouterId);
	Get<NetworkData::Leader>().RemoveBorderRouter(rloc16, NetworkData::Leader::kMatchModeRouterId);
	Get<Mle::MleRouter>().ResetAdvertiseInterval();

	otLogNoteMle("Release router id %d", aRouterId);

	exit:
	return error;
	}

	void RouterTable::RemoveNeighbor(Router &aRouter)
	{
	aRouter.SetLinkQualityOut(0);
	aRouter.SetLastHeard(TimerMilli::GetNow());

	for (Router *cur = GetFirstEntry(); cur != NULL; cur = GetNextEntry(cur))
	{
	if (cur->GetNextHop() == aRouter.GetRouterId())
	{
	cur->SetNextHop(Mle::kInvalidRouterId);
	cur->SetCost(0);

	if (GetLinkCost(*cur) >= Mle::kMaxRouteCost)
	{
	Get<Mle::MleRouter>().ResetAdvertiseInterval();
	}
	}
	}

	if (aRouter.GetNextHop() == Mle::kInvalidRouterId)
	{
	Get<Mle::MleRouter>().ResetAdvertiseInterval();

	// Clear all EID-to-RLOC entries associated with the router.
	Get<AddressResolver>().Remove(aRouter.GetRouterId());
	}
	}

	uint8_t RouterTable::GetActiveLinkCount(void) const
	{
	uint8_t activeLinks = 0;

	for (const Router *router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
	{
	if (router->IsStateValid())
	{
	activeLinks++;
	}
	}

	return activeLinks;
	}

	Router *RouterTable::GetNeighbor(uint16_t aRloc16)
	{
	Router *router = NULL;

	VerifyOrExit(aRloc16 != Get<Mle::MleRouter>().GetRloc16());

	for (router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
	{
	if (router->IsStateValid() && router->GetRloc16() == aRloc16)
	{
	ExitNow();
	}
	}

	exit:
	return router;
	}

	Router *RouterTable::GetNeighbor(const Mac::ExtAddress &aExtAddress)
	{
	Router *router = NULL;

	VerifyOrExit(aExtAddress != Get<Mac::Mac>().GetExtAddress());

	for (router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
	{
	if (router->IsStateValid() && router->GetExtAddress() == aExtAddress)
	{
	ExitNow();
	}
	}

	exit:
	return router;
	}

	const Router *RouterTable::GetRouter(uint8_t aRouterId) const
	{
	const Router *router = NULL;
	uint16_t rloc16 = Mle::Mle::Rloc16FromRouterId(aRouterId);

	for (router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
	{
	if (router->GetRloc16() == rloc16)
	{
	break;
	}
	}

	return router;
	}

	Router *RouterTable::GetRouter(const Mac::ExtAddress &aExtAddress)
	{
	Router *router = NULL;

	for (router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
	{
	if (router->GetExtAddress() == aExtAddress)
	{
	break;
	}
	}

	return router;
	}

	otError RouterTable::GetRouterInfo(uint16_t aRouterId, otRouterInfo &aRouterInfo)
	{
	otError error = OT_ERROR_NONE;
	Router *router;
	uint8_t routerId;

	if (aRouterId <= Mle::kMaxRouterId)
	{
	routerId = static_cast<uint8_t>(aRouterId);
	}
	else
	{
	VerifyOrExit(Mle::Mle::IsActiveRouter(aRouterId), error = OT_ERROR_INVALID_ARGS);
	routerId = Mle::Mle::RouterIdFromRloc16(aRouterId);
	VerifyOrExit(routerId <= Mle::kMaxRouterId, error = OT_ERROR_INVALID_ARGS);
	}

	router = GetRouter(routerId);
	VerifyOrExit(router != NULL, error = OT_ERROR_NOT_FOUND);

	memset(&aRouterInfo, 0, sizeof(aRouterInfo));
	aRouterInfo.mRouterId = routerId;
	aRouterInfo.mRloc16 = Mle::Mle::Rloc16FromRouterId(routerId);
	aRouterInfo.mExtAddress = router->GetExtAddress();
	aRouterInfo.mAllocated = true;
	aRouterInfo.mNextHop = router->GetNextHop();
	aRouterInfo.mLinkEstablished = router->IsStateValid();
	aRouterInfo.mPathCost = router->GetCost();
	aRouterInfo.mLinkQualityIn = router->GetLinkInfo().GetLinkQuality();
	aRouterInfo.mLinkQualityOut = router->GetLinkQualityOut();
	aRouterInfo.mAge = static_cast<uint8_t>(Time::MsecToSec(TimerMilli::GetNow() - router->GetLastHeard()));

	exit:
	return error;
	}

	Router *RouterTable::GetLeader(void)
	{
	return GetRouter(Get<Mle::MleRouter>().GetLeaderId());
	}

	uint32_t RouterTable::GetLeaderAge(void) const
	{
	return (mActiveRouterCount > 0) ? Time::MsecToSec(TimerMilli::GetNow() - mRouterIdSequenceLastUpdated) : 0xffffffff;
	}

	uint8_t RouterTable::GetNeighborCount(void) const
	{
	uint8_t count = 0;

	for (const Router *router = GetFirstEntry(); router != NULL; router = GetNextEntry(router))
	{
	if (router->IsStateValid())
	{
	count++;
	}
	}

	return count;
	}

	uint8_t RouterTable::GetLinkCost(Router &aRouter)
	{
	uint8_t rval = Mle::kMaxRouteCost;

	VerifyOrExit(aRouter.GetRloc16() != Get<Mle::MleRouter>().GetRloc16() && aRouter.IsStateValid());

	rval = aRouter.GetLinkInfo().GetLinkQuality();

	if (rval > aRouter.GetLinkQualityOut())
	{
	rval = aRouter.GetLinkQualityOut();
	}

	rval = Mle::MleRouter::LinkQualityToCost(rval);

	exit:
	return rval;
	}

	void RouterTable::ProcessTlv(const Mle::RouteTlv &aTlv)
	{
	bool allocationChanged = false;

	mRouterIdSequence = aTlv.GetRouterIdSequence();
	mRouterIdSequenceLastUpdated = TimerMilli::GetNow();

	for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
	{
	if (aTlv.IsRouterIdSet(routerId) == IsAllocated(routerId))
	{
	continue;
	}

	allocationChanged = true;

	if (aTlv.IsRouterIdSet(routerId))
	{
	mAllocatedRouterIds.Add(routerId);
	}
	else
	{
	Router *router = GetRouter(routerId);

	assert(router != NULL);
	router->SetNextHop(Mle::kInvalidRouterId);
	RemoveNeighbor(*router);

	mAllocatedRouterIds.Remove(routerId);
	}
	}

	if (allocationChanged)
	{
	UpdateAllocation();
	Get<Mle::MleRouter>().ResetAdvertiseInterval();
	}
	}

	void RouterTable::ProcessTlv(const ThreadRouterMaskTlv &aTlv)
	{
	bool allocationChanged = false;

	mRouterIdSequence = aTlv.GetIdSequence();
	mRouterIdSequenceLastUpdated = TimerMilli::GetNow();

	for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
	{
	if (aTlv.IsAssignedRouterIdSet(routerId) == IsAllocated(routerId))
	{
	continue;
	}

	allocationChanged = true;

	if (aTlv.IsAssignedRouterIdSet(routerId))
	{
	mAllocatedRouterIds.Add(routerId);
	}
	else
	{
	mAllocatedRouterIds.Remove(routerId);
	}
	}

	if (allocationChanged)
	{
	UpdateAllocation();
	Get<Mle::MleRouter>().ResetAdvertiseInterval();
	}
	}

	void RouterTable::ProcessTimerTick(void)
	{
	Mle::MleRouter &mle = Get<Mle::MleRouter>();

	if (mle.GetRole() == OT_DEVICE_ROLE_LEADER)
	{
	// update router id sequence
	if (GetLeaderAge() >= Mle::kRouterIdSequencePeriod)
	{
	mRouterIdSequence++;
	mRouterIdSequenceLastUpdated = TimerMilli::GetNow();
	}

	for (uint8_t routerId = 0; routerId <= Mle::kMaxRouterId; routerId++)
	{
	if (mRouterIdReuseDelay[routerId] > 0)
	{
	mRouterIdReuseDelay[routerId]--;
	}
	}
	}
	}

	} // namespace ot

	#endif // OPENTHREAD_FTD