summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/bihash_template.c
AgeCommit message (Collapse)AuthorFilesLines
2023-03-18vppinfra: fix corner-cases in bihash lookupDave Barach1-13/+37
In a case where one pounds on a single kvp in a KVP_AT_BUCKET_LEVEL table, the code would sporadically return a transitional value (junk) from a half-deleted kvp. At most, 64-bits worth of the kvp will be written atomically, so using memset(...) to smear 0xFF's across a kvp to free it left a lot to be desired. Performance impact: very mild positive, thanks to FC for doing a multi-thread host stack perf/scale test. Added an ASSERT to catch attempts to add a (key,value) pair which contains the magic "free kvp" value. Type: fix Signed-off-by: Dave Barach <dave@barachs.net> Change-Id: I6a1aa8a2c30bc70bec4b696ce7b17c2839927065
2022-03-21vppinfra: add new bihash exportsNathan Skrzypczak1-6/+25
This adds two new exported functions for the clib_bihash * clib_bihash_add_with_overwrite_cb allowing to pass a callback to be called on overwriting a key with bucket lock held. * clib_bihash_add_del_with_hash doing an add_del with a precomputed hash. Type: feature Change-Id: I1590c933fa7cf21e6a8ada89b3456a60c4988244 Signed-off-by: Nathan Skrzypczak <nathan.skrzypczak@gmail.com>
2021-11-22vppinfra: fix the memory leak while doing clib_bihash_freeHan Wu1-0/+1
Type: fix Signed-off-by: Han Wu <wuhan9084@163.com> Change-Id: I6ad3c313dcab5ed193c135676c1cebd0a141fea1
2021-08-10vppinfra: Fix bihash del warningNathan Skrzypczak1-0/+6
Type: fix When freeing an uninstantiated bihash created with dont_add_to_all_bihash_list = 1 we get a warning. This removes the warning & the search for the bihash on cleanup. Change-Id: Iac50ce7e30b97925768f7ad3cb1d30af14686e21 Signed-off-by: Nathan Skrzypczak <nathan.skrzypczak@gmail.com>
2021-05-06vppinfra: fix testsDamjan Marion1-0/+4
Type: fix Change-Id: If59a66aae658dd35dbcb4987ab00c306b3c6e2e2 Signed-off-by: Damjan Marion <damarion@cisco.com>
2021-04-18vppinfra: remove linux/syscall.hDamjan Marion1-1/+1
For portabiliy reasons it is better to have all wrapped in clib code. I.e. instead of using getcpu() we have clib_get_current_numa_node () and clib_get_current_cpu_id(). Type: refactor Change-Id: I29b52d7f29bc7f93873402c4070561f564b71c63 Signed-off-by: Damjan Marion <damarion@cisco.com>
2020-10-02vppinfra: Function to check if a bihash has been initialisedNeale Ranns1-0/+5
Type: improvement Signed-off-by: Neale Ranns <nranns@cisco.com> Change-Id: Ic31f7721f326ca9d78d645abcea63ce58df5bd5b
2020-09-30vpp: update 'show bihash' commandDamjan Marion1-11/+14
Type: improvement Change-Id: I6d00ba840d2168af0658f97c45a42d39be7cbbad Signed-off-by: Damjan Marion <damarion@cisco.com>
2020-09-30vppinfra: use heap to store bihash dataDamjan Marion1-25/+165
Type: improvement Change-Id: Ifb0fa114414aa2fdc244f964612ca3ac3e29b5e1 Signed-off-by: Damjan Marion <damarion@cisco.com>
2020-08-17vppinfra: fix RC in bihash instantiationNathan Skrzypczak1-2/+2
There can be a race condition in the case a thread tries to do a bihash_search while another instantiates the bihash. Type: fix Change-Id: Ic61b590763beb409e112957c43a5a66cd10afb28 Signed-off-by: Nathan Skrzypczak <nathan.skrzypczak@gmail.com>
2020-08-06vppinfra: harmonize function namesDave Barach1-2/+2
Type: fix Signed-off-by: Dave Barach <dave@barachs.net> Change-Id: Icce7eab4510785e15bdcf97e4d1881b0f46f6899
2020-05-27vppinfra: fix SIGBUS in bihash init when running unpriviledged, take twoDamjan Marion1-1/+1
Looks like MAP_LOCK is not enough, so call mlock(...) instead.... Type: fix Change-Id: I1bc668a2bf3c861ca1c2d376c0fb6bfea87d4f48 Signed-off-by: Damjan Marion <damarion@cisco.com>
2020-05-24vppinfra: fix SIGBUS in bihash init when running unpriviledgedDamjan Marion1-1/+1
Obserbed when VPP is running in k8s container. Type: fix Change-Id: Ibbff9c3921bd7f4f97d47cb6f10eed8ed5efe269 Signed-off-by: Damjan Marion <damarion@cisco.com>
2020-04-23nat: add/del ed_ext_ports only if the table is instantiatedDave Barach1-0/+3
Add a suitable ASSERT in the bihash template in case this happens again. Type: fix Signed-off-by: Dave Barach <dave@barachs.net> Change-Id: Ib370d4238f6bae2995bc30fd17fad5c41053c3d1
2020-04-23vppinfra: more bihash optimizatonsDamjan Marion1-54/+20
* Avoid doing expensive bit extraction for most likely case where bucket .log2_page_size == 0 and .linear_search == 0, saves 3-5 cycles for lookup, data_prefetch and add operation * use bextr instruction when available (x86 BMI instruction set) Type: improvement Change-Id: I163df36a29287482c5f133be8b21d62a2f7440de Signed-off-by: Damjan Marion <damarion@cisco.com>
2020-04-22vppinfra: improve bihash add/del performanceDamjan Marion1-19/+27
Measured improvement is from 439 to 167 clocks for add operation in 16_8 case... Type: improvement Change-Id: I975ff46ff30b983a3ec80a5cde25ccb68d7fa03b Signed-off-by: Damjan Marion <damarion@cisco.com>
2020-04-21vppinfra: bihash improvementsDave Barach1-10/+119
Template instances can allocate BIHASH_KVP_PER_PAGE data records tangent to the bucket, to remove a dependent read / prefetch. Template instances can ask for immediate memory allocation, to avoid several branches in the lookup path. Clean up l2 fib, gpb plugin codes: use clib_bihash_get_bucket(...) Use hugepages for bihash allocation arenas Type: improvement Signed-off-by: Dave Barach <dave@barachs.net> Signed-off-by: Damjan Marion <damarion@cisco.com> Change-Id: I92fc11bc58e48d84e2d61f44580916dd1c56361c
2020-03-27vppinfra: add clib_bihash_get_bucketDamjan Marion1-6/+2
Type: improvement Change-Id: I073bb7bea2a55eabbb6c253b003966f0a821e4a3 Signed-off-by: Damjan Marion <damarion@cisco.com>
2020-02-05vppinfra: numa vector placement supportDave Barach1-1/+0
Type: feature Signed-off-by: Dave Barach <dave@barachs.net> Change-Id: I7e7d95a089dd849c1f01ecea84529d8dbf239f21
2020-01-16vppinfra: fixing compilation issues in 32-bitVijayabhaskar Katamreddy1-2/+3
Fixing compilation issuues for 32-bit also setting init flag for shm based bihash Type: fix Signed-off-by: Vijayabhaskar Katamreddy <vkatamre@cisco.com> Change-Id: Ic2072c5ba7fc77d061ca9f1b844a71f6e22e58b2
2019-12-16vppinfra: bihash walk cb typedef and continue/stop controlsNeale Ranns1-3/+4
Type: feature Change-Id: I28f7a658be3f3beec9ea32635b60d1d3a10d9b06 Signed-off-by: Neale Ranns <nranns@cisco.com>
2019-09-03vppinfra: add bihash_init2Dave Barach1-20/+40
Add controls to list / not list a specific bihash in clib_all_bihashes, to immediately initialize a bihash. clib_bihash_init2 is now the primary API. It takes a typical args_t structure. clib_bihash_init becomes a compatibility widget. It fabricates an args_t and calls init2... Type: refactor Ticket: VPP-1758 Signed-off-by: Dave Barach <dave@barachs.net> Change-Id: Ib3e1304884997cf7025af20bdc67a7dda290f15b
2019-08-01vppinfra: make first bihash add thread-safeDave Barach1-7/+24
Type: fix Signed-off-by: Dave Barach <dave@barachs.net> Change-Id: Ie37ff66faba79e3b8f46c7a704137f9ef2acc773
2019-07-19vppinfra: fix OOM check in bihashAndreas Schultz1-1/+1
The OOM check must consider the end of alloced arena and not the start when checking for overflow. Type: fix Change-Id: Ie83e653d0894199d2fa433a604a0fe0cee142338 Signed-off-by: Andreas Schultz <andreas.schultz@travelping.com>
2019-07-11vppinfra: bihash add-but-do-not-overwrite semanticsDave Barach1-0/+7
If is_add=2, fail w/ return value -2 if the key exists instead of overwriting the (key,value) pair. Type: feature Change-Id: I00a3c194a381c68090369c31d6c6f9870cfe0a62 Signed-off-by: Dave Barach <dave@barachs.net>
2019-07-09vppinfra: allocate bihash virtual space on demandDave Barach1-11/+63
Reduces the vpp image virtual size by multiple gigabytes Add a "show bihash" command which displays configured and current virtual space in use by bihash tables. Modify the .py test framework to call "show bihash" on test tear-down Type: refactor Change-Id: Ifc1b7e2c43d29bbef645f6802fa29ff8ef09940c Signed-off-by: Dave Barach <dave@barachs.net>
2019-05-07bihash: Freeing up working_copy_lengths vectorVijayabhaskar Katamreddy1-1/+2
1)Freeing up working_copy_lengths vector 2)Passing vebososity level to fmt_fn Change-Id: I5e3f541e2f8cc0150105cc35835366f84937bb2e Signed-off-by: Vijayabhaskar Katamreddy <vkatamre@cisco.com>
2019-05-07Add bihash statistics hookDave Barach1-0/+18
Example / unit-test in .../src/plugins/unittest/bihash_test.c Change-Id: I23fd0ba742d65291667a755965aee1a3d3477ca2 Signed-off-by: Dave Barach <dave@barachs.net>
2019-04-17Use template-specific key compare fn when deleting recordsDave Barach1-2/+2
A simple memcmp won't work when comparing pointer-keys, such as those used by the bihash_vec8_8.h template. Change-Id: I77e59f3fd7f7740ef42908ace90ed4843e1c9ac7 Signed-off-by: Dave Barach <dave@barachs.net>
2019-03-15Fix bihash bucket double unlock.Tom Seidenberg1-2/+1
Change-Id: Icc9bef32d1bb2b8f277598c50c69343c81f22cd2 Signed-off-by: Tom Seidenberg <tseidenb@cisco.com>
2018-11-14Remove c-11 memcpy checks from perf-critical codeDave Barach1-11/+12
Change-Id: Id4f37f5d4a03160572954a416efa1ef9b3d79ad1 Signed-off-by: Dave Barach <dave@barachs.net>
2018-10-23c11 safe string handling supportDave Barach1-15/+15
Change-Id: Ied34720ca5a6e6e717eea4e86003e854031b6eab Signed-off-by: Dave Barach <dave@barachs.net>
2018-09-20bihash template: avoid memory leak upon rehashAndrew Yourtchenko1-0/+3
Call the BV (value_free) when we have performed the rehash and thus no longer need the memory that old value for the bucket refers to. Change-Id: Ibb82174fc8002aeb3e1a6c8d1f90293d73bc45d8 Signed-off-by: Andrew Yourtchenko <ayourtch@gmail.com>
2018-09-19bihash template: reinstate the check for the available memory in the arenaAndrew Yourtchenko1-1/+1
ffb14b9554afa1e58c3657e0c91dda3135008274 has changed the semantics of alloc_arena_next to become an offset off alloc_arena, but in the available memory check in BV (alloc_aligned) it still treats it as a virtual address, resulting in the check always succeeding, thus over a prolonged period bihash arena allocator potentially overwriting whatever is following the arena. Change-Id: I18882c5f340ca767a389e15cca2696a0a97ef015 Signed-off-by: Andrew Yourtchenko <ayourtch@gmail.com>
2018-09-11bihash 32/64 bit shared memory interopDave Barach1-33/+33
This patch makes 32/64 bit interoperable shared memory bihash tables work regardless of where they're mapped. Change-Id: If5b4a37ccdaa75410eba755c7d7195633de1b30b Signed-off-by: Dave Barach <dave@barachs.net>
2018-08-2832/64 shmem bihash interoperabilityDave Barach1-18/+154
Move the binary api segment above 4gb Change-Id: I40e8aa7a97722a32397f5a538b5ff8344c50d408 Signed-off-by: Dave Barach <dave@barachs.net>
2018-08-23bihash: remove unused countersDamjan Marion1-4/+0
Change-Id: I1f0aae16e4ace850d7d79b9c2c644a3e0d002636 Signed-off-by: Damjan Marion <damarion@cisco.com>
2018-08-22bihash: add support for reuse of expired entry when bucket is full (VPP-1272)Matus Fabian1-2/+30
Applications such as NAT that dynamically create entries require these entries to expire after some time. Bihash user can now lazily delete expired entries. When inserting and bucket is full, expired entry is overwritten. Change-Id: I6852305df399b546159407f1729c856afde5a634 Signed-off-by: Matus Fabian <matfabia@cisco.com>
2018-08-06fix dangling reference in foreach_key_value_pairDave Barach1-0/+7
When the user deletes the last entry in a bihash bucket, the bihash infra frees the bucket's backing storage. If this happens under clib_bihash_foreach_key_value_pair - and the freed bucket happens to be the bucket being traversed - the resulting dangling reference can easily make the wheels fall off. Simple fix: if (bucket-is-now-empty) double-break. Change-Id: Idc44247a82ed5d0ba548507b4a53d4c8503ba8bb Signed-off-by: Dave Barach <dave@barachs.net>
2018-07-20bihash: give hint to CPU that we are spinlockingDamjan Marion1-1/+1
Change-Id: I78c0a6da5d8fc63c1ced43589c42abc15ab12b16 Signed-off-by: Damjan Marion <damarion@cisco.com>
2018-07-20Fine-grained add / delete lockingDave Barach1-119/+95
Add a bucket-level lock bit. Use a spinlock only when actually allocating, freeing, or splitting a bucket. Should improve multi-thread add/del performance. Change-Id: I3e40e2a8371685457f340d6584dea14e3207f2b0 Signed-off-by: Dave Barach <dave@barachs.net>
2018-07-18vppinfra: increase max bihash arena size to 512GBDamjan Marion1-4/+4
Change-Id: Ic636297df4c03303fdcb176669f0268d80e22123 Signed-off-by: Damjan Marion <damarion@cisco.com>
2018-02-22bihash table size perf/scale improvementsDave Barach1-30/+46
Directly allocate and carve cache-line-aligned chunks of virtual memory. To a first approximation, bihash wasn't using clib_mem_free(...). We eliminate mheap object header/trailers, which improves space efficiency. We also eliminate the 4gb bihash table size limit. An 8_8 bihash w/ 100 million random entries uses 3.8 Gbytes. Change-Id: Icf925fdf99bce7d6ac407ac4edd30560b8f04808 Signed-off-by: Dave Barach <dave@barachs.net>
2018-02-08Minimize bihash memory consumptionDave Barach1-9/+46
Reference-count the number of entries in each bucket. If the reference count goes to zero, free the backing store. Add long-term churn-testing to test_bihash_template.c, thanks to Andrew Yourtchenko for the initial implementation. Change-Id: I4fbd9229cacfaba8027a85cbf87b74afdead6e39 Signed-off-by: Dave Barach <dave@barachs.net>
2018-01-24Adding a format function for bihash init routine to format the key, value, ↵Vijayabhaskar Katamreddy1-3/+20
when verbose option is used Change-Id: Ib63ead4525332f897b8a1d8a4cf5a0eb1da1e7f3 Signed-off-by: Vijayabhaskar Katamreddy <vkatamre@cisco.com>
2017-11-09lock initJingLiuZTE1-0/+1
writer_lock must be inited before used. Change-Id: Ib258aa09b3bccc4de6edba0eb75a7eec20f1a61f Signed-off-by: JingLiuZTE <liu.jing5@zte.com.cn>
2017-09-06Fixes for issues raised by Coverity (VPP-972)Chris Luke1-1/+2
Change-Id: I4b1f27b95d67d48b7a13750ff8754c344ed7afa7 Signed-off-by: Chris Luke <chrisy@flirble.org>
2017-08-31Fix BIHASH_KVP_CACHE_SIZE == 0 caseDave Barach1-1/+13
Setting the bucket-level LRU cache size to zero removes the bucket-level LRU cache code. Change-Id: Idf2e63d0d508675e957366515863766f79a3479c Signed-off-by: Dave Barach <dbarach@cisco.com>
2017-07-23Atomic bucket lockDave Barach1-13/+14
Change-Id: I84908b9ad30d7555024e98b69ed37b111f31c27a Signed-off-by: Dave Barach <dbarach@cisco.com>
2017-07-19Add a bihash prefetchable bucket-level cacheDave Barach1-8/+70
According to Maciek, the easiest way to leverage the csit "performance trend" job is to actually merge the patch once verified. Manual testing indicates that the patch improves l2 path performance. Other use-cases are TBD. It's possible that we'll need to back out the patch depending on what happens. Change-Id: Ic0a0363de35ef9be953ad7709c57c3936b73fd5a Signed-off-by: Dave Barach <dave@barachs.net>