summaryrefslogtreecommitdiffstats
path: root/docs/gettingstarted/developers
diff options
context:
space:
mode:
authorDave Barach <dave@barachs.net>2018-08-07 15:26:08 -0400
committerDave Barach <dave@barachs.net>2018-08-07 15:27:22 -0400
commitec954310e32fd254a760d3d7033326faaf693acb (patch)
tree412220514ca94921063c0bae3040ebbca7e96af2 /docs/gettingstarted/developers
parent28374cada08df61180044e24cb758fa570e73c9d (diff)
DOC ONLY: document bihash table walker rules
Change-Id: I0c48e0f4b87065d8f42009e2cc9709c6b7f5e851 Signed-off-by: Dave Barach <dave@barachs.net>
Diffstat (limited to 'docs/gettingstarted/developers')
-rw-r--r--docs/gettingstarted/developers/bihash.md35
1 files changed, 35 insertions, 0 deletions
diff --git a/docs/gettingstarted/developers/bihash.md b/docs/gettingstarted/developers/bihash.md
index 3f53e7bbc3e..a0d652f4f6c 100644
--- a/docs/gettingstarted/developers/bihash.md
+++ b/docs/gettingstarted/developers/bihash.md
@@ -257,6 +257,41 @@ To nobody's great surprise: clib_bihash_foreach_key_value_pair
iterates across the entire table, calling callback_fn with active
entries.
+#### Bihash table iteration safety
+
+The iterator template "clib_bihash_foreach_key_value_pair" must be
+used with a certain amount of care. For one thing, the iterator
+template does _not_ take the bihash hash table writer lock. If your
+use-case requires it, lock the table.
+
+For another, the iterator template is not safe under all conditions:
+
+* It's __OK to delete__ bihash table entries during a table-walk. The
+iterator checks whether the current bucket has been freed after each
+_callback_fn(...)_ invocation.
+
+* It is __not OK to add__ entries during a table-walk.
+
+The add-during-walk case involves a jackpot: while processing a
+key-value-pair in a particular bucket, add a certain number of
+entries. By luck, assume that one or more of the added entries causes
+the __current bucket__ to split-and-rehash.
+
+Since we rehash KVP's to different pages based on what amounts to a
+different hash function, either of these things can go wrong:
+
+* We may revisit previously-visited entries. Depending on how one
+coded the use-case, we could end up in a recursive-add situation.
+
+* We may skip entries that have not been visited
+
+One could build an add-safe iterator, at a significant cost in
+performance: copy the entire bucket, and walk the copy.
+
+It's hard to imagine a worthwhile add-during walk use-case in the
+first place; let alone one which couldn't be implemented by walking
+the table without modifying it, then adding a set of records.
+
### Creating a new template instance
Creating a new template is easy. Use one of the existing templates as