DPDK patches and discussions
 help / color / mirror / Atom feed
* [dpdk-dev] [PATCH 1/2] doc: add programmer's guide for the RIB library
@ 2021-11-08 17:37 Vladimir Medvedkin
  2021-11-08 17:37 ` [dpdk-dev] [PATCH 2/2] doc: add programmer's guide for the FIB library Vladimir Medvedkin
  2021-11-09 11:32 ` [dpdk-dev] [PATCH 1/2] doc: add programmer's guide for the RIB library Walsh, Conor
  0 siblings, 2 replies; 5+ messages in thread
From: Vladimir Medvedkin @ 2021-11-08 17:37 UTC (permalink / raw)
  To: dev

Currently, programmer's guide for the RIB library is missing.
This commit adds it.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 doc/guides/prog_guide/img/rib_internals.svg | 148 +++++++++++++++++
 doc/guides/prog_guide/img/rib_pic.svg       | 152 +++++++++++++++++
 doc/guides/prog_guide/index.rst             |   1 +
 doc/guides/prog_guide/rib_lib.rst           | 172 ++++++++++++++++++++
 4 files changed, 473 insertions(+)
 create mode 100644 doc/guides/prog_guide/img/rib_internals.svg
 create mode 100644 doc/guides/prog_guide/img/rib_pic.svg
 create mode 100644 doc/guides/prog_guide/rib_lib.rst

diff --git a/doc/guides/prog_guide/img/rib_internals.svg b/doc/guides/prog_guide/img/rib_internals.svg
new file mode 100644
index 0000000000..7e40046cba
--- /dev/null
+++ b/doc/guides/prog_guide/img/rib_internals.svg
@@ -0,0 +1,148 @@
+<svg width="1740.327" height="670.034" viewBox="0 0 1305.249 502.526" xml:space="preserve" color-interpolation-filters="sRGB" version="1.1" id="svg997" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg" style="fill:none;fill-rule:evenodd;font-size:12px;overflow:visible;stroke-linecap:square;stroke-miterlimit:3">
+  <style type="text/css" id="style740">
+    .st1{fill:#ff0;fill-opacity:.15;stroke:#3c63ac;stroke-width:.75}.st2,.st3{fill:#fee599;stroke:#c7c8c8;stroke-width:.25}.st3{fill:#bfbfbf}.st4{marker-end:url(#mrkr4-12);stroke:#000;stroke-linecap:round;stroke-linejoin:round;stroke-width:1}.st10{stroke-width:.25}.st6{fill:#23d127}.st6,.st7,.st8,.st9{stroke:#c7c8c8;stroke-width:.25}.st7{fill:#00b0f0}.st8{fill:red}.st9{fill:#7030a0}.st10{fill:none;stroke:none}.st11{fill:#4672c4;font-family:Calibri;font-size:1.5em}.st12{font-size:1em}
+  </style>
+  <defs id="Markers">
+    <marker id="mrkr4-12" refX="-7.04" orient="auto" markerUnits="strokeWidth" overflow="visible" style="fill:#000;fill-opacity:1;stroke:#000;stroke-opacity:1;stroke-width:.28409090909091">
+      <use xlink:href="#lend4" transform="scale(-3.52)" id="use745" x="0" y="0" width="100%" height="100%"/>
+    </marker>
+    <g id="lend4">
+      <path d="M2 1 0 0l2-1v2" style="stroke:none" id="path742"/>
+    </g>
+  </defs>
+  <g id="g995" transform="translate(-217.077 -27.932)">
+    <g id="shape1025-1" transform="translate(504.643 -65.197)">
+      <path d="M583.63 595.28 290.41 324.57 0 595.28Z" class="st1" id="path753"/>
+    </g>
+    <g id="shape2-3" transform="translate(992.354 -368.504)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path758"/>
+    </g>
+    <g id="shape3-5" transform="translate(1182.05 -467.717)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path763"/>
+    </g>
+    <g id="shape8-7" transform="translate(1190.35 -476.016)">
+      <path d="m0 595.28-143.05 56.53" class="st4" id="path768"/>
+    </g>
+    <g id="shape22-13" transform="translate(1094.1 -297.638)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path773"/>
+    </g>
+    <g id="shape31-15" transform="translate(1366.3 -368.504)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path778"/>
+    </g>
+    <g id="shape33-17" transform="translate(1465.51 -297.638)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path783"/>
+    </g>
+    <g id="shape36-19" transform="translate(1230.44 -476.016)">
+      <path d="m0 595.28 137.65 56.44" class="st4" id="path788"/>
+    </g>
+    <g id="shape1000-24" transform="translate(881.803 -297.638)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path793"/>
+    </g>
+    <g id="shape1002-26" transform="translate(994.885 -226.772)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st6" id="path798"/>
+    </g>
+    <g id="shape1006-28" transform="translate(1257.06 -297.638)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path803"/>
+    </g>
+    <g id="shape1007-30" transform="translate(1153.7 -226.772)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path808"/>
+    </g>
+    <g id="shape1008-32" transform="translate(1366.3 -226.772)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path813"/>
+    </g>
+    <g id="shape1012-34" transform="translate(768.113 -226.772)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path818"/>
+    </g>
+    <g id="shape1013-36" transform="translate(668.9 -155.906)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st7" id="path823"/>
+    </g>
+    <g id="shape1018-38" transform="translate(868.818 -155.906)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st8" id="path828"/>
+    </g>
+    <g id="shape1019-40" transform="translate(769.125 -85.04)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st9" id="path833"/>
+    </g>
+    <g id="shape1026-42" transform="translate(238.475 -510.236)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path838"/>
+    </g>
+    <g id="shape1027-44" transform="translate(238.475 -439.37)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path843"/>
+    </g>
+    <g id="shape1028-46" transform="translate(238.475 -368.504)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st6" id="path848"/>
+    </g>
+    <g id="shape1029-48" transform="translate(238.475 -297.638)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st7" id="path853"/>
+    </g>
+    <g id="shape1030-50" transform="translate(238.475 -226.772)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st8" id="path858"/>
+    </g>
+    <g id="shape1031-52" transform="translate(238.475 -155.906)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st9" id="path863"/>
+    </g>
+    <g id="shape1032-54" transform="translate(300.688 -518.013)">
+      <path class="st10" id="rect870" d="M0 554.136h164.559v41.14H0z"/>
+      <text x="13.67" y="580.11" class="st11" id="text872">Intermediate node</text>
+    </g>
+    <g id="shape1033-57" transform="translate(300.688 -447.147)">
+      <path class="st10" id="rect879" d="M0 554.136h164.559v41.14H0z"/>
+      <text x="15.71" y="569.31" class="st11" id="text883">Node containing a <tspan x="62.17" dy="1.2em" class="st12" id="tspan881">route</tspan></text>
+    </g>
+    <g id="shape1034-61" transform="translate(300.688 -376.281)">
+      <path class="st10" id="rect890" d="M0 554.136h164.559v41.14H0z"/>
+      <text x="35.5" y="580.11" class="st11" id="text892">10.15.0.0/23</text>
+    </g>
+    <g id="shape1035-64" transform="translate(300.688 -305.414)">
+      <path class="st10" id="rect899" d="M0 554.136h164.559v41.14H0z"/>
+      <text x="40.06" y="580.11" class="st11" id="text901">10.0.0.0/29</text>
+    </g>
+    <g id="shape1036-67" transform="translate(300.688 -234.548)">
+      <path class="st10" id="rect908" d="M0 554.136h164.559v41.14H0z"/>
+      <text x="30.93" y="580.11" class="st11" id="text910">10.0.0.128/25</text>
+    </g>
+    <g id="shape1037-70" transform="translate(300.688 -163.682)">
+      <path class="st10" id="rect917" d="M0 554.136h164.559v41.14H0z"/>
+      <text x="30.93" y="580.11" class="st11" id="text919">10.0.0.160/27</text>
+    </g>
+    <g id="shape1038-73" transform="translate(218.008 -100.593)">
+      <path d="m85.56 595.28-42.78-41.14L0 595.28Z" class="st1" id="path924"/>
+    </g>
+    <g id="shape1039-75" transform="translate(308.827 -92.816)">
+      <path class="st10" id="rect931" d="M0 554.136h164.559v41.14H0z"/>
+      <text x="8.82" y="558.51" class="st11" id="text937">Routes falling under <tspan x="5.62" dy="1.2em" class="st12" id="tspan933">common 10.0.0.0/24 </tspan><tspan x="61.23" dy="1.2em" class="st12" id="tspan935">prefix</tspan></text>
+    </g>
+    <g id="shape1040-80" transform="translate(1374.6 -376.804)">
+      <path d="m0 595.28-62.71 27.91" class="st4" id="path942"/>
+    </g>
+    <g id="shape1041-85" transform="translate(1414.69 -376.804)">
+      <path d="m0 595.28 52.87 27.52" class="st4" id="path947"/>
+    </g>
+    <g id="shape1042-90" transform="translate(1305.46 -305.938)">
+      <path d="m0 595.28 62.71 27.91" class="st4" id="path952"/>
+    </g>
+    <g id="shape1043-95" transform="translate(1265.36 -305.938)">
+      <path d="m0 595.28-56.94 27.69" class="st4" id="path957"/>
+    </g>
+    <g id="shape1044-100" transform="translate(1040.75 -376.804)">
+      <path d="m0 595.28 55.35 27.62" class="st4" id="path962"/>
+    </g>
+    <g id="shape1045-105" transform="translate(1000.65 -376.804)">
+      <path d="m0 595.28-64.01 27.95" class="st4" id="path967"/>
+    </g>
+    <g id="shape1046-110" transform="translate(930.196 -305.938)">
+      <path d="m0 595.28 66.5 28.03" class="st4" id="path972"/>
+    </g>
+    <g id="shape1047-115" transform="translate(890.102 -305.938)">
+      <path d="m0 595.28-67.1 28.05" class="st4" id="path977"/>
+    </g>
+    <g id="shape1048-120" transform="translate(816.506 -235.071)">
+      <path d="m0 595.28 54.33 27.58" class="st4" id="path982"/>
+    </g>
+    <g id="shape1049-125" transform="translate(776.413 -235.071)">
+      <path d="m0 595.28-52.87 27.52" class="st4" id="path987"/>
+    </g>
+    <g id="shape1050-130" transform="translate(877.117 -164.205)">
+      <path d="m0 595.28-53.34 27.54" class="st4" id="path992"/>
+    </g>
+  </g>
+</svg>
diff --git a/doc/guides/prog_guide/img/rib_pic.svg b/doc/guides/prog_guide/img/rib_pic.svg
new file mode 100644
index 0000000000..8a8b176502
--- /dev/null
+++ b/doc/guides/prog_guide/img/rib_pic.svg
@@ -0,0 +1,152 @@
+<svg width="1280.324" height="563.481" viewBox="0 0 960.246 422.611" xml:space="preserve" color-interpolation-filters="sRGB" version="1.1" id="svg249" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg" style="fill:none;fill-rule:evenodd;font-size:12px;overflow:visible;stroke-linecap:square;stroke-miterlimit:3">
+  <style type="text/css" id="style9">
+    .st1{fill:#eb94e0}.st1,.st2,.st3{stroke:#c7c8c8;stroke-width:.25}.st2{fill:#bfbfbf}.st3{fill:#00b0f0}.st4{marker-end:url(#mrkr4-16);stroke:#000;stroke-linecap:round;stroke-linejoin:round;stroke-width:1}.st7{fill:#00b0f0;fill-opacity:1;stroke:#00b0f0;stroke-opacity:1;stroke-width:.28409090909091}.st8,.st9{marker-end:url(#mrkr4-113);stroke:#00b0f0;stroke-linecap:round;stroke-linejoin:round;stroke-width:1}.st9{marker-end:url(#mrkr4-129);stroke:#eb94e0}.st11{fill:none;stroke:none;stroke-width:.25}.st12{fill:#4672c4;font-family:Calibri;font-size:1.5em}
+  </style>
+  <defs id="Markers">
+    <marker id="mrkr4-16" refX="-7.04" orient="auto" markerUnits="strokeWidth" overflow="visible" style="fill:#000;fill-opacity:1;stroke:#000;stroke-opacity:1;stroke-width:.28409090909091">
+      <use xlink:href="#lend4" transform="scale(-3.52)" id="use14" x="0" y="0" width="100%" height="100%"/>
+    </marker>
+    <marker id="mrkr4-107" class="st7" refX="-7.04" orient="auto" markerUnits="strokeWidth" overflow="visible">
+      <use xlink:href="#lend4" transform="scale(-3.52)" id="use17" x="0" y="0" width="100%" height="100%"/>
+    </marker>
+    <marker id="mrkr4-113" class="st7" refX="-6.68" orient="auto" markerUnits="strokeWidth" overflow="visible">
+      <use xlink:href="#lend4" transform="scale(-3.52)" id="use20" x="0" y="0" width="100%" height="100%"/>
+    </marker>
+    <marker id="mrkr4-129" refX="-6.68" orient="auto" markerUnits="strokeWidth" overflow="visible" style="fill:#eb94e0;fill-opacity:1;stroke:#eb94e0;stroke-opacity:1;stroke-width:.28409090909091">
+      <use xlink:href="#lend4" transform="scale(-3.52)" id="use23" x="0" y="0" width="100%" height="100%"/>
+    </marker>
+    <g id="lend4">
+      <path d="M2 1 0 0l2-1v2" style="stroke:none" id="path11"/>
+    </g>
+  </defs>
+  <g id="g247" transform="translate(-624.44 -59.113)">
+    <g id="shape1000-1" transform="translate(1428.66 -396.85)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path31"/>
+    </g>
+    <g id="shape1001-3" transform="translate(1527.87 -325.984)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path36"/>
+    </g>
+    <g id="shape1002-5" transform="translate(1319.43 -325.984)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path41"/>
+    </g>
+    <g id="shape1003-7" transform="translate(1216.06 -255.118)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path46"/>
+    </g>
+    <g id="shape1004-9" transform="translate(1428.66 -255.118)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path51"/>
+    </g>
+    <g id="shape1005-11" transform="translate(1436.96 -405.15)">
+      <path d="m0 595.28-62.71 27.91" class="st4" id="path56"/>
+    </g>
+    <g id="shape1006-17" transform="translate(1477.05 -405.15)">
+      <path d="m0 595.28 52.87 27.52" class="st4" id="path61"/>
+    </g>
+    <g id="shape1007-22" transform="translate(1367.82 -334.284)">
+      <path d="m0 595.28 62.71 27.91" class="st4" id="path66"/>
+    </g>
+    <g id="shape1008-27" transform="translate(1327.73 -334.284)">
+      <path d="m0 595.28-56.94 27.69" class="st4" id="path71"/>
+    </g>
+    <g id="shape1009-32" transform="translate(1230.24 -479.055)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path76"/>
+    </g>
+    <g id="shape1010-34" transform="translate(1031.81 -396.85)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path81"/>
+    </g>
+    <g id="shape1011-36" transform="translate(1131.02 -325.984)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path86"/>
+    </g>
+    <g id="shape1014-38" transform="translate(1080.2 -405.15)">
+      <path d="m0 595.28 52.87 27.52" class="st4" id="path91"/>
+    </g>
+    <g id="shape1015-43" transform="translate(1238.54 -487.355)">
+      <path d="m0 595.28-151.53 40.3" class="st4" id="path96"/>
+    </g>
+    <g id="shape1016-48" transform="translate(1278.63 -487.355)">
+      <path d="m0 595.28 151.53 40.3" class="st4" id="path101"/>
+    </g>
+    <g id="shape1017-53" transform="translate(922.779 -325.984)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path106"/>
+    </g>
+    <g id="shape1019-55" transform="translate(813.543 -255.118)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path111"/>
+    </g>
+    <g id="shape1020-57" transform="translate(931.079 -334.284)">
+      <path d="m0 595.28-62.71 27.91" class="st4" id="path116"/>
+    </g>
+    <g id="shape1022-62" transform="translate(1022.65 -255.118)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path121"/>
+    </g>
+    <g id="shape1023-64" transform="translate(1121.86 -184.252)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path126"/>
+    </g>
+    <g id="shape1026-66" transform="translate(1071.04 -263.418)">
+      <path d="m0 595.28 52.87 27.52" class="st4" id="path131"/>
+    </g>
+    <g id="shape1027-71" transform="translate(1040.11 -405.15)">
+      <path d="m0 595.28-62.51 27.9" class="st4" id="path136"/>
+    </g>
+    <g id="shape1028-76" transform="translate(971.172 -334.284)">
+      <path d="m0 595.28 53.52 27.55" class="st4" id="path141"/>
+    </g>
+    <g id="shape1029-81" transform="translate(914.275 -184.252)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path146"/>
+    </g>
+    <g id="shape1030-83" transform="translate(1013.49 -113.386)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path151"/>
+    </g>
+    <g id="shape1031-85" transform="translate(805.039 -113.386)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path156"/>
+    </g>
+    <g id="shape1032-87" transform="translate(922.575 -192.552)">
+      <path d="m0 595.28-62.71 27.91" class="st4" id="path161"/>
+    </g>
+    <g id="shape1033-92" transform="translate(962.668 -192.552)">
+      <path d="m0 595.28 52.87 27.52" class="st4" id="path166"/>
+    </g>
+    <g id="shape1034-97" transform="translate(1030.95 -263.418)">
+      <path d="m0 595.28-61.86 27.88" class="st4" id="path171"/>
+    </g>
+    <g id="shape1035-102" transform="translate(861.732 -134.646)">
+      <path d="M0 588.19h144.72" id="path176" style="marker-end:url(#mrkr4-107);stroke:#00b0f0;stroke-linecap:round;stroke-linejoin:round;stroke-width:1"/>
+    </g>
+    <g id="shape1036-108" transform="translate(1061.88 -161.779)">
+      <path d="M0 595.28c17.07 0 45.07 0 57.76-6.9 7.54-4.1 9.68-10.64 10.28-16.84l.01-.36" class="st8" id="path181"/>
+    </g>
+    <g id="shape1037-114" transform="translate(1147.7 -240.945)">
+      <path d="M2.51 595.28c0-21.26 4.17-21.26 6.44-27.88 2.51-7.31 2.7-22.68 2.72-50.12v-.36" class="st8" id="path186"/>
+    </g>
+    <g id="shape1038-119" transform="translate(1187.72 -354.331)">
+      <path d="M0 595.28c104.41 0 106.27 68.37 233.91 70.8h.36" class="st8" id="path191"/>
+    </g>
+    <g id="shape1039-124" transform="translate(870.236 -283.465)">
+      <path d="M0 595.28c19.54 0 21.12 42.91 45.36 49.87l.36.05" class="st9" id="path196"/>
+    </g>
+    <g id="shape1040-130" transform="translate(942.622 -240.945)">
+      <path d="M0 595.28c0-63.78 30.02-63.78 44.53-77.43 13.58-12.76 13.58-37.48 31.95-48.45 12.86-7.69 34.73-8.64 39.92-23.08l.06-.36" class="st9" id="path201"/>
+    </g>
+    <g id="shape1041-135" transform="translate(1088.5 -425.197)">
+      <path d="M0 595.28c38.98 0 99.97 0 129.15 23.13 24.61 19.52 26.58 55.51 26.74 83.21v.36" class="st9" id="path206"/>
+    </g>
+    <g id="shape1042-140" transform="translate(1272.76 -283.465)">
+      <path d="M0 595.28c15.13 0 20.44 0 23.89-5.12 6.37-9.46 6.37-36.42 6.37-61.42 0-27.19 0-52.06 16.86-64.04 15.08-10.73 43.68-11.14 101.75-11.16h.36" class="st9" id="path211"/>
+    </g>
+    <g id="shape1043-145" transform="translate(1485.35 -425.197)">
+      <path d="M0 595.28c17.72 0 46.05 0 59.28 9.06 9.19 6.29 11.09 16.97 11.48 26.42l.01.36" class="st9" id="path216"/>
+    </g>
+    <g id="shape1044-150" transform="translate(624.567 -479.055)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path221"/>
+    </g>
+    <g id="shape1045-152" transform="translate(624.567 -379.843)">
+      <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path226"/>
+    </g>
+    <g id="shape1046-154" transform="translate(695.501 -493.654)">
+      <path class="st11" id="rect233" d="M0 567.78h90.709v27.496H0z"/>
+      <text x="4.67" y="586.93" class="st12" id="text235">Next hop A</text>
+    </g>
+    <g id="shape1047-157" transform="translate(697.019 -394.441)">
+      <path class="st11" id="rect242" d="M0 567.78h90.709v27.496H0z"/>
+      <text x="4.99" y="586.93" class="st12" id="text244">Next hop B</text>
+    </g>
+  </g>
+</svg>
diff --git a/doc/guides/prog_guide/index.rst b/doc/guides/prog_guide/index.rst
index 89af28dacb..0a53ec71c8 100644
--- a/doc/guides/prog_guide/index.rst
+++ b/doc/guides/prog_guide/index.rst
@@ -38,6 +38,7 @@ Programmer's Guide
     member_lib
     lpm_lib
     lpm6_lib
+    rib_lib
     flow_classify_lib
     packet_distrib_lib
     reorder_lib
diff --git a/doc/guides/prog_guide/rib_lib.rst b/doc/guides/prog_guide/rib_lib.rst
new file mode 100644
index 0000000000..e8bb35a2b6
--- /dev/null
+++ b/doc/guides/prog_guide/rib_lib.rst
@@ -0,0 +1,172 @@
+..  SPDX-License-Identifier: BSD-3-Clause
+    Copyright(c) 2021 Intel Corporation.
+
+RIB Library
+===========
+
+The Routing Information Base (RIB) library provides a data store for routing information.
+This library is intended for use in control or management plane applications.
+There are more suitable libraries for use in data plane applications such as
+:ref:`LPM <LPM_Library>` or FIB.
+
+
+Implementation details
+----------------------
+
+RIB implements a key-value store for routing information.
+
+Routing information is represented by a prefix (key) and a next hop ID (value).
+The prefix type depends on the address family. IPv4 addresses are represented by
+``uint32_t`` values. IPv6 addresses are represented as ``uint8_t[16]`` values.
+Next hop IDs are represented by ``uint64_t`` values.
+
+.. note::
+
+   The API and implementation are very similar for IPv4's ``rib`` library and IPv6's ``rib6``
+   library, therefore only the ``rib`` library will be discussed here.
+   Everything within this document except for the size of the prefixes is applicable to  the
+   ``rib6`` library.
+
+Internally RIB is represented as a binary tree as shown in :numref:`figure_rib_internals`:
+
+.. _figure_rib_internals:
+
+.. figure:: img/rib_internals.*
+
+   RIB internals overview
+
+The binary tree consists of two types of nodes:
+
+* Actual Routes.
+
+* Intermediate Nodes which are used internally to preserve the binary tree structure.
+
+
+RIB API Overview
+----------------
+
+RIB has two configuration parameters:
+
+* The maximum number of nodes.
+
+* The size of the extension block within each node. This space is used to store
+  additional user defined data.
+
+The main methods within the ``rib`` library are:
+
+* ``rte_rib_insert()``: Add new routes.
+
+* ``rte_rib_remove()``: Delete an existing route.
+
+* ``rte_rib_lookup()``: Lookup an IP in the structure using longest match.
+
+* ``rte_rib_lookup_exact()``: Lookup an IP in the structure using exact match.
+
+* ``rte_rib_lookup_parent()``: Find a parent prefix within the structure.
+
+* ``rte_rib_get_nxt()``: Traverse a subtree within the structure.
+
+Given a RIB structure with the routes depicted in :numref:`figure_rib_internals`,
+here are several usage examples:
+
+* The best route for ``10.0.0.1`` can be found by calling:
+
+.. code-block:: c
+
+      struct rte_rib_node *route = rte_rib_lookup(rib, RTE_IPV4(10,0,0,1));
+
+This returns an ``rte_rib_node`` pointing to the ``10.0.0.0/29`` prefix.
+
+* To find an exact match route:
+
+.. code-block:: c
+
+      struct rte_rib_node *route = rte_rib_lookup_exact(rib, RTE_IPV4(10,0,0,128), 25);
+
+This returns an ``rte_rib_node`` pointing to the ``10.0.0.128/25`` prefix.
+
+and
+
+.. code-block:: c
+
+      struct rte_rib_node *route = rte_rib_lookup_exact(rib, RTE_IPV4(10,0,0,0), 24);
+
+This returns ``NULL`` as no exact match can be found.
+
+* To retrieve a group of routes under the common prefix ``10.0.0.0/24``
+  (yellow triangle in :numref:`figure_rib_internals`):
+
+.. code-block:: c
+
+      struct rte_rib_node *route = NULL;
+      do {
+         route = rte_rib_get_nxt(rib, RTE_IPV4(10,0,0,0), 24, route, RTE_RIB_GET_NXT_ALL);
+      } while (route != NULL)
+
+This returns 3 ``rte_rib_node`` nodes pointing to ``10.0.0.0/29``, ``10.0.0.160/27``
+and ``10.0.0.128/25``.
+
+Extensions usage example
+------------------------
+
+Extensions can be used for a wide range of tasks.
+By default, an ``rte_rib_node`` node contains only crucial information such as the prefix and
+next hop ID, but it doesn't contain protocol specific information such as
+metrics, administrative distance and other routing protocol information.
+These examples are application specific data and the user can decide what to keep
+and how it is stored within the extension memory region in each ``rte_rib_node``.
+
+It is possible to implement a prefix independent convergence using the RIB extension feature.
+If the routing daemon can provide a feasible next hop ID along with a best (active) next hop ID,
+it is possible to react to a neighbour failing relatively fast.
+Consider a RIB with a number of routes with different next hops (A and B) as
+shown in :numref:`figure_rib_pic`. Every route can have a feasible next hop
+provided by the routing daemon.
+
+.. _figure_rib_pic:
+
+.. figure:: img/rib_pic.*
+
+   RIB prefix independent convergence
+
+In case of a next hop failure, we need to replace an active failed next hop with a
+feasible next hop for every corresponding route without waiting for the routing daemon
+recalculation process to complete.
+To achieve this we can link all existing routes with the same active next hop in a linked list,
+saving the feasible next hop ID and a pointer inside the extension space of each ``rte_rib_node``.
+
+.. code-block:: c
+
+      struct my_route_ext {
+         struct rte_rib_node *next;
+         uint64_t feasible_nh;
+      };
+
+      struct rte_rib_conf conf;
+      conf.ext_sz = sizeof(struct my_route_ext);
+      rib = rte_rib_create("test", 0, &conf);
+      ...
+      /* routing daemon task */
+      struct rte_rib_node *route = rte_rib_insert(rib, RTE_IPV4(192,0,2,0), 24);
+      rte_rib_set_nh(route, active_nh_from_rd);
+      struct my_route_ext *ext = rte_rib_get_ext(route);
+      ext->feasible_nh = feasible_nh_from_rd;
+      list_insert(nh_table[active_nh_from_rd].list_head, route);
+      ...
+      /* dataplane monitoring thread */
+      /* nexthop id fail_nh fails */
+      route = NULL;
+      do {
+         route = get_next(nh_table[fail_nh].list_head, route);
+         uint32_t ip;
+         uint8_t depth;
+         rte_rib_get_ip(route, &ip);
+         rte_rib_get_depth(route, &depth);
+         ext = rte_rib_get_ext(route);
+         uint64_t new_nh = ext->feasible_nh;
+         /* do update to the dataplane, for example to the fib */
+         rte_fib_add(fib, ip, depth, new_nh);
+         /* update nexthop if necessary */
+         rte_rib_set_nh(route, new_nh);
+      } while (route != NULL);
+
-- 
2.25.1


^ permalink raw reply	[flat|nested] 5+ messages in thread

* [dpdk-dev] [PATCH 2/2] doc: add programmer's guide for the FIB library
  2021-11-08 17:37 [dpdk-dev] [PATCH 1/2] doc: add programmer's guide for the RIB library Vladimir Medvedkin
@ 2021-11-08 17:37 ` Vladimir Medvedkin
  2021-11-09 11:32   ` Walsh, Conor
  2021-11-09 11:32 ` [dpdk-dev] [PATCH 1/2] doc: add programmer's guide for the RIB library Walsh, Conor
  1 sibling, 1 reply; 5+ messages in thread
From: Vladimir Medvedkin @ 2021-11-08 17:37 UTC (permalink / raw)
  To: dev

Currently, programmer's guide for the FIB library is missing.
This commit adds it.

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 doc/guides/prog_guide/fib_lib.rst          | 139 +++++++++++++++++++++
 doc/guides/prog_guide/img/dir_24_8_alg.svg | 136 ++++++++++++++++++++
 doc/guides/prog_guide/index.rst            |   1 +
 doc/guides/prog_guide/rib_lib.rst          |   2 +-
 4 files changed, 277 insertions(+), 1 deletion(-)
 create mode 100644 doc/guides/prog_guide/fib_lib.rst
 create mode 100644 doc/guides/prog_guide/img/dir_24_8_alg.svg

diff --git a/doc/guides/prog_guide/fib_lib.rst b/doc/guides/prog_guide/fib_lib.rst
new file mode 100644
index 0000000000..4aa02e1ed9
--- /dev/null
+++ b/doc/guides/prog_guide/fib_lib.rst
@@ -0,0 +1,139 @@
+..  SPDX-License-Identifier: BSD-3-Clause
+    Copyright(c) 2021 Intel Corporation.
+
+.. _FIB_Library:
+
+FIB Library
+===========
+
+The FIB library provides a fast Longest Prefix Match (LPM) search for 32-bit
+keys or 128-bit for IPv6. It can be used in a variety of applications,
+the most typical of which is IPv4/IPv6 forwarding.
+
+.. note::
+
+   The API and implementation are very similar for IPv4's ``fib`` library and
+   IPv6's ``fib6`` library, therefore only the ``fib`` library will be discussed here.
+   Everything within this document except for the size of the prefixes applies
+   to the ``rib6`` library.
+
+FIB API Overview
+----------------
+
+The main configuration struct contains:
+
+* Type of :ref:`dataplane algorithm <fib_dataplane_algorithms>`.
+
+* Default next hop ID.
+
+* The maximum number of routes.
+
+* Settings for the data algorithm (:ref:`will be discussed later <fib_dataplane_algorithms>`).
+
+A FIB rule consists of a prefix and an associated next hop ID. The prefix consists
+of an IPv4 network address (``uint32_t``) and the corresponding prefix length.
+The prefix serves as the key and the next hop ID as the value while doing an LPM
+search within FIB. The size of the next hop ID is variable and must be configured
+during initialization.
+
+The main methods within the ``fib`` library are:
+
+* ``rte_fib_add()``: Add a new route with a corresponding next hop ID to the
+  table or update the next hop ID if the prefix already exists in a table.
+
+* ``rte_fib_delete()``: Delete an existing route from the table.
+
+* ``rte_fib_lookup_bulk()``: Provides a bulk Longest Prefix Match (LPM) lookup function
+  for a set of IP addresses, it will return a set of corresponding next hop IDs.
+
+
+Implementation details
+----------------------
+
+Internally FIB contains the ``rte_rib`` data struct to help maintain the dataplane struct.
+The dataplane struct is opaque, so that users can add their own algorithm implementations.
+
+
+.. _fib_dataplane_algorithms:
+
+Dataplane Algorithms
+--------------------
+
+Dummy
+~~~~~
+
+This algorithm uses ``rte_rib`` as a dataplane struct. Lookups are relatively slow,
+but extra memory isn't used for the dataplane struct. This algorithm should only
+be used for testing and debugging purposes.
+
+This algorithm will be used if the ``RTE_FIB_DUMMY`` type is configured as the
+dataplane algorithm on FIB creation.
+
+
+DIR-24-8
+~~~~~~~~
+
+The current implementation of this algorithm uses a variation of the DIR-24-8
+algorithm that trades memory usage for improved LPM lookup speed.
+This algorithm allows the lookup operation to be performed using only a single
+memory read access in most cases. In the statistically rare case where the best
+match rule has a depth larger than 24, the lookup operation will require two
+memory read accesses.
+
+This algorithm will be used if the ``RTE_FIB_DIR24_8`` type is configured as the
+dataplane algorithm on FIB creation.
+
+The main FIB configuration struct stores the dataplane parameters inside ``dir24_8``
+within the ``rte_fib_conf`` and it consists of:
+
+* ``nh_sz``: The size of the entry containing the next hop ID.
+  This could be 1, 2, 4 or 8 bytes long.
+  Note that all available bits except one are used to store the actual next hop ID.
+
+* ``num_tbl8``: The number of tbl8 groups, each group consists of 256 entries
+  corresponding to the ``nh_sz`` size.
+
+The main elements of the dataplane struct for the DIR-24-8 algorithm are:
+
+* TBL24: An array with 2\ :sup:`24` entries, corresponding to the ``nh_sz`` size.
+
+* TBL8: An array of ``num_tbl8`` tbl8 groups.
+
+The lookup algorithms logic can be seen in :numref:`figure_dir_24_8_alg`:
+
+.. _figure_dir_24_8_alg:
+
+.. figure:: img/dir_24_8_alg.*
+
+   DIR-24-8 Lookup algorithm
+
+The first table ``tbl24``, is indexed using the first 24 bits of the IP address to be looked up,
+while the second table(s) ``tbl8``, is indexed using the last 8 bits of the IP address.
+This means that depending on the outcome of trying to match the IP address of an incoming packet
+to a rule stored in the tbl24 we might need to continue the lookup process in the second level.
+
+Since every entry of the tbl24 can potentially point to a tbl8,
+ideally we would have 2\ :sup:`24` tbl8s, which would be the same as having a
+single table with 2\ :sup:`32` entries. This is not feasible due to resource restrictions.
+Instead, this approach takes advantage of the fact that rules longer than 24 bits are very rare.
+By splitting the process into two different tables/levels and limiting the number of tbl8s,
+we can greatly reduce memory consumption while maintaining a very good lookup speed.
+This method generally results in one memory access per lookup.
+
+An entry in a tbl8 contains the following fields:
+
+* The next hop ID.
+
+* 1 bit indicating if the lookup should proceed inside the tbl8.
+
+Use cases
+---------
+
+The FIB library is useful for any use cases that rely on the Longest Prefix Match (LPM)
+algorithm such as IP forwarding or packet classification.
+
+More complex use cases are also possible, as it is possible to have next hop IDs
+which are 63 bits long (using ``RTE_FIB_DIR24_8_8B`` as a next hop size).
+These use cases could include storing two next hop IDs inside the 63 bits of the next hop.
+This may be useful to provide a fallback next hop ID, ASN or forwarding class
+corresponding to a given prefix without having to perform an additional lookup.
diff --git a/doc/guides/prog_guide/img/dir_24_8_alg.svg b/doc/guides/prog_guide/img/dir_24_8_alg.svg
new file mode 100644
index 0000000000..17725b7b97
--- /dev/null
+++ b/doc/guides/prog_guide/img/dir_24_8_alg.svg
@@ -0,0 +1,136 @@
+<svg width="945.881" height="658.889" viewBox="0 0 709.411 494.167" xml:space="preserve" color-interpolation-filters="sRGB" version="1.1" id="svg220" style="fill:none;fill-rule:evenodd;font-size:12px;overflow:visible;stroke-linecap:square;stroke-miterlimit:3" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg">
+  <style type="text/css" id="style2">
+    .st1{fill:url(#grad0-4);stroke:#3c63ac;stroke-width:.749999}.st2{fill:#3c63ac;font-family:Calibri;font-size:1.16666em}.st3{marker-end:url(#mrkr4-55);stroke:#4672c4;stroke-linecap:round;stroke-linejoin:round;stroke-width:.999999}.st5{fill:url(#grad0-4);stroke:#3d64ac;stroke-width:.749999}.st6{fill:#3d64ac;font-family:Calibri;font-size:1.16666em}.st8,.st9{stroke:none}.st8{fill:#fff;stroke-linecap:butt;stroke-width:7.2}.st9{fill:none;stroke-width:.25}.st10{fill:#4672c4;font-family:Calibri;font-size:1.16666em;font-weight:700}
+  </style>
+  <defs id="Patterns_And_Gradients">
+    <linearGradient id="grad0-4" x1="0" y1="0" x2="1" y2="0">
+      <stop offset="0" stop-color="#e8ebf4" stop-opacity="1" id="stop4"/>
+      <stop offset=".24" stop-color="#f4f5f9" stop-opacity="1" id="stop6"/>
+      <stop offset=".54" stop-color="#feffff" stop-opacity="1" id="stop8"/>
+    </linearGradient>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient224" x1="-.573" y1="46.345" x2="277.982" y2="46.345" gradientTransform="scale(.65397 1.52912)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient226" x1="-.185" y1="928.807" x2="75.865" y2="928.807" gradientTransform="scale(2.02261 .49441)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient228" x1="-.185" y1="928.807" x2="75.865" y2="928.807" gradientTransform="scale(2.02261 .49441)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient230" x1="-.185" y1="928.807" x2="75.865" y2="928.807" gradientTransform="scale(2.02261 .49441)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient232" x1="-.185" y1="928.807" x2="75.865" y2="928.807" gradientTransform="scale(2.02261 .49441)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient234" x1="-.185" y1="928.807" x2="75.865" y2="928.807" gradientTransform="scale(2.02261 .49441)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient236" x1="-.185" y1="928.807" x2="75.865" y2="928.807" gradientTransform="scale(2.02261 .49441)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient238" x1="-.185" y1="928.807" x2="75.865" y2="928.807" gradientTransform="scale(2.02261 .49441)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient240" x1="-.378" y1="309.413" x2="183.201" y2="309.413" gradientTransform="scale(.9923 1.00775)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient242" x1="-.185" y1="928.807" x2="75.865" y2="928.807" gradientTransform="scale(2.02261 .49441)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient244" x1="-.185" y1="928.807" x2="75.865" y2="928.807" gradientTransform="scale(2.02261 .49441)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient246" x1="-.185" y1="928.807" x2="75.865" y2="928.807" gradientTransform="scale(2.02261 .49441)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient248" x1="-.181" y1="987.935" x2="42.539" y2="987.935" gradientTransform="scale(2.07454 .48204)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient250" x1="-.315" y1="566.074" x2="24.162" y2="566.074" gradientTransform="scale(1.18868 .84127)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient252" x1="-.565" y1="550.271" x2="90.593" y2="550.271" gradientTransform="scale(1.29092 .77464)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient254" x1="-.181" y1="987.935" x2="42.539" y2="987.935" gradientTransform="scale(2.07454 .48204)" gradientUnits="userSpaceOnUse"/>
+    <linearGradient xlink:href="#grad0-4" id="linearGradient256" x1="-.204" y1="834.253" x2="79.387" y2="834.253" gradientTransform="scale(1.83941 .54365)" gradientUnits="userSpaceOnUse"/>
+  </defs>
+  <defs id="Markers">
+    <marker id="mrkr4-55" refX="0" orient="auto" markerUnits="strokeWidth" overflow="visible" style="fill:#4672c4;fill-opacity:1;stroke:#4672c4;stroke-opacity:1;stroke-width:.28409061414099">
+      <use xlink:href="#lend4" transform="scale(-3.52)" id="use15" x="0" y="0" width="100%" height="100%"/>
+    </marker>
+    <g id="lend4">
+      <path d="M2 1 0 0l2-1v2" style="stroke:none" id="path12"/>
+    </g>
+  </defs>
+  <g id="g218" transform="translate(0 -2.27)">
+    <g id="shape1-1" transform="translate(113.761 -.375)">
+      <path class="st1" id="rect23" style="fill:url(#linearGradient224)" d="M0 71.242h181.417v425.196H0z"/>
+    </g>
+    <g id="shape2-5" transform="translate(127.934 -374.549)">
+      <path class="st1" id="rect30" style="fill:url(#linearGradient226)" d="M0 459.587h153.071v36.85H0z"/>
+      <text x="25.03" y="482.21" class="st2" id="text32">uint[8,16,32,64]_t</text>
+    </g>
+    <g id="shape3-9" transform="translate(127.934 -332.029)">
+      <path class="st1" id="rect37" style="fill:url(#linearGradient228)" d="M0 459.587h153.071v36.85H0z"/>
+    </g>
+    <g id="shape4-12" transform="translate(127.934 -289.509)">
+      <path class="st1" id="rect44" style="fill:url(#linearGradient230)" d="M0 459.587h153.071v36.85H0z"/>
+      <text x="60.41" y="482.21" class="st2" id="text46">nh_id</text>
+    </g>
+    <g id="shape5-16" transform="translate(127.934 -246.99)">
+      <path class="st1" id="rect51" style="fill:url(#linearGradient232)" d="M0 459.587h153.071v36.85H0z"/>
+    </g>
+    <g id="shape6-19" transform="translate(127.934 -110.927)">
+      <path class="st1" id="rect56" style="fill:url(#linearGradient234)" d="M0 459.587h153.071v36.85H0z"/>
+    </g>
+    <g id="shape7-22" transform="translate(127.934 -62.738)">
+      <path class="st1" id="rect61" style="fill:url(#linearGradient236)" d="M0 459.587h153.071v36.85H0z"/>
+    </g>
+    <g id="shape8-25" transform="translate(127.934 -14.549)">
+      <path class="st1" id="rect66" style="fill:url(#linearGradient238)" d="M0 459.587h153.071v36.85H0z"/>
+    </g>
+    <g id="shape9-28" transform="translate(527.619 -241.319)">
+      <path class="st1" id="rect71" style="fill:url(#linearGradient240)" d="M0 312.186h181.417v184.252H0z"/>
+    </g>
+    <g id="shape10-31" transform="translate(541.792 -377.383)">
+      <path class="st1" id="rect78" style="fill:url(#linearGradient242)" d="M0 459.587h153.071v36.85H0z"/>
+      <text x="25.03" y="482.21" class="st2" id="text80">uint[8,16,32,64]_t</text>
+    </g>
+    <g id="shape11-35" transform="translate(541.792 -334.864)">
+      <path class="st1" id="rect87" style="fill:url(#linearGradient244)" d="M0 459.587h153.071v36.85H0z"/>
+      <text x="60.41" y="482.21" class="st2" id="text89">nh_id</text>
+    </g>
+    <g id="shape12-39" transform="translate(541.792 -252.659)">
+      <path class="st1" id="rect94" style="fill:url(#linearGradient246)" d="M0 459.587h153.071v36.85H0z"/>
+    </g>
+    <g id="shape13-42" transform="translate(.375 -461.004)">
+      <path class="st1" id="rect101" style="fill:url(#linearGradient248)" d="M0 476.595h87.874v19.843H0z"/>
+      <text x="36.84" y="490.72" class="st2" id="text103">24</text>
+    </g>
+    <g id="shape14-46" transform="translate(88.25 -461.004)">
+      <path class="st1" id="rect110" style="fill:url(#linearGradient250)" d="M0 476.595h28.346v19.843H0z"/>
+      <text x="10.63" y="490.72" class="st2" id="text112">8</text>
+    </g>
+    <g id="shape15-50" transform="translate(44.312 -307.93)">
+      <path d="M0 343.37v153.07h83.62" class="st3" id="path117"/>
+    </g>
+    <g id="shape16-56" transform="translate(317.855 -198.796)">
+      <path d="m0 461.57 58.11-34.87 58.11 34.87-58.11 34.87z" class="st5" id="path124" style="fill:url(#linearGradient252)"/>
+      <text x="31.32" y="457.37" class="st6" id="text128">Extended <tspan x="39.75" dy="1.2em" id="tspan126" style="font-size:1em">entry?</tspan></text>
+    </g>
+    <g id="shape17-61" transform="translate(332.028 -79.745)">
+      <path class="st1" id="rect135" style="fill:url(#linearGradient254)" d="M0 476.595h87.874v19.843H0z"/>
+      <text x="6.8" y="490.72" class="st2" id="text137">Return nh_id</text>
+    </g>
+    <g id="shape18-65" transform="translate(375.969 -99.587)">
+      <path d="M0 397.23v99.21" class="st3" id="path144"/>
+      <path class="st8" id="rect146" d="M-7.372 438.43H7.366v16.8H-7.372z"/>
+      <text x="-7.37" y="451.03" class="st2" id="text148">no</text>
+    </g>
+    <g id="shape19-72" transform="translate(281.005 -268.529)">
+      <path d="M0 457.04h94.96v39.4" class="st3" id="path153"/>
+    </g>
+    <g id="shape20-77" transform="translate(344.409 -371.713)">
+      <path class="st5" id="rect160" style="fill:url(#linearGradient256)" d="M0 453.918h145.65v42.52H0z"/>
+      <text x="8.68" y="479.38" class="st6" id="text162">nh_id * 256 + ip &amp; 0xff  </text>
+    </g>
+    <g id="shape21-81" transform="translate(116.595 -414.232)">
+      <path d="M0 439.75h300.1v56.69" class="st3" id="path167"/>
+    </g>
+    <g id="shape22-86" transform="translate(490.06 -353.289)">
+      <path d="M0 456.76h21.26v39.68h30.47" class="st3" id="path172"/>
+    </g>
+    <g id="shape23-91" transform="translate(434.073 -233.662)">
+      <path d="M0 496.44h12.05V358.39" class="st3" id="path179"/>
+      <path class="st8" id="rect181" d="M2.661 425.034h18.778v16.8H2.661z"/>
+      <text x="2.66" y="437.63" class="st2" id="text183">yes</text>
+    </g>
+    <g id="shape24-98" transform="translate(375.591 -99.591)">
+      <path d="M242.74 262.59v212.59H0v21.26" class="st3" id="path188"/>
+    </g>
+    <g id="shape25-103" transform="translate(12.047 -483.914)">
+      <path class="st9" id="rect195" d="M0 486.517h89.291v9.921H0z"/>
+      <text x="7.26" y="495.68" class="st10" id="text197">IPv4 Address</text>
+    </g>
+    <g id="shape26-106" transform="translate(170.079 -426.331)">
+      <path class="st9" id="rect204" d="M0 483.398h68.031v13.039H0z"/>
+      <text x="16.57" y="494.12" class="st10" id="text206">tbl24</text>
+    </g>
+    <g id="shape27-109" transform="translate(597.067 -426.331)">
+      <path class="st9" id="rect213" d="M0 483.398h46.772v13.039H0z"/>
+      <text x="9.49" y="494.12" class="st10" id="text215">tbl8</text>
+    </g>
+  </g>
+</svg>
diff --git a/doc/guides/prog_guide/index.rst b/doc/guides/prog_guide/index.rst
index 0a53ec71c8..42c4a690c6 100644
--- a/doc/guides/prog_guide/index.rst
+++ b/doc/guides/prog_guide/index.rst
@@ -38,6 +38,7 @@ Programmer's Guide
     member_lib
     lpm_lib
     lpm6_lib
+    fib_lib
     rib_lib
     flow_classify_lib
     packet_distrib_lib
diff --git a/doc/guides/prog_guide/rib_lib.rst b/doc/guides/prog_guide/rib_lib.rst
index e8bb35a2b6..0a6c3d7063 100644
--- a/doc/guides/prog_guide/rib_lib.rst
+++ b/doc/guides/prog_guide/rib_lib.rst
@@ -7,7 +7,7 @@ RIB Library
 The Routing Information Base (RIB) library provides a data store for routing information.
 This library is intended for use in control or management plane applications.
 There are more suitable libraries for use in data plane applications such as
-:ref:`LPM <LPM_Library>` or FIB.
+:ref:`LPM <LPM_Library>` or :ref:`FIB <FIB_Library>`.
 
 
 Implementation details
-- 
2.25.1


^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [dpdk-dev] [PATCH 1/2] doc: add programmer's guide for the RIB library
  2021-11-08 17:37 [dpdk-dev] [PATCH 1/2] doc: add programmer's guide for the RIB library Vladimir Medvedkin
  2021-11-08 17:37 ` [dpdk-dev] [PATCH 2/2] doc: add programmer's guide for the FIB library Vladimir Medvedkin
@ 2021-11-09 11:32 ` Walsh, Conor
  1 sibling, 0 replies; 5+ messages in thread
From: Walsh, Conor @ 2021-11-09 11:32 UTC (permalink / raw)
  To: Medvedkin, Vladimir, dev

> From: dev <dev-bounces@dpdk.org> On Behalf Of Vladimir Medvedkin
> Sent: Monday 8 November 2021 17:37
> To: dev@dpdk.org
> Subject: [dpdk-dev] [PATCH 1/2] doc: add programmer's guide for the RIB
> library
> 
> Currently, programmer's guide for the RIB library is missing.
> This commit adds it.
> 
> Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
> ---
>  doc/guides/prog_guide/img/rib_internals.svg | 148 +++++++++++++++++
>  doc/guides/prog_guide/img/rib_pic.svg       | 152 +++++++++++++++++
>  doc/guides/prog_guide/index.rst             |   1 +
>  doc/guides/prog_guide/rib_lib.rst           | 172 ++++++++++++++++++++
>  4 files changed, 473 insertions(+)
>  create mode 100644 doc/guides/prog_guide/img/rib_internals.svg
>  create mode 100644 doc/guides/prog_guide/img/rib_pic.svg
>  create mode 100644 doc/guides/prog_guide/rib_lib.rst
> 

<snip>

> +   RIB prefix independent convergence
> +
> +In case of a next hop failure, we need to replace an active failed next hop
> with a
> +feasible next hop for every corresponding route without waiting for the
> routing daemon
> +recalculation process to complete.
> +To achieve this we can link all existing routes with the same active next hop
> in a linked list,
> +saving the feasible next hop ID and a pointer inside the extension space of
> each ``rte_rib_node``.
> +
> +.. code-block:: c
> +
> +      struct my_route_ext {
> +         struct rte_rib_node *next;
> +         uint64_t feasible_nh;
> +      };
> +
> +      struct rte_rib_conf conf;
> +      conf.ext_sz = sizeof(struct my_route_ext);
> +      rib = rte_rib_create("test", 0, &conf);
> +      ...
> +      /* routing daemon task */
> +      struct rte_rib_node *route = rte_rib_insert(rib, RTE_IPV4(192,0,2,0), 24);
> +      rte_rib_set_nh(route, active_nh_from_rd);
> +      struct my_route_ext *ext = rte_rib_get_ext(route);
> +      ext->feasible_nh = feasible_nh_from_rd;
> +      list_insert(nh_table[active_nh_from_rd].list_head, route);
> +      ...
> +      /* dataplane monitoring thread */
> +      /* nexthop id fail_nh fails */
                ^^^^^^^

> +      route = NULL;
> +      do {
> +         route = get_next(nh_table[fail_nh].list_head, route);
> +         uint32_t ip;
> +         uint8_t depth;
> +         rte_rib_get_ip(route, &ip);
> +         rte_rib_get_depth(route, &depth);
> +         ext = rte_rib_get_ext(route);
> +         uint64_t new_nh = ext->feasible_nh;
> +         /* do update to the dataplane, for example to the fib */
> +         rte_fib_add(fib, ip, depth, new_nh);
> +         /* update nexthop if necessary */
                                 ^^^^^^^
These two comments are showing as spelling errors on aspell but I think they are ok as this is technically a code comment
and nexthop often appears in the code without a space.

> +         rte_rib_set_nh(route, new_nh);
> +      } while (route != NULL);
> +
> --
> 2.25.1

Reviewed-by: Conor Walsh <conor.walsh@intel.com>

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [dpdk-dev] [PATCH 2/2] doc: add programmer's guide for the FIB library
  2021-11-08 17:37 ` [dpdk-dev] [PATCH 2/2] doc: add programmer's guide for the FIB library Vladimir Medvedkin
@ 2021-11-09 11:32   ` Walsh, Conor
  2021-11-26 14:26     ` David Marchand
  0 siblings, 1 reply; 5+ messages in thread
From: Walsh, Conor @ 2021-11-09 11:32 UTC (permalink / raw)
  To: Medvedkin, Vladimir, dev

> From: dev <dev-bounces@dpdk.org> On Behalf Of Vladimir Medvedkin
> Sent: Monday 8 November 2021 17:37
> To: dev@dpdk.org
> Subject: [dpdk-dev] [PATCH 2/2] doc: add programmer's guide for the FIB
> library
> 
> Currently, programmer's guide for the FIB library is missing.
> This commit adds it.
> 
> Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
> ---

Both of these look good to me!

Reviewed-by: Conor Walsh <conor.walsh@intel.com>

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [dpdk-dev] [PATCH 2/2] doc: add programmer's guide for the FIB library
  2021-11-09 11:32   ` Walsh, Conor
@ 2021-11-26 14:26     ` David Marchand
  0 siblings, 0 replies; 5+ messages in thread
From: David Marchand @ 2021-11-26 14:26 UTC (permalink / raw)
  To: Medvedkin, Vladimir; +Cc: dev, Walsh, Conor

On Tue, Nov 9, 2021 at 12:33 PM Walsh, Conor <conor.walsh@intel.com> wrote:
>
> > From: dev <dev-bounces@dpdk.org> On Behalf Of Vladimir Medvedkin
> > Sent: Monday 8 November 2021 17:37
> > To: dev@dpdk.org
> > Subject: [dpdk-dev] [PATCH 2/2] doc: add programmer's guide for the FIB
> > library
> >
> > Currently, programmer's guide for the FIB library is missing.
> > This commit adds it.
> >
> > Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
> Reviewed-by: Conor Walsh <conor.walsh@intel.com>


Applied, thanks.


-- 
David Marchand


^ permalink raw reply	[flat|nested] 5+ messages in thread

end of thread, other threads:[~2021-11-26 14:26 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-11-08 17:37 [dpdk-dev] [PATCH 1/2] doc: add programmer's guide for the RIB library Vladimir Medvedkin
2021-11-08 17:37 ` [dpdk-dev] [PATCH 2/2] doc: add programmer's guide for the FIB library Vladimir Medvedkin
2021-11-09 11:32   ` Walsh, Conor
2021-11-26 14:26     ` David Marchand
2021-11-09 11:32 ` [dpdk-dev] [PATCH 1/2] doc: add programmer's guide for the RIB library Walsh, Conor

DPDK patches and discussions

This inbox may be cloned and mirrored by anyone:

	git clone --mirror http://inbox.dpdk.org/dev/0 dev/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 dev dev/ http://inbox.dpdk.org/dev \
		dev@dpdk.org
	public-inbox-index dev

Example config snippet for mirrors.
Newsgroup available over NNTP:
	nntp://inbox.dpdk.org/inbox.dpdk.dev


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git