summaryrefslogtreecommitdiffstats
path: root/src/vnet/ip/ip4_mtrie.c
AgeCommit message (Collapse)AuthorFilesLines
2021-12-24ip: remove archaic vector code from mtrieDamjan Marion1-67/+9
Type: improvement Change-Id: Ib39478a2e6991d721c4ba3ea61c97bfb07238016 Signed-off-by: Damjan Marion <damarion@cisco.com>
2021-08-11ip: [re]introduce the 8-8-8-8 stride MTRIENeale Ranns1-46/+161
Type: improvement there's a time-space trade-off between the 16-8-8 and 8-8-8-8 stride. FIB continues to use the 16-8-8. Other features are now free to make the choice. Signed-off-by: Neale Ranns <neale@graphiant.com> Change-Id: I6691a163486ce62e75e629f6ef0c990f253df8e5
2021-08-11ip: Rename the ip4 mtrie function to be 16_8_8 specificNeale Ranns1-135/+121
Type: improvement the existing mtrie functions use the existing 16_8_8 mtrie. Rename them to make that explicit. Then we can add the 8_8_8_8 types and functions alongside. Signed-off-by: Neale Ranns <neale@graphiant.com> Change-Id: If5ce7a282d5d3742dc65bcd0523220235d9c510d
2020-09-21ip: use main heap for mtrieDamjan Marion1-48/+0
Main heap can be hugepage backed so it is more efficient to use main heap instead of allocating special heap just for mtrie.... Type: improvement Change-Id: I210912ab8567c043205ddfc10fdcfde9a0fa7757 Signed-off-by: Damjan Marion <damarion@cisco.com>
2020-06-12ip: allocate ip4 mtrie pages in htlb memoryDave Barach1-2/+42
No change in default behavior. To use htlb pages for the ip4 mtrie, use the "ip" command-line option "mtrie-hugetlb". Type: improvement Signed-off-by: Dave Barach <dave@barachs.net> Change-Id: I5497e426a47200edff2c7e15563ed6a42af12e7f
2020-05-15misc: removed executable bits from source filesRay Kinsella1-0/+0
Identified and removed executable bit from source files in the tree. find . -perm 755 -name *.[ch] -exec chmod a-x {} \; Type: improvement Signed-off-by: Ray Kinsella <mdr@ashroe.eu> Change-Id: I00710d59fcc46ce5be5233109af4c8077daff74b
2020-02-11vppinfra: remove the historical mheap memory allocatorDave Barach1-4/+0
The mheap allocator has been turned off for several releases. This commit removes the cmake config parameter, parallel support for dlmalloc and mheap, and the mheap allocator itself. Type: refactor Signed-off-by: Dave Barach <dave@barachs.net> Change-Id: I104f88a1f06e47e90e5f7fb3e11cd1ca66467903
2019-10-29ip: refactor ip4_mtrie to use atomic store-releasejaszha031-14/+5
ip4_mtrie used full memory barrier compare-and-swap in set_leaf () and set_root_leaf () even though only one thread updates the trie. Replaced such instances of compare-and-swap with atomic store-release. Type: refactor Change-Id: Ic6e3c84480697915541acd16dcc630d1c436137d Signed-off-by: Jason Zhang <jason.zhang2@arm.com> Reviewed-by: Lijian Zhang <Lijian.Zhang@arm.com> Reviewed-by: Ruifeng Wang <ruifeng.wang@arm.com>
2019-10-29ip: refactor ip4_mtrie to atomically unset leavesjaszha031-4/+6
ip4_mtrie set leaves atomically in set_leaf () and set_root_leaf () but deleted leaves using regular stores in unset_leaf () and unset_root_leaf (). Changed leaf deletion to update mtrie using atomic store-release. Slight performance improvement was observed in benchmarking on Qualcomm and Xeon machines. Benchmarking involved running 'ip route add' and 'ip route del' on vpp instances. Below are the routes/second for adding and deleting 100k routes before and after the store-release changes: Xeon Add Routes Before: 1.140e6, 1.139e6, 1.148e6, 1.158e6, 1.155e6 Xeon Add Routes After: 1.167e6, 1.170e6, 1.174e6, 1.173e6, 1.169e6 Xeon Del Routes Before: 7.287e7, 8.089e7, 6.048e7, 7.171e7, 7.821e7 Xeon Del Routes After: 8.729e7, 7.353e7, 7.856e7, 8.209e7, 7.787e7 Qualcomm Add Routes Before: 3.709e5, 3.954e5, 3.739e5, 3.759e5, 3.671e5 Qualcomm Add Routes After: 3.879e5, 3.967e5, 3.936e5, 3.764e5, 3.817e5 Qualcomm Del Routes Before: 1.286e7, 1.379e7, 1.353e7, 1.230e7, 1.331e7 Qualcomm Del Routes After: 1.411e7, 1.355e7, 1.373e7, 1.394e7, 1.314e7 Type: refactor Change-Id: If3acd25a2fb87addd0eb13d82d3c8f46579e8060 Signed-off-by: Jason Zhang <jason.zhang2@arm.com> Reviewed-by: Lijian Zhang <Lijian.Zhang@arm.com> Reviewed-by: Ruifeng Wang <ruifeng.wang@arm.com>
2019-09-25fib: fix some typos in fib/mtrieLijian.Zhang1-1/+1
Type: fix Change-Id: I1af0e4a9bc23a3b6b6d3a74df093801ab6cae1f8 Signed-off-by: Lijian Zhang <Lijian.Zhang@arm.com>
2018-10-23c11 safe string handling supportDave Barach1-3/+3
Change-Id: Ied34720ca5a6e6e717eea4e86003e854031b6eab Signed-off-by: Dave Barach <dave@barachs.net>
2018-10-19vppinfra: add atomic macros for __sync builtinsSirshak Das1-9/+9
This is first part of addition of atomic macros with only macros for __sync builtins. - Based on earlier patch by Damjan (https://gerrit.fd.io/r/#/c/10729/) Additionally - clib_atomic_release macro added and used in the absence of any memory barrier. - clib_atomic_bool_cmp_and_swap added Change-Id: Ie4e48c1e184a652018d1d0d87c4be80ddd180a3b Original-patch-by: Damjan Marion <damarion@cisco.com> Signed-off-by: Sirshak Das <sirshak.das@arm.com> Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com> Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com> Reviewed-by: Steve Capper <steve.capper@arm.com>
2018-10-17VPP-1459:Ip4 lookup fail when exist prefix cover.mu.duojiao1-3/+1
Change-Id: I4ba0aeb65219596475345e42b8cd34019f5594c6 Signed-off-by: mu.duojiao <mu.duojiao@zte.com.cn>
2018-10-15VPP-1448: Fix error when recurse on down the trie.mu.duojiao1-21/+19
Change-Id: Idfed8243643780d3f52dfe6e6ec621c440daa6ae Signed-off-by: mu.duojiao <mu.duojiao@zte.com.cn>
2018-07-18Add config option to use dlmalloc instead of mheapDave Barach1-0/+4
Configure w/ --enable-dlmalloc, see .../build-data/platforms/vpp.mk src/vppinfra/dlmalloc.[ch] are slightly modified versions of the well-known Doug Lea malloc. Main advantage: dlmalloc mspaces have no inherent size limit. Change-Id: I19b3f43f3c65bcfb82c1a265a97922d01912446e Signed-off-by: Dave Barach <dave@barachs.net>
2018-04-12Fixes for 'make UNATTENDED=yes CC=clang CXX=clang verify'Neale Ranns1-3/+3
Change-Id: I994649761fe2e66e12ae0e49a84fb1d0a966ddfb Signed-off-by: Neale Ranns <nranns@cisco.com>
2017-12-13Separate heap for IPv4 mtriesNeale Ranns1-3/+18
Change-Id: I497e9f6489dd35219bcf2b51ac992467aac4c8eb Signed-off-by: Neale Ranns <nranns@cisco.com>
2017-11-29Include allocated table memory in 'sh fib mem' outputNeale Ranns1-3/+5
DBGvpp# sh fib mem FIB memory Tables: SAFI Number Bytes IPv4 unicast 2 673066 IPv6 unicast 2 1054608 MPLS 1 4194312 IPv4 multicast 2 2322 IPv6 multicast 2 ??? Nodes: Name Size in-use /allocated totals Entry 96 20 / 20 1920/1920 Entry Source 32 0 / 0 0/0 Entry Path-Extensions 60 0 / 0 0/0 multicast-Entry 192 12 / 12 2304/2304 Path-list 40 28 / 28 1120/1120 uRPF-list 16 20 / 20 320/320 Path 72 28 / 28 2016/2016 Node-list elements 20 28 / 28 560/560 Node-list heads 8 30 / 30 240/240 Change-Id: I8c8f6f1c87502a40265bf4f302d0daef111a4a4e Signed-off-by: Neale Ranns <nranns@cisco.com>
2017-11-27Fix - sh ip fib mtrie sumNeale Ranns1-8/+13
Change-Id: I62a6ee78ee9ad73fd58a46fbdca54fd964fec113 Signed-off-by: Neale Ranns <nranns@cisco.com>
2017-10-04[aarch64] Fixes CLI crashes on dpaa2 platform.Christophe Fontaine1-1/+1
- always use 'va_args' as pointer in all format_* functions - u32 for all 'indent' params as it's declaration was inconsistent Change-Id: Ic5799309a6b104c9b50fec309cba789c8da99e79 Signed-off-by: Christophe Fontaine <christophe.fontaine@enea.com>
2017-06-06Fix coverity error in IP4 Mtrie.Neale Ranns1-4/+4
Change-Id: I586a758a8b4b0ea5ca030b2df2796f5acb49e154 Signed-off-by: Neale Ranns <nranns@cisco.com>
2017-04-11MTRIE coverity fixesNeale Ranns1-6/+8
Change-Id: If98355bebe823f45b11b0908a8d7700ab273a6db Signed-off-by: Neale Ranns <nranns@cisco.com>
2017-04-01MTRIE Optimisations 2Neale Ranns1-207/+404
1) 16-8-8 stride. Reduce trie depth walk traded with increased memory in the top PLY. 2) separate the vector of protocol-independent (PI) fib_table_t with the vector of protocol dependent (PD) FIBs. PD FIBs are large structures, we don't want to burn the memory for ech PD type 3) Go straight to the PD FIB in the data-path thus avoiding an indirection through, e.g., a PLY pool. Change-Id: I800d1ed0b2049040d5da95213f3ed6b12bdd78b7 Signed-off-by: Neale Ranns <nranns@cisco.com>
2017-03-29Mtrie optimisationsNeale Ranns1-80/+124
1 - make the default route non-special, i.e. like any other less specific route. Consequently, all buckets have a valid valid index of either a leaf or a ply. Checks for special indeices in the data-path can thus be removed. 2 - since all leaves are now 'real' i.e. they represent a real load-balance object, to tell if a ply slot is 'empty' requeirs chekcing that the prefix length of the leaf occupying the slot is slot than the minium value for that ply. 3 - when removing a leaf find the cover first, then recurse down the ply and replace the old leaf with the cover. This saves us a ply walk. Change-Id: Idd523019e8bb1b6ef527b1f5279a5e24bcf18332 Signed-off-by: Neale Ranns <nranns@cisco.com>
2016-12-28Reorganize source tree to use single autotools instanceDamjan Marion1-0/+568
Change-Id: I7b51f88292e057c6443b12224486f2d0c9f8ae23 Signed-off-by: Damjan Marion <damarion@cisco.com>