Ip4Route.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654
  1. /** @file
  2. Copyright (c) 2005 - 2016, Intel Corporation. All rights reserved.<BR>
  3. SPDX-License-Identifier: BSD-2-Clause-Patent
  4. **/
  5. #include "Ip4Impl.h"
  6. /**
  7. Allocate a route entry then initialize it with the Dest/Netmask
  8. and Gateway.
  9. @param[in] Dest The destination network
  10. @param[in] Netmask The destination network mask
  11. @param[in] GateWay The nexthop address
  12. @return NULL if failed to allocate memory, otherwise the newly created
  13. route entry.
  14. **/
  15. IP4_ROUTE_ENTRY *
  16. Ip4CreateRouteEntry (
  17. IN IP4_ADDR Dest,
  18. IN IP4_ADDR Netmask,
  19. IN IP4_ADDR GateWay
  20. )
  21. {
  22. IP4_ROUTE_ENTRY *RtEntry;
  23. RtEntry = AllocatePool (sizeof (IP4_ROUTE_ENTRY));
  24. if (RtEntry == NULL) {
  25. return NULL;
  26. }
  27. InitializeListHead (&RtEntry->Link);
  28. RtEntry->RefCnt = 1;
  29. RtEntry->Dest = Dest;
  30. RtEntry->Netmask = Netmask;
  31. RtEntry->NextHop = GateWay;
  32. RtEntry->Flag = 0;
  33. return RtEntry;
  34. }
  35. /**
  36. Free the route table entry. It is reference counted.
  37. @param RtEntry The route entry to free.
  38. **/
  39. VOID
  40. Ip4FreeRouteEntry (
  41. IN IP4_ROUTE_ENTRY *RtEntry
  42. )
  43. {
  44. ASSERT (RtEntry->RefCnt > 0);
  45. if (--RtEntry->RefCnt == 0) {
  46. FreePool (RtEntry);
  47. }
  48. }
  49. /**
  50. Allocate and initialize an IP4 route cache entry.
  51. @param[in] Dst The destination address
  52. @param[in] Src The source address
  53. @param[in] GateWay The next hop address
  54. @param[in] Tag The tag from the caller. This marks all the cache
  55. entries spawned from one route table entry.
  56. @return NULL if failed to allocate memory for the cache, other point
  57. to the created route cache entry.
  58. **/
  59. IP4_ROUTE_CACHE_ENTRY *
  60. Ip4CreateRouteCacheEntry (
  61. IN IP4_ADDR Dst,
  62. IN IP4_ADDR Src,
  63. IN IP4_ADDR GateWay,
  64. IN UINTN Tag
  65. )
  66. {
  67. IP4_ROUTE_CACHE_ENTRY *RtCacheEntry;
  68. RtCacheEntry = AllocatePool (sizeof (IP4_ROUTE_CACHE_ENTRY));
  69. if (RtCacheEntry == NULL) {
  70. return NULL;
  71. }
  72. InitializeListHead (&RtCacheEntry->Link);
  73. RtCacheEntry->RefCnt = 1;
  74. RtCacheEntry->Dest = Dst;
  75. RtCacheEntry->Src = Src;
  76. RtCacheEntry->NextHop = GateWay;
  77. RtCacheEntry->Tag = Tag;
  78. return RtCacheEntry;
  79. }
  80. /**
  81. Free the route cache entry. It is reference counted.
  82. @param RtCacheEntry The route cache entry to free.
  83. **/
  84. VOID
  85. Ip4FreeRouteCacheEntry (
  86. IN IP4_ROUTE_CACHE_ENTRY *RtCacheEntry
  87. )
  88. {
  89. ASSERT (RtCacheEntry->RefCnt > 0);
  90. if (--RtCacheEntry->RefCnt == 0) {
  91. FreePool (RtCacheEntry);
  92. }
  93. }
  94. /**
  95. Initialize an empty route cache table.
  96. @param[in, out] RtCache The route cache table to initialize.
  97. **/
  98. VOID
  99. Ip4InitRouteCache (
  100. IN OUT IP4_ROUTE_CACHE *RtCache
  101. )
  102. {
  103. UINT32 Index;
  104. for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) {
  105. InitializeListHead (&(RtCache->CacheBucket[Index]));
  106. }
  107. }
  108. /**
  109. Clean up a route cache, that is free all the route cache
  110. entries enqueued in the cache.
  111. @param[in] RtCache The route cache table to clean up
  112. **/
  113. VOID
  114. Ip4CleanRouteCache (
  115. IN IP4_ROUTE_CACHE *RtCache
  116. )
  117. {
  118. LIST_ENTRY *Entry;
  119. LIST_ENTRY *Next;
  120. IP4_ROUTE_CACHE_ENTRY *RtCacheEntry;
  121. UINT32 Index;
  122. for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) {
  123. NET_LIST_FOR_EACH_SAFE (Entry, Next, &(RtCache->CacheBucket[Index])) {
  124. RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
  125. RemoveEntryList (Entry);
  126. Ip4FreeRouteCacheEntry (RtCacheEntry);
  127. }
  128. }
  129. }
  130. /**
  131. Create an empty route table, includes its internal route cache
  132. @return NULL if failed to allocate memory for the route table, otherwise
  133. the point to newly created route table.
  134. **/
  135. IP4_ROUTE_TABLE *
  136. Ip4CreateRouteTable (
  137. VOID
  138. )
  139. {
  140. IP4_ROUTE_TABLE *RtTable;
  141. UINT32 Index;
  142. RtTable = AllocatePool (sizeof (IP4_ROUTE_TABLE));
  143. if (RtTable == NULL) {
  144. return NULL;
  145. }
  146. RtTable->RefCnt = 1;
  147. RtTable->TotalNum = 0;
  148. for (Index = 0; Index <= IP4_MASK_MAX; Index++) {
  149. InitializeListHead (&(RtTable->RouteArea[Index]));
  150. }
  151. RtTable->Next = NULL;
  152. Ip4InitRouteCache (&RtTable->Cache);
  153. return RtTable;
  154. }
  155. /**
  156. Free the route table and its associated route cache. Route
  157. table is reference counted.
  158. @param[in] RtTable The route table to free.
  159. **/
  160. VOID
  161. Ip4FreeRouteTable (
  162. IN IP4_ROUTE_TABLE *RtTable
  163. )
  164. {
  165. LIST_ENTRY *Entry;
  166. LIST_ENTRY *Next;
  167. IP4_ROUTE_ENTRY *RtEntry;
  168. UINT32 Index;
  169. ASSERT (RtTable->RefCnt > 0);
  170. if (--RtTable->RefCnt > 0) {
  171. return;
  172. }
  173. //
  174. // Free all the route table entry and its route cache.
  175. //
  176. for (Index = 0; Index <= IP4_MASK_MAX; Index++) {
  177. NET_LIST_FOR_EACH_SAFE (Entry, Next, &(RtTable->RouteArea[Index])) {
  178. RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
  179. RemoveEntryList (Entry);
  180. Ip4FreeRouteEntry (RtEntry);
  181. }
  182. }
  183. Ip4CleanRouteCache (&RtTable->Cache);
  184. FreePool (RtTable);
  185. }
  186. /**
  187. Remove all the cache entries bearing the Tag. When a route cache
  188. entry is created, it is tagged with the address of route entry
  189. from which it is spawned. When a route entry is deleted, the cache
  190. entries spawned from it are also deleted.
  191. @param RtCache Route cache to remove the entries from
  192. @param Tag The Tag of the entries to remove
  193. **/
  194. VOID
  195. Ip4PurgeRouteCache (
  196. IN OUT IP4_ROUTE_CACHE *RtCache,
  197. IN UINTN Tag
  198. )
  199. {
  200. LIST_ENTRY *Entry;
  201. LIST_ENTRY *Next;
  202. IP4_ROUTE_CACHE_ENTRY *RtCacheEntry;
  203. UINT32 Index;
  204. for (Index = 0; Index < IP4_ROUTE_CACHE_HASH_VALUE; Index++) {
  205. NET_LIST_FOR_EACH_SAFE (Entry, Next, &RtCache->CacheBucket[Index]) {
  206. RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
  207. if (RtCacheEntry->Tag == Tag) {
  208. RemoveEntryList (Entry);
  209. Ip4FreeRouteCacheEntry (RtCacheEntry);
  210. }
  211. }
  212. }
  213. }
  214. /**
  215. Add a route entry to the route table. All the IP4_ADDRs are in
  216. host byte order.
  217. @param[in, out] RtTable Route table to add route to
  218. @param[in] Dest The destination of the network
  219. @param[in] Netmask The netmask of the destination
  220. @param[in] Gateway The next hop address
  221. @retval EFI_ACCESS_DENIED The same route already exists
  222. @retval EFI_OUT_OF_RESOURCES Failed to allocate memory for the entry
  223. @retval EFI_SUCCESS The route is added successfully.
  224. **/
  225. EFI_STATUS
  226. Ip4AddRoute (
  227. IN OUT IP4_ROUTE_TABLE *RtTable,
  228. IN IP4_ADDR Dest,
  229. IN IP4_ADDR Netmask,
  230. IN IP4_ADDR Gateway
  231. )
  232. {
  233. LIST_ENTRY *Head;
  234. LIST_ENTRY *Entry;
  235. IP4_ROUTE_ENTRY *RtEntry;
  236. //
  237. // All the route entries with the same netmask length are
  238. // linke to the same route area
  239. //
  240. Head = &(RtTable->RouteArea[NetGetMaskLength (Netmask)]);
  241. //
  242. // First check whether the route exists
  243. //
  244. NET_LIST_FOR_EACH (Entry, Head) {
  245. RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
  246. if (IP4_NET_EQUAL (RtEntry->Dest, Dest, Netmask) && (RtEntry->NextHop == Gateway)) {
  247. return EFI_ACCESS_DENIED;
  248. }
  249. }
  250. //
  251. // Create a route entry and insert it to the route area.
  252. //
  253. RtEntry = Ip4CreateRouteEntry (Dest, Netmask, Gateway);
  254. if (RtEntry == NULL) {
  255. return EFI_OUT_OF_RESOURCES;
  256. }
  257. if (Gateway == IP4_ALLZERO_ADDRESS) {
  258. RtEntry->Flag = IP4_DIRECT_ROUTE;
  259. }
  260. InsertHeadList (Head, &RtEntry->Link);
  261. RtTable->TotalNum++;
  262. return EFI_SUCCESS;
  263. }
  264. /**
  265. Remove a route entry and all the route caches spawn from it.
  266. @param RtTable The route table to remove the route from
  267. @param Dest The destination network
  268. @param Netmask The netmask of the Dest
  269. @param Gateway The next hop address
  270. @retval EFI_SUCCESS The route entry is successfully removed
  271. @retval EFI_NOT_FOUND There is no route entry in the table with that
  272. property.
  273. **/
  274. EFI_STATUS
  275. Ip4DelRoute (
  276. IN OUT IP4_ROUTE_TABLE *RtTable,
  277. IN IP4_ADDR Dest,
  278. IN IP4_ADDR Netmask,
  279. IN IP4_ADDR Gateway
  280. )
  281. {
  282. LIST_ENTRY *Head;
  283. LIST_ENTRY *Entry;
  284. LIST_ENTRY *Next;
  285. IP4_ROUTE_ENTRY *RtEntry;
  286. Head = &(RtTable->RouteArea[NetGetMaskLength (Netmask)]);
  287. NET_LIST_FOR_EACH_SAFE (Entry, Next, Head) {
  288. RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
  289. if (IP4_NET_EQUAL (RtEntry->Dest, Dest, Netmask) && (RtEntry->NextHop == Gateway)) {
  290. Ip4PurgeRouteCache (&RtTable->Cache, (UINTN)RtEntry);
  291. RemoveEntryList (Entry);
  292. Ip4FreeRouteEntry (RtEntry);
  293. RtTable->TotalNum--;
  294. return EFI_SUCCESS;
  295. }
  296. }
  297. return EFI_NOT_FOUND;
  298. }
  299. /**
  300. Find a route cache with the dst and src. This is used by ICMP
  301. redirect message process. All kinds of redirect is treated as
  302. host redirect according to RFC1122. So, only route cache entries
  303. are modified according to the ICMP redirect message.
  304. @param[in] RtTable The route table to search the cache for
  305. @param[in] Dest The destination address
  306. @param[in] Src The source address
  307. @return NULL if no route entry to the (Dest, Src). Otherwise the point
  308. to the correct route cache entry.
  309. **/
  310. IP4_ROUTE_CACHE_ENTRY *
  311. Ip4FindRouteCache (
  312. IN IP4_ROUTE_TABLE *RtTable,
  313. IN IP4_ADDR Dest,
  314. IN IP4_ADDR Src
  315. )
  316. {
  317. LIST_ENTRY *Entry;
  318. IP4_ROUTE_CACHE_ENTRY *RtCacheEntry;
  319. UINT32 Index;
  320. Index = IP4_ROUTE_CACHE_HASH (Dest, Src);
  321. NET_LIST_FOR_EACH (Entry, &RtTable->Cache.CacheBucket[Index]) {
  322. RtCacheEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
  323. if ((RtCacheEntry->Dest == Dest) && (RtCacheEntry->Src == Src)) {
  324. NET_GET_REF (RtCacheEntry);
  325. return RtCacheEntry;
  326. }
  327. }
  328. return NULL;
  329. }
  330. /**
  331. Search the route table for a most specific match to the Dst. It searches
  332. from the longest route area (mask length == 32) to the shortest route area
  333. (default routes). In each route area, it will first search the instance's
  334. route table, then the default route table. This is required by the following
  335. requirements:
  336. 1. IP search the route table for a most specific match
  337. 2. The local route entries have precedence over the default route entry.
  338. @param[in] RtTable The route table to search from
  339. @param[in] Dst The destination address to search
  340. @return NULL if no route matches the Dst, otherwise the point to the
  341. most specific route to the Dst.
  342. **/
  343. IP4_ROUTE_ENTRY *
  344. Ip4FindRouteEntry (
  345. IN IP4_ROUTE_TABLE *RtTable,
  346. IN IP4_ADDR Dst
  347. )
  348. {
  349. LIST_ENTRY *Entry;
  350. IP4_ROUTE_ENTRY *RtEntry;
  351. IP4_ROUTE_TABLE *Table;
  352. INTN Index;
  353. RtEntry = NULL;
  354. for (Index = IP4_MASK_MAX; Index >= 0; Index--) {
  355. for (Table = RtTable; Table != NULL; Table = Table->Next) {
  356. NET_LIST_FOR_EACH (Entry, &Table->RouteArea[Index]) {
  357. RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
  358. if (IP4_NET_EQUAL (RtEntry->Dest, Dst, RtEntry->Netmask)) {
  359. NET_GET_REF (RtEntry);
  360. return RtEntry;
  361. }
  362. }
  363. }
  364. }
  365. return NULL;
  366. }
  367. /**
  368. Search the route table to route the packet. Return/create a route
  369. cache if there is a route to the destination.
  370. @param[in] RtTable The route table to search from
  371. @param[in] Dest The destination address to search for
  372. @param[in] Src The source address to search for
  373. @param[in] SubnetMask The subnet mask of the Src address, this field is
  374. used to check if the station is using /32 subnet.
  375. @param[in] AlwaysTryDestAddr Always try to use the dest address as next hop even
  376. though we can't find a matching route entry. This
  377. field is only valid when using /32 subnet.
  378. @return NULL if failed to route packet, otherwise a route cache
  379. entry that can be used to route packet.
  380. **/
  381. IP4_ROUTE_CACHE_ENTRY *
  382. Ip4Route (
  383. IN IP4_ROUTE_TABLE *RtTable,
  384. IN IP4_ADDR Dest,
  385. IN IP4_ADDR Src,
  386. IN IP4_ADDR SubnetMask,
  387. IN BOOLEAN AlwaysTryDestAddr
  388. )
  389. {
  390. LIST_ENTRY *Head;
  391. LIST_ENTRY *Entry;
  392. LIST_ENTRY *Next;
  393. IP4_ROUTE_CACHE_ENTRY *RtCacheEntry;
  394. IP4_ROUTE_CACHE_ENTRY *Cache;
  395. IP4_ROUTE_ENTRY *RtEntry;
  396. IP4_ADDR NextHop;
  397. UINT32 Count;
  398. ASSERT (RtTable != NULL);
  399. Head = &RtTable->Cache.CacheBucket[IP4_ROUTE_CACHE_HASH (Dest, Src)];
  400. RtCacheEntry = Ip4FindRouteCache (RtTable, Dest, Src);
  401. //
  402. // If found, promote the cache entry to the head of the hash bucket. LRU
  403. //
  404. if (RtCacheEntry != NULL) {
  405. RemoveEntryList (&RtCacheEntry->Link);
  406. InsertHeadList (Head, &RtCacheEntry->Link);
  407. return RtCacheEntry;
  408. }
  409. //
  410. // Search the route table for the most specific route
  411. //
  412. RtEntry = Ip4FindRouteEntry (RtTable, Dest);
  413. if (RtEntry == NULL) {
  414. if (SubnetMask != IP4_ALLONE_ADDRESS) {
  415. return NULL;
  416. } else if (!AlwaysTryDestAddr) {
  417. return NULL;
  418. }
  419. }
  420. //
  421. // Found a route to the Dest, if it is a direct route, the packet
  422. // will be sent directly to the destination, such as for connected
  423. // network. Otherwise, it is an indirect route, the packet will be
  424. // sent to the next hop router.
  425. //
  426. // When using /32 subnet mask, the packet will always be sent to the direct
  427. // destination first, if we can't find a matching route cache.
  428. //
  429. if ((SubnetMask == IP4_ALLONE_ADDRESS) || ((RtEntry->Flag & IP4_DIRECT_ROUTE) != 0)) {
  430. NextHop = Dest;
  431. } else {
  432. NextHop = RtEntry->NextHop;
  433. }
  434. if (RtEntry != NULL) {
  435. Ip4FreeRouteEntry (RtEntry);
  436. }
  437. //
  438. // Create a route cache entry, and tag it as spawned from this route entry
  439. // For /32 subnet mask, the default route in RtEntry will be used if failed
  440. // to send the packet to driect destination address.
  441. //
  442. RtCacheEntry = Ip4CreateRouteCacheEntry (Dest, Src, NextHop, (UINTN)RtEntry);
  443. if (RtCacheEntry == NULL) {
  444. return NULL;
  445. }
  446. InsertHeadList (Head, &RtCacheEntry->Link);
  447. NET_GET_REF (RtCacheEntry);
  448. //
  449. // Each bucket of route cache can contain at most 64 entries.
  450. // Remove the entries at the tail of the bucket. These entries
  451. // are likely to be used least.
  452. //
  453. Count = 0;
  454. NET_LIST_FOR_EACH_SAFE (Entry, Next, Head) {
  455. if (++Count < IP4_ROUTE_CACHE_MAX) {
  456. continue;
  457. }
  458. Cache = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_CACHE_ENTRY, Link);
  459. RemoveEntryList (Entry);
  460. Ip4FreeRouteCacheEntry (Cache);
  461. }
  462. return RtCacheEntry;
  463. }
  464. /**
  465. Build a EFI_IP4_ROUTE_TABLE to be returned to the caller of
  466. GetModeData. The EFI_IP4_ROUTE_TABLE is clumsy to use in the
  467. internal operation of the IP4 driver.
  468. @param[in] IpInstance The IP4 child that requests the route table.
  469. @retval EFI_SUCCESS The route table is successfully build
  470. @retval EFI_OUT_OF_RESOURCES Failed to allocate the memory for the route table.
  471. **/
  472. EFI_STATUS
  473. Ip4BuildEfiRouteTable (
  474. IN IP4_PROTOCOL *IpInstance
  475. )
  476. {
  477. LIST_ENTRY *Entry;
  478. IP4_ROUTE_TABLE *RtTable;
  479. IP4_ROUTE_ENTRY *RtEntry;
  480. EFI_IP4_ROUTE_TABLE *Table;
  481. UINT32 Count;
  482. INT32 Index;
  483. RtTable = IpInstance->RouteTable;
  484. if (IpInstance->EfiRouteTable != NULL) {
  485. FreePool (IpInstance->EfiRouteTable);
  486. IpInstance->EfiRouteTable = NULL;
  487. IpInstance->EfiRouteCount = 0;
  488. }
  489. Count = RtTable->TotalNum;
  490. if (RtTable->Next != NULL) {
  491. Count += RtTable->Next->TotalNum;
  492. }
  493. if (Count == 0) {
  494. return EFI_SUCCESS;
  495. }
  496. Table = AllocatePool (sizeof (EFI_IP4_ROUTE_TABLE) * Count);
  497. if (Table == NULL) {
  498. return EFI_OUT_OF_RESOURCES;
  499. }
  500. //
  501. // Copy the route entry to EFI route table. Keep the order of
  502. // route entry copied from most specific to default route. That
  503. // is, interlevel the route entry from the instance's route area
  504. // and those from the default route table's route area.
  505. //
  506. Count = 0;
  507. for (Index = IP4_MASK_MAX; Index >= 0; Index--) {
  508. for (RtTable = IpInstance->RouteTable; RtTable != NULL; RtTable = RtTable->Next) {
  509. NET_LIST_FOR_EACH (Entry, &(RtTable->RouteArea[Index])) {
  510. RtEntry = NET_LIST_USER_STRUCT (Entry, IP4_ROUTE_ENTRY, Link);
  511. EFI_IP4 (Table[Count].SubnetAddress) = HTONL (RtEntry->Dest & RtEntry->Netmask);
  512. EFI_IP4 (Table[Count].SubnetMask) = HTONL (RtEntry->Netmask);
  513. EFI_IP4 (Table[Count].GatewayAddress) = HTONL (RtEntry->NextHop);
  514. Count++;
  515. }
  516. }
  517. }
  518. IpInstance->EfiRouteTable = Table;
  519. IpInstance->EfiRouteCount = Count;
  520. return EFI_SUCCESS;
  521. }