diff options
Diffstat (limited to 'Documentation/RCU/Design/Data-Structures')
12 files changed, 8410 insertions, 0 deletions
diff --git a/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCU.svg b/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCU.svg new file mode 100644 index 000000000..727e270b1 --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCU.svg @@ -0,0 +1,474 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:28:20 2015 --> + +<!-- Magnification: 3.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="9.1in" + height="8.9in" + viewBox="-66 -66 10932 10707" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="BigTreeClassicRCU.fig"> + <metadata + id="metadata106"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs104"> + <marker + inkscape:stockid="Arrow1Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow1Mend" + style="overflow:visible;"> + <path + id="path3864" + d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " + style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;" + transform="scale(0.4) rotate(180) translate(10,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="973" + inkscape:window-height="1137" + id="namedview102" + showgrid="false" + inkscape:zoom="0.9743589" + inkscape:cx="409.50003" + inkscape:cy="400.49997" + inkscape:window-x="915" + inkscape:window-y="24" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="0" + y="0" + width="10800" + height="5625" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect6" /> + <!-- Line: box --> + <rect + x="1125" + y="3600" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect8" /> + <!-- Line: box --> + <rect + x="3825" + y="900" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect10" /> + <!-- Line: box --> + <rect + x="6525" + y="3600" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect12" /> + <!-- Line --> + <polyline + points="3375,6525 3375,5046 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline14" /> + <!-- Arrowhead on XXXpoint 3375 6525 - 3375 4860--> + <!-- Circle --> + <circle + cx="7425" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle18" /> + <!-- Circle --> + <circle + cx="7875" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle20" /> + <!-- Circle --> + <circle + cx="8325" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle22" /> + <!-- Circle --> + <circle + cx="2025" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle24" /> + <!-- Circle --> + <circle + cx="2475" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle26" /> + <!-- Circle --> + <circle + cx="2925" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle28" /> + <!-- Circle --> + <circle + cx="4725" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle30" /> + <!-- Circle --> + <circle + cx="5175" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle32" /> + <!-- Circle --> + <circle + cx="5625" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle34" /> + <!-- Line: box --> + <rect + x="2025" + y="6525" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect36" /> + <!-- Line --> + <polyline + points="2475,3600 3975,2310 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline38" /> + <!-- Arrowhead on XXXpoint 2475 3600 - 4116 2190--> + <!-- Line --> + <polyline + points="7875,3600 6372,2310 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline42" /> + <!-- Arrowhead on XXXpoint 7875 3600 - 6231 2190--> + <!-- Line --> + <polyline + points="6975,8775 6975,5046 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline46" /> + <!-- Arrowhead on XXXpoint 6975 8775 - 6975 4860--> + <!-- Line --> + <polyline + points="1575,8775 1575,5046 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline50" /> + <!-- Arrowhead on XXXpoint 1575 8775 - 1575 4860--> + <!-- Line --> + <polyline + points="8775,6525 8775,5046 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline54" /> + <!-- Arrowhead on XXXpoint 8775 6525 - 8775 4860--> + <!-- Text --> + <text + xml:space="preserve" + x="1575" + y="9225" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text58">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1575" + y="9675" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text60">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="1575" + y="10350" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text62">CPU 0</text> + <!-- Text --> + <text + xml:space="preserve" + x="3375" + y="6975" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text64">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="3375" + y="7425" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text66">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="3375" + y="8100" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text68">CPU 15</text> + <!-- Text --> + <text + xml:space="preserve" + x="6975" + y="9225" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text70">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="6975" + y="9675" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text72">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="6975" + y="10350" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text74">CPU 1007</text> + <!-- Text --> + <text + xml:space="preserve" + x="8730" + y="6930" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text76">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="8730" + y="7380" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text78">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="8730" + y="8055" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text80">CPU 1023</text> + <!-- Text --> + <text + xml:space="preserve" + x="225" + y="450" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="start" + id="text82">struct rcu_state</text> + <!-- Text --> + <text + xml:space="preserve" + x="2475" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text84">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2475" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text86">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="7875" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text88">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="7875" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text90">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5175" + y="1350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text92">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5175" + y="1800" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text94">rcu_node</text> + <!-- Line: box --> + <rect + x="225" + y="8775" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect96" /> + <!-- Line: box --> + <rect + x="5625" + y="8775" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect98" /> + <!-- Line: box --> + <rect + x="7380" + y="6480" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect100" /> + </g> +</svg> diff --git a/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBH.svg b/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBH.svg new file mode 100644 index 000000000..9bbb1944f --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBH.svg @@ -0,0 +1,499 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:26:09 2015 --> + +<!-- Magnification: 2.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="5.7in" + height="6.6in" + viewBox="-44 -44 6838 7888" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="BigTreeClassicRCUBH.fig"> + <metadata + id="metadata110"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs108"> + <marker + inkscape:stockid="Arrow1Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow1Mend" + style="overflow:visible;"> + <path + id="path3868" + d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " + style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;" + transform="scale(0.4) rotate(180) translate(10,0)" /> + </marker> + <marker + inkscape:stockid="Arrow2Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow2Mend" + style="overflow:visible;"> + <path + id="path3886" + style="fill-rule:evenodd;stroke-width:0.62500000;stroke-linejoin:round;" + d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.9730900,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z " + transform="scale(0.6) rotate(180) translate(0,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="878" + inkscape:window-height="1148" + id="namedview106" + showgrid="false" + inkscape:zoom="1.3547758" + inkscape:cx="256.5" + inkscape:cy="297" + inkscape:window-x="45" + inkscape:window-y="24" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="450" + y="0" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect6" /> + <!-- Line: box --> + <rect + x="4950" + y="4950" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect8" /> + <!-- Line: box --> + <rect + x="750" + y="600" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect10" /> + <!-- Line: box --> + <rect + x="0" + y="450" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect12" /> + <!-- Line: box --> + <rect + x="300" + y="1050" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect14" /> + <!-- Circle --> + <circle + cx="2850" + cy="3900" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle16" /> + <!-- Circle --> + <circle + cx="3150" + cy="3900" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle18" /> + <!-- Circle --> + <circle + cx="3450" + cy="3900" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle20" /> + <!-- Circle --> + <circle + cx="1350" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle22" /> + <!-- Circle --> + <circle + cx="1650" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle24" /> + <!-- Circle --> + <circle + cx="1950" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle26" /> + <!-- Circle --> + <circle + cx="4350" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle28" /> + <!-- Circle --> + <circle + cx="4650" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle30" /> + <!-- Circle --> + <circle + cx="4950" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle32" /> + <!-- Line --> + <polyline + points="1350,3450 2350,2590 " + style="stroke:#00d1d1;stroke-width:30.0045575;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline34" /> + <!-- Arrowhead on XXXpoint 1350 3450 - 2444 2510--> + <!-- Line --> + <polyline + points="4950,3450 3948,2590 " + style="stroke:#00d1d1;stroke-width:30.0045575;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline38" /> + <!-- Arrowhead on XXXpoint 4950 3450 - 3854 2510--> + <!-- Line: box --> + <rect + x="750" + y="3450" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect42" /> + <!-- Line --> + <polyline + points="2250,5400 2250,4414 " + style="stroke:#00d1d1;stroke-width:30.0045575;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline44" /> + <!-- Arrowhead on XXXpoint 2250 5400 - 2250 4290--> + <!-- Line: box --> + <rect + x="1500" + y="5400" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect48" /> + <!-- Line: box --> + <rect + x="300" + y="6600" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect50" /> + <!-- Line: box --> + <rect + x="3750" + y="3450" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect52" /> + <!-- Line: box --> + <rect + x="4500" + y="5400" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect54" /> + <!-- Line: box --> + <rect + x="3300" + y="6600" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect56" /> + <!-- Line: box --> + <rect + x="2250" + y="1650" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect58" /> + <!-- Text --> + <text + xml:space="preserve" + x="6450" + y="300" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text60">rcu_bh</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="1950" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text62">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="2250" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text64">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="1650" + y="3750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text66">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1650" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text68">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="4650" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text70">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="4650" + y="3750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text72">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="5700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text74">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="6000" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text76">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="6900" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text78">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text80">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="5250" + y="5700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text82">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5250" + y="6000" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text84">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="6900" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text86">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text88">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="450" + y="1350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="start" + id="text90">struct rcu_state</text> + <!-- Text --> + <text + xml:space="preserve" + x="6000" + y="750" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text92">rcu_sched</text> + <!-- Line --> + <polyline + points="5250,5400 5250,4414 " + style="stroke:#00d1d1;stroke-width:30.0045575;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline94" /> + <!-- Arrowhead on XXXpoint 5250 5400 - 5250 4290--> + <!-- Line --> + <polyline + points="4050,6600 4050,4414 " + style="stroke:#00d1d1;stroke-width:30.0045575;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline98" /> + <!-- Arrowhead on XXXpoint 4050 6600 - 4050 4290--> + <!-- Line --> + <polyline + points="1050,6600 1050,4414 " + style="stroke:#00d1d1;stroke-width:30.0045575;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline102" /> + <!-- Arrowhead on XXXpoint 1050 6600 - 1050 4290--> + </g> +</svg> diff --git a/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBHdyntick.svg b/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBHdyntick.svg new file mode 100644 index 000000000..21ba78234 --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBHdyntick.svg @@ -0,0 +1,695 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:20:02 2015 --> + +<!-- Magnification: 2.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="5.7in" + height="8.6in" + viewBox="-44 -44 6838 10288" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="BigTreeClassicRCUBHdyntick.fig"> + <metadata + id="metadata166"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs164"> + <marker + inkscape:stockid="Arrow1Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow1Mend" + style="overflow:visible;"> + <path + id="path3924" + d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " + style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;" + transform="scale(0.4) rotate(180) translate(10,0)" /> + </marker> + <marker + inkscape:stockid="Arrow2Lend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow2Lend" + style="overflow:visible;"> + <path + id="path3936" + style="fill-rule:evenodd;stroke-width:0.62500000;stroke-linejoin:round;" + d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.9730900,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z " + transform="scale(1.1) rotate(180) translate(1,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="845" + inkscape:window-height="988" + id="namedview162" + showgrid="false" + inkscape:zoom="1.0452196" + inkscape:cx="256.5" + inkscape:cy="387.00003" + inkscape:window-x="356" + inkscape:window-y="61" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="450" + y="0" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect6" /> + <!-- Line: box --> + <rect + x="4950" + y="4950" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect8" /> + <!-- Line: box --> + <rect + x="750" + y="600" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect10" /> + <!-- Line --> + <polyline + points="5250,8100 5688,5912 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline12" /> + <!-- Arrowhead on XXXpoint 5250 8100 - 5710 5790--> + <polyline + points="5714 6068 5704 5822 5598 6044 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline14" /> + <!-- Line --> + <polyline + points="4050,9300 4486,7262 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline16" /> + <!-- Arrowhead on XXXpoint 4050 9300 - 4512 7140--> + <polyline + points="4514 7418 4506 7172 4396 7394 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline18" /> + <!-- Line --> + <polyline + points="1040,9300 1476,7262 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline20" /> + <!-- Arrowhead on XXXpoint 1040 9300 - 1502 7140--> + <polyline + points="1504 7418 1496 7172 1386 7394 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline22" /> + <!-- Line --> + <polyline + points="2240,8100 2676,6062 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline24" /> + <!-- Arrowhead on XXXpoint 2240 8100 - 2702 5940--> + <polyline + points="2704 6218 2696 5972 2586 6194 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline26" /> + <!-- Line: box --> + <rect + x="0" + y="450" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect28" /> + <!-- Line: box --> + <rect + x="300" + y="1050" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect30" /> + <!-- Line --> + <polyline + points="1350,3450 2350,2590 " + style="stroke:#00d1d1;stroke-width:30.0045575;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline32" /> + <!-- Arrowhead on XXXpoint 1350 3450 - 2444 2510--> + <!-- Line --> + <polyline + points="4950,3450 3948,2590 " + style="stroke:#00d1d1;stroke-width:30.0045575;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline36" /> + <!-- Arrowhead on XXXpoint 4950 3450 - 3854 2510--> + <!-- Line --> + <polyline + points="4050,6600 4050,4414 " + style="stroke:#00d1d1;stroke-width:30.00455750000000066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline40" /> + <!-- Arrowhead on XXXpoint 4050 6600 - 4050 4290--> + <!-- Line --> + <polyline + points="1050,6600 1050,4414 " + style="stroke:#00d1d1;stroke-width:30.00455750000000066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline44" /> + <!-- Arrowhead on XXXpoint 1050 6600 - 1050 4290--> + <!-- Line --> + <polyline + points="2250,5400 2250,4414 " + style="stroke:#00d1d1;stroke-width:30.00455750000000066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline48" /> + <!-- Arrowhead on XXXpoint 2250 5400 - 2250 4290--> + <!-- Line --> + <polyline + points="2250,8100 2250,6364 " + style="stroke:#00ff00;stroke-width:30;stroke-linejoin:miter;stroke-linecap:butt;marker-end:url(#Arrow1Mend)" + id="polyline52" /> + <!-- Arrowhead on XXXpoint 2250 8100 - 2250 6240--> + <!-- Line --> + <polyline + points="1050,9300 1050,7564 " + style="stroke:#00ff00;stroke-width:30;stroke-linejoin:miter;stroke-linecap:butt;marker-end:url(#Arrow1Mend)" + id="polyline56" /> + <!-- Arrowhead on XXXpoint 1050 9300 - 1050 7440--> + <!-- Line --> + <polyline + points="4050,9300 4050,7564 " + style="stroke:#00ff00;stroke-width:30;stroke-linejoin:miter;stroke-linecap:butt;marker-end:url(#Arrow1Mend)" + id="polyline60" /> + <!-- Arrowhead on XXXpoint 4050 9300 - 4050 7440--> + <!-- Line --> + <polyline + points="5250,8100 5250,6364 " + style="stroke:#00ff00;stroke-width:30;stroke-linejoin:miter;stroke-linecap:butt;marker-end:url(#Arrow1Mend)" + id="polyline64" /> + <!-- Arrowhead on XXXpoint 5250 8100 - 5250 6240--> + <!-- Circle --> + <circle + cx="2850" + cy="3900" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle68" /> + <!-- Circle --> + <circle + cx="3150" + cy="3900" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle70" /> + <!-- Circle --> + <circle + cx="3450" + cy="3900" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle72" /> + <!-- Circle --> + <circle + cx="1350" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle74" /> + <!-- Circle --> + <circle + cx="1650" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle76" /> + <!-- Circle --> + <circle + cx="1950" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle78" /> + <!-- Circle --> + <circle + cx="4350" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle80" /> + <!-- Circle --> + <circle + cx="4650" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle82" /> + <!-- Circle --> + <circle + cx="4950" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle84" /> + <!-- Line: box --> + <rect + x="750" + y="3450" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect86" /> + <!-- Line: box --> + <rect + x="300" + y="6600" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect88" /> + <!-- Line: box --> + <rect + x="3750" + y="3450" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect90" /> + <!-- Line: box --> + <rect + x="4500" + y="5400" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect92" /> + <!-- Line: box --> + <rect + x="3300" + y="6600" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect94" /> + <!-- Line: box --> + <rect + x="2250" + y="1650" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect96" /> + <!-- Line: box --> + <rect + x="0" + y="9300" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect98" /> + <!-- Line: box --> + <rect + x="1350" + y="8100" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect100" /> + <!-- Line: box --> + <rect + x="3000" + y="9300" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect102" /> + <!-- Line: box --> + <rect + x="4350" + y="8100" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect104" /> + <!-- Line: box --> + <rect + x="1500" + y="5400" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect106" /> + <!-- Text --> + <text + xml:space="preserve" + x="6450" + y="300" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text108">rcu_bh</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="1950" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text110">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="2250" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text112">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="1650" + y="3750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text114">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1650" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text116">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="4650" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text118">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="4650" + y="3750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text120">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="5700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text122">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="6000" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text124">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="6900" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text126">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text128">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="5250" + y="5700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text130">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5250" + y="6000" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text132">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="6900" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text134">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text136">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="450" + y="1350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="start" + id="text138">struct rcu_state</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="9600" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text140">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="9900" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text142">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="9600" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text144">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="9900" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text146">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="2400" + y="8400" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text148">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2400" + y="8700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text150">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="5400" + y="8400" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text152">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5400" + y="8700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text154">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="6000" + y="750" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text156">rcu_sched</text> + <!-- Line --> + <polyline + points="5250,5400 5250,4414 " + style="stroke:#00d1d1;stroke-width:30.00455750000000066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline158" /> + <!-- Arrowhead on XXXpoint 5250 5400 - 5250 4290--> + </g> +</svg> diff --git a/Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntick.svg b/Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntick.svg new file mode 100644 index 000000000..15adcac03 --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntick.svg @@ -0,0 +1,741 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:32:59 2015 --> + +<!-- Magnification: 2.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="6.1in" + height="8.9in" + viewBox="-44 -44 7288 10738" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="BigTreePreemptRCUBHdyntick.fig"> + <metadata + id="metadata182"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs180"> + <marker + inkscape:stockid="Arrow1Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow1Mend" + style="overflow:visible;"> + <path + id="path3940" + d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " + style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;" + transform="scale(0.4) rotate(180) translate(10,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="874" + inkscape:window-height="1148" + id="namedview178" + showgrid="false" + inkscape:zoom="1.2097379" + inkscape:cx="274.5" + inkscape:cy="400.49997" + inkscape:window-x="946" + inkscape:window-y="24" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="900" + y="0" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect6" /> + <!-- Line: box --> + <rect + x="1200" + y="600" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect8" /> + <!-- Line: box --> + <rect + x="5400" + y="4950" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect10" /> + <!-- Line: box --> + <rect + x="450" + y="450" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect12" /> + <!-- Line: box --> + <rect + x="750" + y="1050" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect14" /> + <!-- Line: box --> + <rect + x="4950" + y="5400" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect16" /> + <!-- Line --> + <polyline + points="5250,8550 5688,6362 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline18" /> + <!-- Arrowhead on XXXpoint 5250 8550 - 5710 6240--> + <polyline + points="5714 6518 5704 6272 5598 6494 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline20" /> + <!-- Line --> + <polyline + points="4050,9750 4486,7712 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline22" /> + <!-- Arrowhead on XXXpoint 4050 9750 - 4512 7590--> + <polyline + points="4514 7868 4506 7622 4396 7844 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline24" /> + <!-- Line --> + <polyline + points="1040,9750 1476,7712 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline26" /> + <!-- Arrowhead on XXXpoint 1040 9750 - 1502 7590--> + <polyline + points="1504 7868 1496 7622 1386 7844 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline28" /> + <!-- Line --> + <polyline + points="2240,8550 2676,6512 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline30" /> + <!-- Arrowhead on XXXpoint 2240 8550 - 2702 6390--> + <polyline + points="2704 6668 2696 6422 2586 6644 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline32" /> + <!-- Line --> + <polyline + points="4050,9750 5682,6360 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline34" /> + <!-- Arrowhead on XXXpoint 4050 9750 - 5736 6246--> + <polyline + points="5672 6518 5722 6276 5562 6466 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline36" /> + <!-- Line --> + <polyline + points="1010,9750 2642,6360 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline38" /> + <!-- Arrowhead on XXXpoint 1010 9750 - 2696 6246--> + <polyline + points="2632 6518 2682 6276 2522 6466 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline40" /> + <!-- Line: box --> + <rect + x="0" + y="900" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect42" /> + <!-- Line: box --> + <rect + x="300" + y="1500" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect44" /> + <!-- Line --> + <polyline + points="1350,3900 2350,3040 " + style="stroke:#00d1d1;stroke-width:30.00205472;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline46" /> + <!-- Arrowhead on XXXpoint 1350 3900 - 2444 2960--> + <!-- Line --> + <polyline + points="4950,3900 3948,3040 " + style="stroke:#00d1d1;stroke-width:30.00205472;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline50" /> + <!-- Arrowhead on XXXpoint 4950 3900 - 3854 2960--> + <!-- Line --> + <polyline + points="4050,7050 4050,4864 " + style="stroke:#00d1d1;stroke-width:30.00205472;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline54" /> + <!-- Arrowhead on XXXpoint 4050 7050 - 4050 4740--> + <!-- Line --> + <polyline + points="1050,7050 1050,4864 " + style="stroke:#00d1d1;stroke-width:30.00205472;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline58" /> + <!-- Arrowhead on XXXpoint 1050 7050 - 1050 4740--> + <!-- Line --> + <polyline + points="2250,5850 2250,4864 " + style="stroke:#00d1d1;stroke-width:30.00205472;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline62" /> + <!-- Arrowhead on XXXpoint 2250 5850 - 2250 4740--> + <!-- Line --> + <polyline + points="2250,8550 2250,6814 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline66" /> + <!-- Arrowhead on XXXpoint 2250 8550 - 2250 6690--> + <!-- Line --> + <polyline + points="1050,9750 1050,8014 " + style="stroke:#00ff00;stroke-width:30.00205472;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline70" /> + <!-- Arrowhead on XXXpoint 1050 9750 - 1050 7890--> + <!-- Line --> + <polyline + points="4050,9750 4050,8014 " + style="stroke:#00ff00;stroke-width:30.00205472;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline74" /> + <!-- Arrowhead on XXXpoint 4050 9750 - 4050 7890--> + <!-- Line --> + <polyline + points="5250,8550 5250,6814 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline78" /> + <!-- Arrowhead on XXXpoint 5250 8550 - 5250 6690--> + <!-- Circle --> + <circle + cx="2850" + cy="4350" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle82" /> + <!-- Circle --> + <circle + cx="3150" + cy="4350" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle84" /> + <!-- Circle --> + <circle + cx="3450" + cy="4350" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle86" /> + <!-- Circle --> + <circle + cx="1350" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle88" /> + <!-- Circle --> + <circle + cx="1650" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle90" /> + <!-- Circle --> + <circle + cx="1950" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle92" /> + <!-- Circle --> + <circle + cx="4350" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle94" /> + <!-- Circle --> + <circle + cx="4650" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle96" /> + <!-- Circle --> + <circle + cx="4950" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle98" /> + <!-- Line: box --> + <rect + x="750" + y="3900" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect100" /> + <!-- Line: box --> + <rect + x="300" + y="7050" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect102" /> + <!-- Line: box --> + <rect + x="3750" + y="3900" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect104" /> + <!-- Line: box --> + <rect + x="4500" + y="5850" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect106" /> + <!-- Line: box --> + <rect + x="3300" + y="7050" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect108" /> + <!-- Line: box --> + <rect + x="2250" + y="2100" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect110" /> + <!-- Line: box --> + <rect + x="0" + y="9750" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect112" /> + <!-- Line: box --> + <rect + x="1350" + y="8550" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect114" /> + <!-- Line: box --> + <rect + x="3000" + y="9750" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect116" /> + <!-- Line: box --> + <rect + x="4350" + y="8550" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect118" /> + <!-- Line: box --> + <rect + x="1500" + y="5850" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect120" /> + <!-- Text --> + <text + xml:space="preserve" + x="6450" + y="750" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text122">rcu_bh</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="2400" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text124">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="2700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text126">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="1650" + y="4200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text128">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1650" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text130">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="4650" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text132">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="4650" + y="4200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text134">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="6150" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text136">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="6450" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text138">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="7350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text140">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="7650" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text142">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="5250" + y="6150" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text144">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5250" + y="6450" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text146">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="7350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text148">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="7650" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text150">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="450" + y="1800" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="start" + id="text152">struct rcu_state</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="10050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text154">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="10350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text156">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="10050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text158">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="10350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text160">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="2400" + y="8850" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text162">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2400" + y="9150" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text164">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="5400" + y="8850" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text166">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5400" + y="9150" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text168">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="6900" + y="300" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text170">rcu_preempt</text> + <!-- Text --> + <text + xml:space="preserve" + x="6000" + y="1200" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text172">rcu_sched</text> + <!-- Line --> + <polyline + points="5250,5850 5250,4864 " + style="stroke:#00d1d1;stroke-width:30.00205472;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline174" /> + <!-- Arrowhead on XXXpoint 5250 5850 - 5250 4740--> + </g> +</svg> diff --git a/Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntickCB.svg b/Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntickCB.svg new file mode 100644 index 000000000..bbc380147 --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntickCB.svg @@ -0,0 +1,858 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:29:48 2015 --> + +<!-- Magnification: 2.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="7.4in" + height="9.9in" + viewBox="-44 -44 8938 11938" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="BigTreePreemptRCUBHdyntickCB.svg"> + <metadata + id="metadata212"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs210"> + <marker + inkscape:stockid="Arrow1Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow1Mend" + style="overflow:visible;"> + <path + id="path3970" + d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " + style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;" + transform="scale(0.4) rotate(180) translate(10,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="881" + inkscape:window-height="1128" + id="namedview208" + showgrid="false" + inkscape:zoom="1.0195195" + inkscape:cx="333" + inkscape:cy="445.49997" + inkscape:window-x="936" + inkscape:window-y="24" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="900" + y="0" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect6" /> + <!-- Line: box --> + <rect + x="1200" + y="600" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect8" /> + <!-- Line: box --> + <rect + x="5400" + y="4950" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect10" /> + <!-- Line: box --> + <rect + x="450" + y="450" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect12" /> + <!-- Line: box --> + <rect + x="750" + y="1050" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect14" /> + <!-- Line: box --> + <rect + x="4950" + y="5400" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect16" /> + <!-- Line --> + <polyline + points="5250,8550 5688,6362 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline18" /> + <!-- Arrowhead on XXXpoint 5250 8550 - 5710 6240--> + <polyline + points="5714 6518 5704 6272 5598 6494 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline20" /> + <!-- Line --> + <polyline + points="4050,9750 4486,7712 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline22" /> + <!-- Arrowhead on XXXpoint 4050 9750 - 4512 7590--> + <polyline + points="4514 7868 4506 7622 4396 7844 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline24" /> + <!-- Line --> + <polyline + points="1040,9750 1476,7712 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline26" /> + <!-- Arrowhead on XXXpoint 1040 9750 - 1502 7590--> + <polyline + points="1504 7868 1496 7622 1386 7844 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline28" /> + <!-- Line --> + <polyline + points="2240,8550 2676,6512 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline30" /> + <!-- Arrowhead on XXXpoint 2240 8550 - 2702 6390--> + <polyline + points="2704 6668 2696 6422 2586 6644 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline32" /> + <!-- Line --> + <polyline + points="4050,9600 5692,6062 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline34" /> + <!-- Arrowhead on XXXpoint 4050 9600 - 5744 5948--> + <polyline + points="5682 6220 5730 5978 5574 6170 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline36" /> + <!-- Line --> + <polyline + points="1086,9600 2728,6062 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline38" /> + <!-- Arrowhead on XXXpoint 1086 9600 - 2780 5948--> + <polyline + points="2718 6220 2766 5978 2610 6170 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline40" /> + <!-- Line: box --> + <rect + x="0" + y="900" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect42" /> + <!-- Line: box --> + <rect + x="300" + y="1500" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect44" /> + <!-- Line --> + <polyline + points="1350,3900 2350,3040 " + style="stroke:#00d1d1;stroke-width:29.99463964;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline46" /> + <!-- Arrowhead on XXXpoint 1350 3900 - 2444 2960--> + <!-- Line --> + <polyline + points="4950,3900 3948,3040 " + style="stroke:#00d1d1;stroke-width:29.99463964;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline50" /> + <!-- Arrowhead on XXXpoint 4950 3900 - 3854 2960--> + <!-- Line --> + <polyline + points="4050,7050 4050,4864 " + style="stroke:#00d1d1;stroke-width:29.99463964;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline54" /> + <!-- Arrowhead on XXXpoint 4050 7050 - 4050 4740--> + <!-- Line --> + <polyline + points="1050,7050 1050,4864 " + style="stroke:#00d1d1;stroke-width:29.99463964;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline58" /> + <!-- Arrowhead on XXXpoint 1050 7050 - 1050 4740--> + <!-- Line --> + <polyline + points="2250,5850 2250,4864 " + style="stroke:#00d1d1;stroke-width:29.99463964;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline62" /> + <!-- Arrowhead on XXXpoint 2250 5850 - 2250 4740--> + <!-- Line --> + <polyline + points="2250,8550 2250,6814 " + style="stroke:#00ff00;stroke-width:29.99463964;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline66" /> + <!-- Arrowhead on XXXpoint 2250 8550 - 2250 6690--> + <!-- Line --> + <polyline + points="1050,9750 1050,8014 " + style="stroke:#00ff00;stroke-width:29.99463964;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline70" /> + <!-- Arrowhead on XXXpoint 1050 9750 - 1050 7890--> + <!-- Line --> + <polyline + points="4050,9750 4050,8014 " + style="stroke:#00ff00;stroke-width:29.99463964;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline74" /> + <!-- Arrowhead on XXXpoint 4050 9750 - 4050 7890--> + <!-- Line --> + <polyline + points="5250,8550 5250,6814 " + style="stroke:#00ff00;stroke-width:29.99463964;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline78" /> + <!-- Arrowhead on XXXpoint 5250 8550 - 5250 6690--> + <!-- Line --> + <polyline + points="6000,6300 8048,7910 " + style="stroke:#87cfff;stroke-width:30;stroke-linejoin:miter;stroke-linecap:butt;marker-end:url(#Arrow1Mend)" + id="polyline82" /> + <!-- Arrowhead on XXXpoint 6000 6300 - 8146 7986--> + <!-- Circle --> + <circle + cx="2850" + cy="4350" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle86" /> + <!-- Circle --> + <circle + cx="3150" + cy="4350" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle88" /> + <!-- Circle --> + <circle + cx="3450" + cy="4350" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle90" /> + <!-- Circle --> + <circle + cx="1350" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle92" /> + <!-- Circle --> + <circle + cx="1650" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle94" /> + <!-- Circle --> + <circle + cx="1950" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle96" /> + <!-- Circle --> + <circle + cx="4350" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle98" /> + <!-- Circle --> + <circle + cx="4650" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle100" /> + <!-- Circle --> + <circle + cx="4950" + cy="5550" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle102" /> + <!-- Line: box --> + <rect + x="7350" + y="7950" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect104" /> + <!-- Line: box --> + <rect + x="7350" + y="9450" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect106" /> + <!-- Line --> + <polyline + points="8100,8850 8100,9384 " + style="stroke:#000000;stroke-width:30;stroke-linejoin:miter;stroke-linecap:butt;marker-end:url(#Arrow1Mend)" + id="polyline108" /> + <!-- Arrowhead on XXXpoint 8100 8850 - 8100 9510--> + <!-- Line: box --> + <rect + x="7350" + y="10950" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect112" /> + <!-- Line --> + <polyline + points="8100,10350 8100,10884 " + style="stroke:#000000;stroke-width:30;stroke-linejoin:miter;stroke-linecap:butt;marker-end:url(#Arrow1Mend)" + id="polyline114" /> + <!-- Arrowhead on XXXpoint 8100 10350 - 8100 11010--> + <!-- Line: box --> + <rect + x="750" + y="3900" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect118" /> + <!-- Line: box --> + <rect + x="300" + y="7050" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect120" /> + <!-- Line: box --> + <rect + x="3750" + y="3900" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect122" /> + <!-- Line: box --> + <rect + x="4500" + y="5850" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect124" /> + <!-- Line: box --> + <rect + x="3300" + y="7050" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect126" /> + <!-- Line: box --> + <rect + x="2250" + y="2100" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect128" /> + <!-- Line: box --> + <rect + x="0" + y="9750" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect130" /> + <!-- Line: box --> + <rect + x="1350" + y="8550" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect132" /> + <!-- Line: box --> + <rect + x="3000" + y="9750" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect134" /> + <!-- Line: box --> + <rect + x="4350" + y="8550" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect136" /> + <!-- Line: box --> + <rect + x="1500" + y="5850" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect138" /> + <!-- Text --> + <text + xml:space="preserve" + x="8100" + y="8250" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text140">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="8100" + y="8550" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text142">rcu_head</text> + <!-- Text --> + <text + xml:space="preserve" + x="8100" + y="9750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text144">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="8100" + y="10050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text146">rcu_head</text> + <!-- Text --> + <text + xml:space="preserve" + x="8100" + y="11250" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text148">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="8100" + y="11550" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text150">rcu_head</text> + <!-- Text --> + <text + xml:space="preserve" + x="6000" + y="1200" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text152">rcu_sched</text> + <!-- Text --> + <text + xml:space="preserve" + x="6450" + y="750" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text154">rcu_bh</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="2400" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text156">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="2700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text158">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="1650" + y="4200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text160">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1650" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text162">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="4650" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text164">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="4650" + y="4200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text166">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="6150" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text168">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="6450" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text170">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="7350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text172">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="7650" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text174">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="5250" + y="6150" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text176">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5250" + y="6450" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text178">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="7350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text180">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="7650" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text182">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="450" + y="1800" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="start" + id="text184">struct rcu_state</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="10050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text186">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="10350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text188">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="10050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text190">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="10350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text192">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="2400" + y="8850" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text194">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2400" + y="9150" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text196">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="5400" + y="8850" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text198">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5400" + y="9150" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text200">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="6900" + y="300" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text202">rcu_preempt</text> + <!-- Line --> + <polyline + points="5250,5850 5250,4864 " + style="stroke:#00d1d1;stroke-width:29.99463964;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline204" /> + <!-- Arrowhead on XXXpoint 5250 5850 - 5250 4740--> + </g> +</svg> diff --git a/Documentation/RCU/Design/Data-Structures/Data-Structures.html b/Documentation/RCU/Design/Data-Structures/Data-Structures.html new file mode 100644 index 000000000..f5120a00f --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/Data-Structures.html @@ -0,0 +1,1462 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" + "http://www.w3.org/TR/html4/loose.dtd"> + <html> + <head><title>A Tour Through TREE_RCU's Data Structures [LWN.net]</title> + <meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1"> + + <p>December 18, 2016</p> + <p>This article was contributed by Paul E. McKenney</p> + +<h3>Introduction</h3> + +This document describes RCU's major data structures and their relationship +to each other. + +<ol> +<li> <a href="#Data-Structure Relationships"> + Data-Structure Relationships</a> +<li> <a href="#The rcu_state Structure"> + The <tt>rcu_state</tt> Structure</a> +<li> <a href="#The rcu_node Structure"> + The <tt>rcu_node</tt> Structure</a> +<li> <a href="#The rcu_segcblist Structure"> + The <tt>rcu_segcblist</tt> Structure</a> +<li> <a href="#The rcu_data Structure"> + The <tt>rcu_data</tt> Structure</a> +<li> <a href="#The rcu_dynticks Structure"> + The <tt>rcu_dynticks</tt> Structure</a> +<li> <a href="#The rcu_head Structure"> + The <tt>rcu_head</tt> Structure</a> +<li> <a href="#RCU-Specific Fields in the task_struct Structure"> + RCU-Specific Fields in the <tt>task_struct</tt> Structure</a> +<li> <a href="#Accessor Functions"> + Accessor Functions</a> +</ol> + +<h3><a name="Data-Structure Relationships">Data-Structure Relationships</a></h3> + +<p>RCU is for all intents and purposes a large state machine, and its +data structures maintain the state in such a way as to allow RCU readers +to execute extremely quickly, while also processing the RCU grace periods +requested by updaters in an efficient and extremely scalable fashion. +The efficiency and scalability of RCU updaters is provided primarily +by a combining tree, as shown below: + +</p><p><img src="BigTreeClassicRCU.svg" alt="BigTreeClassicRCU.svg" width="30%"> + +</p><p>This diagram shows an enclosing <tt>rcu_state</tt> structure +containing a tree of <tt>rcu_node</tt> structures. +Each leaf node of the <tt>rcu_node</tt> tree has up to 16 +<tt>rcu_data</tt> structures associated with it, so that there +are <tt>NR_CPUS</tt> number of <tt>rcu_data</tt> structures, +one for each possible CPU. +This structure is adjusted at boot time, if needed, to handle the +common case where <tt>nr_cpu_ids</tt> is much less than +<tt>NR_CPUs</tt>. +For example, a number of Linux distributions set <tt>NR_CPUs=4096</tt>, +which results in a three-level <tt>rcu_node</tt> tree. +If the actual hardware has only 16 CPUs, RCU will adjust itself +at boot time, resulting in an <tt>rcu_node</tt> tree with only a single node. + +</p><p>The purpose of this combining tree is to allow per-CPU events +such as quiescent states, dyntick-idle transitions, +and CPU hotplug operations to be processed efficiently +and scalably. +Quiescent states are recorded by the per-CPU <tt>rcu_data</tt> structures, +and other events are recorded by the leaf-level <tt>rcu_node</tt> +structures. +All of these events are combined at each level of the tree until finally +grace periods are completed at the tree's root <tt>rcu_node</tt> +structure. +A grace period can be completed at the root once every CPU +(or, in the case of <tt>CONFIG_PREEMPT_RCU</tt>, task) +has passed through a quiescent state. +Once a grace period has completed, record of that fact is propagated +back down the tree. + +</p><p>As can be seen from the diagram, on a 64-bit system +a two-level tree with 64 leaves can accommodate 1,024 CPUs, with a fanout +of 64 at the root and a fanout of 16 at the leaves. + +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Why isn't the fanout at the leaves also 64? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + Because there are more types of events that affect the leaf-level + <tt>rcu_node</tt> structures than further up the tree. + Therefore, if the leaf <tt>rcu_node</tt> structures have fanout of + 64, the contention on these structures' <tt>->structures</tt> + becomes excessive. + Experimentation on a wide variety of systems has shown that a fanout + of 16 works well for the leaves of the <tt>rcu_node</tt> tree. + </font> + + <p><font color="ffffff">Of course, further experience with + systems having hundreds or thousands of CPUs may demonstrate + that the fanout for the non-leaf <tt>rcu_node</tt> structures + must also be reduced. + Such reduction can be easily carried out when and if it proves + necessary. + In the meantime, if you are using such a system and running into + contention problems on the non-leaf <tt>rcu_node</tt> structures, + you may use the <tt>CONFIG_RCU_FANOUT</tt> kernel configuration + parameter to reduce the non-leaf fanout as needed. + </font> + + <p><font color="ffffff">Kernels built for systems with + strong NUMA characteristics might also need to adjust + <tt>CONFIG_RCU_FANOUT</tt> so that the domains of the + <tt>rcu_node</tt> structures align with hardware boundaries. + However, there has thus far been no need for this. +</font></td></tr> +<tr><td> </td></tr> +</table> + +<p>If your system has more than 1,024 CPUs (or more than 512 CPUs on +a 32-bit system), then RCU will automatically add more levels to the +tree. +For example, if you are crazy enough to build a 64-bit system with 65,536 +CPUs, RCU would configure the <tt>rcu_node</tt> tree as follows: + +</p><p><img src="HugeTreeClassicRCU.svg" alt="HugeTreeClassicRCU.svg" width="50%"> + +</p><p>RCU currently permits up to a four-level tree, which on a 64-bit system +accommodates up to 4,194,304 CPUs, though only a mere 524,288 CPUs for +32-bit systems. +On the other hand, you can set <tt>CONFIG_RCU_FANOUT</tt> to be +as small as 2 if you wish, which would permit only 16 CPUs, which +is useful for testing. + +</p><p>This multi-level combining tree allows us to get most of the +performance and scalability +benefits of partitioning, even though RCU grace-period detection is +inherently a global operation. +The trick here is that only the last CPU to report a quiescent state +into a given <tt>rcu_node</tt> structure need advance to the <tt>rcu_node</tt> +structure at the next level up the tree. +This means that at the leaf-level <tt>rcu_node</tt> structure, only +one access out of sixteen will progress up the tree. +For the internal <tt>rcu_node</tt> structures, the situation is even +more extreme: Only one access out of sixty-four will progress up +the tree. +Because the vast majority of the CPUs do not progress up the tree, +the lock contention remains roughly constant up the tree. +No matter how many CPUs there are in the system, at most 64 quiescent-state +reports per grace period will progress all the way to the root +<tt>rcu_node</tt> structure, thus ensuring that the lock contention +on that root <tt>rcu_node</tt> structure remains acceptably low. + +</p><p>In effect, the combining tree acts like a big shock absorber, +keeping lock contention under control at all tree levels regardless +of the level of loading on the system. + +</p><p>The Linux kernel actually supports multiple flavors of RCU +running concurrently, so RCU builds separate data structures for each +flavor. +For example, for <tt>CONFIG_TREE_RCU=y</tt> kernels, RCU provides +rcu_sched and rcu_bh, as shown below: + +</p><p><img src="BigTreeClassicRCUBH.svg" alt="BigTreeClassicRCUBH.svg" width="33%"> + +</p><p>Energy efficiency is increasingly important, and for that +reason the Linux kernel provides <tt>CONFIG_NO_HZ_IDLE</tt>, which +turns off the scheduling-clock interrupts on idle CPUs, which in +turn allows those CPUs to attain deeper sleep states and to consume +less energy. +CPUs whose scheduling-clock interrupts have been turned off are +said to be in <i>dyntick-idle mode</i>. +RCU must handle dyntick-idle CPUs specially +because RCU would otherwise wake up each CPU on every grace period, +which would defeat the whole purpose of <tt>CONFIG_NO_HZ_IDLE</tt>. +RCU uses the <tt>rcu_dynticks</tt> structure to track +which CPUs are in dyntick idle mode, as shown below: + +</p><p><img src="BigTreeClassicRCUBHdyntick.svg" alt="BigTreeClassicRCUBHdyntick.svg" width="33%"> + +</p><p>However, if a CPU is in dyntick-idle mode, it is in that mode +for all flavors of RCU. +Therefore, a single <tt>rcu_dynticks</tt> structure is allocated per +CPU, and all of a given CPU's <tt>rcu_data</tt> structures share +that <tt>rcu_dynticks</tt>, as shown in the figure. + +</p><p>Kernels built with <tt>CONFIG_PREEMPT_RCU</tt> support +rcu_preempt in addition to rcu_sched and rcu_bh, as shown below: + +</p><p><img src="BigTreePreemptRCUBHdyntick.svg" alt="BigTreePreemptRCUBHdyntick.svg" width="35%"> + +</p><p>RCU updaters wait for normal grace periods by registering +RCU callbacks, either directly via <tt>call_rcu()</tt> and +friends (namely <tt>call_rcu_bh()</tt> and <tt>call_rcu_sched()</tt>), +there being a separate interface per flavor of RCU) +or indirectly via <tt>synchronize_rcu()</tt> and friends. +RCU callbacks are represented by <tt>rcu_head</tt> structures, +which are queued on <tt>rcu_data</tt> structures while they are +waiting for a grace period to elapse, as shown in the following figure: + +</p><p><img src="BigTreePreemptRCUBHdyntickCB.svg" alt="BigTreePreemptRCUBHdyntickCB.svg" width="40%"> + +</p><p>This figure shows how <tt>TREE_RCU</tt>'s and +<tt>PREEMPT_RCU</tt>'s major data structures are related. +Lesser data structures will be introduced with the algorithms that +make use of them. + +</p><p>Note that each of the data structures in the above figure has +its own synchronization: + +<p><ol> +<li> Each <tt>rcu_state</tt> structures has a lock and a mutex, + and some fields are protected by the corresponding root + <tt>rcu_node</tt> structure's lock. +<li> Each <tt>rcu_node</tt> structure has a spinlock. +<li> The fields in <tt>rcu_data</tt> are private to the corresponding + CPU, although a few can be read and written by other CPUs. +<li> Similarly, the fields in <tt>rcu_dynticks</tt> are private + to the corresponding CPU, although a few can be read by + other CPUs. +</ol> + +<p>It is important to note that different data structures can have +very different ideas about the state of RCU at any given time. +For but one example, awareness of the start or end of a given RCU +grace period propagates slowly through the data structures. +This slow propagation is absolutely necessary for RCU to have good +read-side performance. +If this balkanized implementation seems foreign to you, one useful +trick is to consider each instance of these data structures to be +a different person, each having the usual slightly different +view of reality. + +</p><p>The general role of each of these data structures is as +follows: + +</p><ol> +<li> <tt>rcu_state</tt>: + This structure forms the interconnection between the + <tt>rcu_node</tt> and <tt>rcu_data</tt> structures, + tracks grace periods, serves as short-term repository + for callbacks orphaned by CPU-hotplug events, + maintains <tt>rcu_barrier()</tt> state, + tracks expedited grace-period state, + and maintains state used to force quiescent states when + grace periods extend too long, +<li> <tt>rcu_node</tt>: This structure forms the combining + tree that propagates quiescent-state + information from the leaves to the root, and also propagates + grace-period information from the root to the leaves. + It provides local copies of the grace-period state in order + to allow this information to be accessed in a synchronized + manner without suffering the scalability limitations that + would otherwise be imposed by global locking. + In <tt>CONFIG_PREEMPT_RCU</tt> kernels, it manages the lists + of tasks that have blocked while in their current + RCU read-side critical section. + In <tt>CONFIG_PREEMPT_RCU</tt> with + <tt>CONFIG_RCU_BOOST</tt>, it manages the + per-<tt>rcu_node</tt> priority-boosting + kernel threads (kthreads) and state. + Finally, it records CPU-hotplug state in order to determine + which CPUs should be ignored during a given grace period. +<li> <tt>rcu_data</tt>: This per-CPU structure is the + focus of quiescent-state detection and RCU callback queuing. + It also tracks its relationship to the corresponding leaf + <tt>rcu_node</tt> structure to allow more-efficient + propagation of quiescent states up the <tt>rcu_node</tt> + combining tree. + Like the <tt>rcu_node</tt> structure, it provides a local + copy of the grace-period information to allow for-free + synchronized + access to this information from the corresponding CPU. + Finally, this structure records past dyntick-idle state + for the corresponding CPU and also tracks statistics. +<li> <tt>rcu_dynticks</tt>: + This per-CPU structure tracks the current dyntick-idle + state for the corresponding CPU. + Unlike the other three structures, the <tt>rcu_dynticks</tt> + structure is not replicated per RCU flavor. +<li> <tt>rcu_head</tt>: + This structure represents RCU callbacks, and is the + only structure allocated and managed by RCU users. + The <tt>rcu_head</tt> structure is normally embedded + within the RCU-protected data structure. +</ol> + +<p>If all you wanted from this article was a general notion of how +RCU's data structures are related, you are done. +Otherwise, each of the following sections give more details on +the <tt>rcu_state</tt>, <tt>rcu_node</tt>, <tt>rcu_data</tt>, +and <tt>rcu_dynticks</tt> data structures. + +<h3><a name="The rcu_state Structure"> +The <tt>rcu_state</tt> Structure</a></h3> + +<p>The <tt>rcu_state</tt> structure is the base structure that +represents a flavor of RCU. +This structure forms the interconnection between the +<tt>rcu_node</tt> and <tt>rcu_data</tt> structures, +tracks grace periods, contains the lock used to +synchronize with CPU-hotplug events, +and maintains state used to force quiescent states when +grace periods extend too long, + +</p><p>A few of the <tt>rcu_state</tt> structure's fields are discussed, +singly and in groups, in the following sections. +The more specialized fields are covered in the discussion of their +use. + +<h5>Relationship to rcu_node and rcu_data Structures</h5> + +This portion of the <tt>rcu_state</tt> structure is declared +as follows: + +<pre> + 1 struct rcu_node node[NUM_RCU_NODES]; + 2 struct rcu_node *level[NUM_RCU_LVLS + 1]; + 3 struct rcu_data __percpu *rda; +</pre> + +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Wait a minute! + You said that the <tt>rcu_node</tt> structures formed a tree, + but they are declared as a flat array! + What gives? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + The tree is laid out in the array. + The first node In the array is the head, the next set of nodes in the + array are children of the head node, and so on until the last set of + nodes in the array are the leaves. + </font> + + <p><font color="ffffff">See the following diagrams to see how + this works. +</font></td></tr> +<tr><td> </td></tr> +</table> + +<p>The <tt>rcu_node</tt> tree is embedded into the +<tt>->node[]</tt> array as shown in the following figure: + +</p><p><img src="TreeMapping.svg" alt="TreeMapping.svg" width="40%"> + +</p><p>One interesting consequence of this mapping is that a +breadth-first traversal of the tree is implemented as a simple +linear scan of the array, which is in fact what the +<tt>rcu_for_each_node_breadth_first()</tt> macro does. +This macro is used at the beginning and ends of grace periods. + +</p><p>Each entry of the <tt>->level</tt> array references +the first <tt>rcu_node</tt> structure on the corresponding level +of the tree, for example, as shown below: + +</p><p><img src="TreeMappingLevel.svg" alt="TreeMappingLevel.svg" width="40%"> + +</p><p>The zero<sup>th</sup> element of the array references the root +<tt>rcu_node</tt> structure, the first element references the +first child of the root <tt>rcu_node</tt>, and finally the second +element references the first leaf <tt>rcu_node</tt> structure. + +</p><p>For whatever it is worth, if you draw the tree to be tree-shaped +rather than array-shaped, it is easy to draw a planar representation: + +</p><p><img src="TreeLevel.svg" alt="TreeLevel.svg" width="60%"> + +</p><p>Finally, the <tt>->rda</tt> field references a per-CPU +pointer to the corresponding CPU's <tt>rcu_data</tt> structure. + +</p><p>All of these fields are constant once initialization is complete, +and therefore need no protection. + +<h5>Grace-Period Tracking</h5> + +<p>This portion of the <tt>rcu_state</tt> structure is declared +as follows: + +<pre> + 1 unsigned long gp_seq; +</pre> + +<p>RCU grace periods are numbered, and +the <tt>->gp_seq</tt> field contains the current grace-period +sequence number. +The bottom two bits are the state of the current grace period, +which can be zero for not yet started or one for in progress. +In other words, if the bottom two bits of <tt>->gp_seq</tt> are +zero, the corresponding flavor of RCU is idle. +Any other value in the bottom two bits indicates that something is broken. +This field is protected by the root <tt>rcu_node</tt> structure's +<tt>->lock</tt> field. + +</p><p>There are <tt>->gp_seq</tt> fields +in the <tt>rcu_node</tt> and <tt>rcu_data</tt> structures +as well. +The fields in the <tt>rcu_state</tt> structure represent the +most current value, and those of the other structures are compared +in order to detect the beginnings and ends of grace periods in a distributed +fashion. +The values flow from <tt>rcu_state</tt> to <tt>rcu_node</tt> +(down the tree from the root to the leaves) to <tt>rcu_data</tt>. + +<h5>Miscellaneous</h5> + +<p>This portion of the <tt>rcu_state</tt> structure is declared +as follows: + +<pre> + 1 unsigned long gp_max; + 2 char abbr; + 3 char *name; +</pre> + +<p>The <tt>->gp_max</tt> field tracks the duration of the longest +grace period in jiffies. +It is protected by the root <tt>rcu_node</tt>'s <tt>->lock</tt>. + +<p>The <tt>->name</tt> field points to the name of the RCU flavor +(for example, “rcu_sched”), and is constant. +The <tt>->abbr</tt> field contains a one-character abbreviation, +for example, “s” for RCU-sched. + +<h3><a name="The rcu_node Structure"> +The <tt>rcu_node</tt> Structure</a></h3> + +<p>The <tt>rcu_node</tt> structures form the combining +tree that propagates quiescent-state +information from the leaves to the root and also that propagates +grace-period information from the root down to the leaves. +They provides local copies of the grace-period state in order +to allow this information to be accessed in a synchronized +manner without suffering the scalability limitations that +would otherwise be imposed by global locking. +In <tt>CONFIG_PREEMPT_RCU</tt> kernels, they manage the lists +of tasks that have blocked while in their current +RCU read-side critical section. +In <tt>CONFIG_PREEMPT_RCU</tt> with +<tt>CONFIG_RCU_BOOST</tt>, they manage the +per-<tt>rcu_node</tt> priority-boosting +kernel threads (kthreads) and state. +Finally, they record CPU-hotplug state in order to determine +which CPUs should be ignored during a given grace period. + +</p><p>The <tt>rcu_node</tt> structure's fields are discussed, +singly and in groups, in the following sections. + +<h5>Connection to Combining Tree</h5> + +<p>This portion of the <tt>rcu_node</tt> structure is declared +as follows: + +<pre> + 1 struct rcu_node *parent; + 2 u8 level; + 3 u8 grpnum; + 4 unsigned long grpmask; + 5 int grplo; + 6 int grphi; +</pre> + +<p>The <tt>->parent</tt> pointer references the <tt>rcu_node</tt> +one level up in the tree, and is <tt>NULL</tt> for the root +<tt>rcu_node</tt>. +The RCU implementation makes heavy use of this field to push quiescent +states up the tree. +The <tt>->level</tt> field gives the level in the tree, with +the root being at level zero, its children at level one, and so on. +The <tt>->grpnum</tt> field gives this node's position within +the children of its parent, so this number can range between 0 and 31 +on 32-bit systems and between 0 and 63 on 64-bit systems. +The <tt>->level</tt> and <tt>->grpnum</tt> fields are +used only during initialization and for tracing. +The <tt>->grpmask</tt> field is the bitmask counterpart of +<tt>->grpnum</tt>, and therefore always has exactly one bit set. +This mask is used to clear the bit corresponding to this <tt>rcu_node</tt> +structure in its parent's bitmasks, which are described later. +Finally, the <tt>->grplo</tt> and <tt>->grphi</tt> fields +contain the lowest and highest numbered CPU served by this +<tt>rcu_node</tt> structure, respectively. + +</p><p>All of these fields are constant, and thus do not require any +synchronization. + +<h5>Synchronization</h5> + +<p>This field of the <tt>rcu_node</tt> structure is declared +as follows: + +<pre> + 1 raw_spinlock_t lock; +</pre> + +<p>This field is used to protect the remaining fields in this structure, +unless otherwise stated. +That said, all of the fields in this structure can be accessed without +locking for tracing purposes. +Yes, this can result in confusing traces, but better some tracing confusion +than to be heisenbugged out of existence. + +<h5>Grace-Period Tracking</h5> + +<p>This portion of the <tt>rcu_node</tt> structure is declared +as follows: + +<pre> + 1 unsigned long gp_seq; + 2 unsigned long gp_seq_needed; +</pre> + +<p>The <tt>rcu_node</tt> structures' <tt>->gp_seq</tt> fields are +the counterparts of the field of the same name in the <tt>rcu_state</tt> +structure. +They each may lag up to one step behind their <tt>rcu_state</tt> +counterpart. +If the bottom two bits of a given <tt>rcu_node</tt> structure's +<tt>->gp_seq</tt> field is zero, then this <tt>rcu_node</tt> +structure believes that RCU is idle. +</p><p>The <tt>>gp_seq</tt> field of each <tt>rcu_node</tt> +structure is updated at the beginning and the end +of each grace period. + +<p>The <tt>->gp_seq_needed</tt> fields record the +furthest-in-the-future grace period request seen by the corresponding +<tt>rcu_node</tt> structure. The request is considered fulfilled when +the value of the <tt>->gp_seq</tt> field equals or exceeds that of +the <tt>->gp_seq_needed</tt> field. + +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Suppose that this <tt>rcu_node</tt> structure doesn't see + a request for a very long time. + Won't wrapping of the <tt>->gp_seq</tt> field cause + problems? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + No, because if the <tt>->gp_seq_needed</tt> field lags behind the + <tt>->gp_seq</tt> field, the <tt>->gp_seq_needed</tt> field + will be updated at the end of the grace period. + Modulo-arithmetic comparisons therefore will always get the + correct answer, even with wrapping. +</font></td></tr> +<tr><td> </td></tr> +</table> + +<h5>Quiescent-State Tracking</h5> + +<p>These fields manage the propagation of quiescent states up the +combining tree. + +</p><p>This portion of the <tt>rcu_node</tt> structure has fields +as follows: + +<pre> + 1 unsigned long qsmask; + 2 unsigned long expmask; + 3 unsigned long qsmaskinit; + 4 unsigned long expmaskinit; +</pre> + +<p>The <tt>->qsmask</tt> field tracks which of this +<tt>rcu_node</tt> structure's children still need to report +quiescent states for the current normal grace period. +Such children will have a value of 1 in their corresponding bit. +Note that the leaf <tt>rcu_node</tt> structures should be +thought of as having <tt>rcu_data</tt> structures as their +children. +Similarly, the <tt>->expmask</tt> field tracks which +of this <tt>rcu_node</tt> structure's children still need to report +quiescent states for the current expedited grace period. +An expedited grace period has +the same conceptual properties as a normal grace period, but the +expedited implementation accepts extreme CPU overhead to obtain +much lower grace-period latency, for example, consuming a few +tens of microseconds worth of CPU time to reduce grace-period +duration from milliseconds to tens of microseconds. +The <tt>->qsmaskinit</tt> field tracks which of this +<tt>rcu_node</tt> structure's children cover for at least +one online CPU. +This mask is used to initialize <tt>->qsmask</tt>, +and <tt>->expmaskinit</tt> is used to initialize +<tt>->expmask</tt> and the beginning of the +normal and expedited grace periods, respectively. + +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Why are these bitmasks protected by locking? + Come on, haven't you heard of atomic instructions??? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + Lockless grace-period computation! Such a tantalizing possibility! + </font> + + <p><font color="ffffff">But consider the following sequence of events: + </font> + + <ol> + <li> <font color="ffffff">CPU 0 has been in dyntick-idle + mode for quite some time. + When it wakes up, it notices that the current RCU + grace period needs it to report in, so it sets a + flag where the scheduling clock interrupt will find it. + </font><p> + <li> <font color="ffffff">Meanwhile, CPU 1 is running + <tt>force_quiescent_state()</tt>, + and notices that CPU 0 has been in dyntick idle mode, + which qualifies as an extended quiescent state. + </font><p> + <li> <font color="ffffff">CPU 0's scheduling clock + interrupt fires in the + middle of an RCU read-side critical section, and notices + that the RCU core needs something, so commences RCU softirq + processing. + </font> + <p> + <li> <font color="ffffff">CPU 0's softirq handler + executes and is just about ready + to report its quiescent state up the <tt>rcu_node</tt> + tree. + </font><p> + <li> <font color="ffffff">But CPU 1 beats it to the punch, + completing the current + grace period and starting a new one. + </font><p> + <li> <font color="ffffff">CPU 0 now reports its quiescent + state for the wrong + grace period. + That grace period might now end before the RCU read-side + critical section. + If that happens, disaster will ensue. + </font> + </ol> + + <p><font color="ffffff">So the locking is absolutely required in + order to coordinate clearing of the bits with updating of the + grace-period sequence number in <tt>->gp_seq</tt>. +</font></td></tr> +<tr><td> </td></tr> +</table> + +<h5>Blocked-Task Management</h5> + +<p><tt>PREEMPT_RCU</tt> allows tasks to be preempted in the +midst of their RCU read-side critical sections, and these tasks +must be tracked explicitly. +The details of exactly why and how they are tracked will be covered +in a separate article on RCU read-side processing. +For now, it is enough to know that the <tt>rcu_node</tt> +structure tracks them. + +<pre> + 1 struct list_head blkd_tasks; + 2 struct list_head *gp_tasks; + 3 struct list_head *exp_tasks; + 4 bool wait_blkd_tasks; +</pre> + +<p>The <tt>->blkd_tasks</tt> field is a list header for +the list of blocked and preempted tasks. +As tasks undergo context switches within RCU read-side critical +sections, their <tt>task_struct</tt> structures are enqueued +(via the <tt>task_struct</tt>'s <tt>->rcu_node_entry</tt> +field) onto the head of the <tt>->blkd_tasks</tt> list for the +leaf <tt>rcu_node</tt> structure corresponding to the CPU +on which the outgoing context switch executed. +As these tasks later exit their RCU read-side critical sections, +they remove themselves from the list. +This list is therefore in reverse time order, so that if one of the tasks +is blocking the current grace period, all subsequent tasks must +also be blocking that same grace period. +Therefore, a single pointer into this list suffices to track +all tasks blocking a given grace period. +That pointer is stored in <tt>->gp_tasks</tt> for normal +grace periods and in <tt>->exp_tasks</tt> for expedited +grace periods. +These last two fields are <tt>NULL</tt> if either there is +no grace period in flight or if there are no blocked tasks +preventing that grace period from completing. +If either of these two pointers is referencing a task that +removes itself from the <tt>->blkd_tasks</tt> list, +then that task must advance the pointer to the next task on +the list, or set the pointer to <tt>NULL</tt> if there +are no subsequent tasks on the list. + +</p><p>For example, suppose that tasks T1, T2, and T3 are +all hard-affinitied to the largest-numbered CPU in the system. +Then if task T1 blocked in an RCU read-side +critical section, then an expedited grace period started, +then task T2 blocked in an RCU read-side critical section, +then a normal grace period started, and finally task 3 blocked +in an RCU read-side critical section, then the state of the +last leaf <tt>rcu_node</tt> structure's blocked-task list +would be as shown below: + +</p><p><img src="blkd_task.svg" alt="blkd_task.svg" width="60%"> + +</p><p>Task T1 is blocking both grace periods, task T2 is +blocking only the normal grace period, and task T3 is blocking +neither grace period. +Note that these tasks will not remove themselves from this list +immediately upon resuming execution. +They will instead remain on the list until they execute the outermost +<tt>rcu_read_unlock()</tt> that ends their RCU read-side critical +section. + +<p> +The <tt>->wait_blkd_tasks</tt> field indicates whether or not +the current grace period is waiting on a blocked task. + +<h5>Sizing the <tt>rcu_node</tt> Array</h5> + +<p>The <tt>rcu_node</tt> array is sized via a series of +C-preprocessor expressions as follows: + +<pre> + 1 #ifdef CONFIG_RCU_FANOUT + 2 #define RCU_FANOUT CONFIG_RCU_FANOUT + 3 #else + 4 # ifdef CONFIG_64BIT + 5 # define RCU_FANOUT 64 + 6 # else + 7 # define RCU_FANOUT 32 + 8 # endif + 9 #endif +10 +11 #ifdef CONFIG_RCU_FANOUT_LEAF +12 #define RCU_FANOUT_LEAF CONFIG_RCU_FANOUT_LEAF +13 #else +14 # ifdef CONFIG_64BIT +15 # define RCU_FANOUT_LEAF 64 +16 # else +17 # define RCU_FANOUT_LEAF 32 +18 # endif +19 #endif +20 +21 #define RCU_FANOUT_1 (RCU_FANOUT_LEAF) +22 #define RCU_FANOUT_2 (RCU_FANOUT_1 * RCU_FANOUT) +23 #define RCU_FANOUT_3 (RCU_FANOUT_2 * RCU_FANOUT) +24 #define RCU_FANOUT_4 (RCU_FANOUT_3 * RCU_FANOUT) +25 +26 #if NR_CPUS <= RCU_FANOUT_1 +27 # define RCU_NUM_LVLS 1 +28 # define NUM_RCU_LVL_0 1 +29 # define NUM_RCU_NODES NUM_RCU_LVL_0 +30 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0 } +31 # define RCU_NODE_NAME_INIT { "rcu_node_0" } +32 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0" } +33 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0" } +34 #elif NR_CPUS <= RCU_FANOUT_2 +35 # define RCU_NUM_LVLS 2 +36 # define NUM_RCU_LVL_0 1 +37 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1) +38 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1) +39 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1 } +40 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1" } +41 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1" } +42 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1" } +43 #elif NR_CPUS <= RCU_FANOUT_3 +44 # define RCU_NUM_LVLS 3 +45 # define NUM_RCU_LVL_0 1 +46 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2) +47 # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1) +48 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2) +49 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2 } +50 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1", "rcu_node_2" } +51 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2" } +52 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2" } +53 #elif NR_CPUS <= RCU_FANOUT_4 +54 # define RCU_NUM_LVLS 4 +55 # define NUM_RCU_LVL_0 1 +56 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_3) +57 # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2) +58 # define NUM_RCU_LVL_3 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1) +59 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3) +60 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2, NUM_RCU_LVL_3 } +61 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1", "rcu_node_2", "rcu_node_3" } +62 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2", "rcu_node_fqs_3" } +63 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2", "rcu_node_exp_3" } +64 #else +65 # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS" +66 #endif +</pre> + +<p>The maximum number of levels in the <tt>rcu_node</tt> structure +is currently limited to four, as specified by lines 21-24 +and the structure of the subsequent “if” statement. +For 32-bit systems, this allows 16*32*32*32=524,288 CPUs, which +should be sufficient for the next few years at least. +For 64-bit systems, 16*64*64*64=4,194,304 CPUs is allowed, which +should see us through the next decade or so. +This four-level tree also allows kernels built with +<tt>CONFIG_RCU_FANOUT=8</tt> to support up to 4096 CPUs, +which might be useful in very large systems having eight CPUs per +socket (but please note that no one has yet shown any measurable +performance degradation due to misaligned socket and <tt>rcu_node</tt> +boundaries). +In addition, building kernels with a full four levels of <tt>rcu_node</tt> +tree permits better testing of RCU's combining-tree code. + +</p><p>The <tt>RCU_FANOUT</tt> symbol controls how many children +are permitted at each non-leaf level of the <tt>rcu_node</tt> tree. +If the <tt>CONFIG_RCU_FANOUT</tt> Kconfig option is not specified, +it is set based on the word size of the system, which is also +the Kconfig default. + +</p><p>The <tt>RCU_FANOUT_LEAF</tt> symbol controls how many CPUs are +handled by each leaf <tt>rcu_node</tt> structure. +Experience has shown that allowing a given leaf <tt>rcu_node</tt> +structure to handle 64 CPUs, as permitted by the number of bits in +the <tt>->qsmask</tt> field on a 64-bit system, results in +excessive contention for the leaf <tt>rcu_node</tt> structures' +<tt>->lock</tt> fields. +The number of CPUs per leaf <tt>rcu_node</tt> structure is therefore +limited to 16 given the default value of <tt>CONFIG_RCU_FANOUT_LEAF</tt>. +If <tt>CONFIG_RCU_FANOUT_LEAF</tt> is unspecified, the value +selected is based on the word size of the system, just as for +<tt>CONFIG_RCU_FANOUT</tt>. +Lines 11-19 perform this computation. + +</p><p>Lines 21-24 compute the maximum number of CPUs supported by +a single-level (which contains a single <tt>rcu_node</tt> structure), +two-level, three-level, and four-level <tt>rcu_node</tt> tree, +respectively, given the fanout specified by <tt>RCU_FANOUT</tt> +and <tt>RCU_FANOUT_LEAF</tt>. +These numbers of CPUs are retained in the +<tt>RCU_FANOUT_1</tt>, +<tt>RCU_FANOUT_2</tt>, +<tt>RCU_FANOUT_3</tt>, and +<tt>RCU_FANOUT_4</tt> +C-preprocessor variables, respectively. + +</p><p>These variables are used to control the C-preprocessor <tt>#if</tt> +statement spanning lines 26-66 that computes the number of +<tt>rcu_node</tt> structures required for each level of the tree, +as well as the number of levels required. +The number of levels is placed in the <tt>NUM_RCU_LVLS</tt> +C-preprocessor variable by lines 27, 35, 44, and 54. +The number of <tt>rcu_node</tt> structures for the topmost level +of the tree is always exactly one, and this value is unconditionally +placed into <tt>NUM_RCU_LVL_0</tt> by lines 28, 36, 45, and 55. +The rest of the levels (if any) of the <tt>rcu_node</tt> tree +are computed by dividing the maximum number of CPUs by the +fanout supported by the number of levels from the current level down, +rounding up. This computation is performed by lines 37, +46-47, and 56-58. +Lines 31-33, 40-42, 50-52, and 62-63 create initializers +for lockdep lock-class names. +Finally, lines 64-66 produce an error if the maximum number of +CPUs is too large for the specified fanout. + +<h3><a name="The rcu_segcblist Structure"> +The <tt>rcu_segcblist</tt> Structure</a></h3> + +The <tt>rcu_segcblist</tt> structure maintains a segmented list of +callbacks as follows: + +<pre> + 1 #define RCU_DONE_TAIL 0 + 2 #define RCU_WAIT_TAIL 1 + 3 #define RCU_NEXT_READY_TAIL 2 + 4 #define RCU_NEXT_TAIL 3 + 5 #define RCU_CBLIST_NSEGS 4 + 6 + 7 struct rcu_segcblist { + 8 struct rcu_head *head; + 9 struct rcu_head **tails[RCU_CBLIST_NSEGS]; +10 unsigned long gp_seq[RCU_CBLIST_NSEGS]; +11 long len; +12 long len_lazy; +13 }; +</pre> + +<p> +The segments are as follows: + +<ol> +<li> <tt>RCU_DONE_TAIL</tt>: Callbacks whose grace periods have elapsed. + These callbacks are ready to be invoked. +<li> <tt>RCU_WAIT_TAIL</tt>: Callbacks that are waiting for the + current grace period. + Note that different CPUs can have different ideas about which + grace period is current, hence the <tt>->gp_seq</tt> field. +<li> <tt>RCU_NEXT_READY_TAIL</tt>: Callbacks waiting for the next + grace period to start. +<li> <tt>RCU_NEXT_TAIL</tt>: Callbacks that have not yet been + associated with a grace period. +</ol> + +<p> +The <tt>->head</tt> pointer references the first callback or +is <tt>NULL</tt> if the list contains no callbacks (which is +<i>not</i> the same as being empty). +Each element of the <tt>->tails[]</tt> array references the +<tt>->next</tt> pointer of the last callback in the corresponding +segment of the list, or the list's <tt>->head</tt> pointer if +that segment and all previous segments are empty. +If the corresponding segment is empty but some previous segment is +not empty, then the array element is identical to its predecessor. +Older callbacks are closer to the head of the list, and new callbacks +are added at the tail. +This relationship between the <tt>->head</tt> pointer, the +<tt>->tails[]</tt> array, and the callbacks is shown in this +diagram: + +</p><p><img src="nxtlist.svg" alt="nxtlist.svg" width="40%"> + +</p><p>In this figure, the <tt>->head</tt> pointer references the +first +RCU callback in the list. +The <tt>->tails[RCU_DONE_TAIL]</tt> array element references +the <tt>->head</tt> pointer itself, indicating that none +of the callbacks is ready to invoke. +The <tt>->tails[RCU_WAIT_TAIL]</tt> array element references callback +CB 2's <tt>->next</tt> pointer, which indicates that +CB 1 and CB 2 are both waiting on the current grace period, +give or take possible disagreements about exactly which grace period +is the current one. +The <tt>->tails[RCU_NEXT_READY_TAIL]</tt> array element +references the same RCU callback that <tt>->tails[RCU_WAIT_TAIL]</tt> +does, which indicates that there are no callbacks waiting on the next +RCU grace period. +The <tt>->tails[RCU_NEXT_TAIL]</tt> array element references +CB 4's <tt>->next</tt> pointer, indicating that all the +remaining RCU callbacks have not yet been assigned to an RCU grace +period. +Note that the <tt>->tails[RCU_NEXT_TAIL]</tt> array element +always references the last RCU callback's <tt>->next</tt> pointer +unless the callback list is empty, in which case it references +the <tt>->head</tt> pointer. + +<p> +There is one additional important special case for the +<tt>->tails[RCU_NEXT_TAIL]</tt> array element: It can be <tt>NULL</tt> +when this list is <i>disabled</i>. +Lists are disabled when the corresponding CPU is offline or when +the corresponding CPU's callbacks are offloaded to a kthread, +both of which are described elsewhere. + +</p><p>CPUs advance their callbacks from the +<tt>RCU_NEXT_TAIL</tt> to the <tt>RCU_NEXT_READY_TAIL</tt> to the +<tt>RCU_WAIT_TAIL</tt> to the <tt>RCU_DONE_TAIL</tt> list segments +as grace periods advance. + +</p><p>The <tt>->gp_seq[]</tt> array records grace-period +numbers corresponding to the list segments. +This is what allows different CPUs to have different ideas as to +which is the current grace period while still avoiding premature +invocation of their callbacks. +In particular, this allows CPUs that go idle for extended periods +to determine which of their callbacks are ready to be invoked after +reawakening. + +</p><p>The <tt>->len</tt> counter contains the number of +callbacks in <tt>->head</tt>, and the +<tt>->len_lazy</tt> contains the number of those callbacks that +are known to only free memory, and whose invocation can therefore +be safely deferred. + +<p><b>Important note</b>: It is the <tt>->len</tt> field that +determines whether or not there are callbacks associated with +this <tt>rcu_segcblist</tt> structure, <i>not</i> the <tt>->head</tt> +pointer. +The reason for this is that all the ready-to-invoke callbacks +(that is, those in the <tt>RCU_DONE_TAIL</tt> segment) are extracted +all at once at callback-invocation time. +If callback invocation must be postponed, for example, because a +high-priority process just woke up on this CPU, then the remaining +callbacks are placed back on the <tt>RCU_DONE_TAIL</tt> segment. +Either way, the <tt>->len</tt> and <tt>->len_lazy</tt> counts +are adjusted after the corresponding callbacks have been invoked, and so +again it is the <tt>->len</tt> count that accurately reflects whether +or not there are callbacks associated with this <tt>rcu_segcblist</tt> +structure. +Of course, off-CPU sampling of the <tt>->len</tt> count requires +the use of appropriate synchronization, for example, memory barriers. +This synchronization can be a bit subtle, particularly in the case +of <tt>rcu_barrier()</tt>. + +<h3><a name="The rcu_data Structure"> +The <tt>rcu_data</tt> Structure</a></h3> + +<p>The <tt>rcu_data</tt> maintains the per-CPU state for the +corresponding flavor of RCU. +The fields in this structure may be accessed only from the corresponding +CPU (and from tracing) unless otherwise stated. +This structure is the +focus of quiescent-state detection and RCU callback queuing. +It also tracks its relationship to the corresponding leaf +<tt>rcu_node</tt> structure to allow more-efficient +propagation of quiescent states up the <tt>rcu_node</tt> +combining tree. +Like the <tt>rcu_node</tt> structure, it provides a local +copy of the grace-period information to allow for-free +synchronized +access to this information from the corresponding CPU. +Finally, this structure records past dyntick-idle state +for the corresponding CPU and also tracks statistics. + +</p><p>The <tt>rcu_data</tt> structure's fields are discussed, +singly and in groups, in the following sections. + +<h5>Connection to Other Data Structures</h5> + +<p>This portion of the <tt>rcu_data</tt> structure is declared +as follows: + +<pre> + 1 int cpu; + 2 struct rcu_state *rsp; + 3 struct rcu_node *mynode; + 4 struct rcu_dynticks *dynticks; + 5 unsigned long grpmask; + 6 bool beenonline; +</pre> + +<p>The <tt>->cpu</tt> field contains the number of the +corresponding CPU, the <tt>->rsp</tt> pointer references +the corresponding <tt>rcu_state</tt> structure (and is most frequently +used to locate the name of the corresponding flavor of RCU for tracing), +and the <tt>->mynode</tt> field references the corresponding +<tt>rcu_node</tt> structure. +The <tt>->mynode</tt> is used to propagate quiescent states +up the combining tree. +<p>The <tt>->dynticks</tt> pointer references the +<tt>rcu_dynticks</tt> structure corresponding to this +CPU. +Recall that a single per-CPU instance of the <tt>rcu_dynticks</tt> +structure is shared among all flavors of RCU. +These first four fields are constant and therefore require not +synchronization. + +</p><p>The <tt>->grpmask</tt> field indicates the bit in +the <tt>->mynode->qsmask</tt> corresponding to this +<tt>rcu_data</tt> structure, and is also used when propagating +quiescent states. +The <tt>->beenonline</tt> flag is set whenever the corresponding +CPU comes online, which means that the debugfs tracing need not dump +out any <tt>rcu_data</tt> structure for which this flag is not set. + +<h5>Quiescent-State and Grace-Period Tracking</h5> + +<p>This portion of the <tt>rcu_data</tt> structure is declared +as follows: + +<pre> + 1 unsigned long gp_seq; + 2 unsigned long gp_seq_needed; + 3 bool cpu_no_qs; + 4 bool core_needs_qs; + 5 bool gpwrap; + 6 unsigned long rcu_qs_ctr_snap; +</pre> + +<p>The <tt>->gp_seq</tt> and <tt>->gp_seq_needed</tt> +fields are the counterparts of the fields of the same name +in the <tt>rcu_state</tt> and <tt>rcu_node</tt> structures. +They may each lag up to one behind their <tt>rcu_node</tt> +counterparts, but in <tt>CONFIG_NO_HZ_IDLE</tt> and +<tt>CONFIG_NO_HZ_FULL</tt> kernels can lag +arbitrarily far behind for CPUs in dyntick-idle mode (but these counters +will catch up upon exit from dyntick-idle mode). +If the lower two bits of a given <tt>rcu_data</tt> structure's +<tt>->gp_seq</tt> are zero, then this <tt>rcu_data</tt> +structure believes that RCU is idle. + +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + All this replication of the grace period numbers can only cause + massive confusion. + Why not just keep a global sequence number and be done with it??? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + Because if there was only a single global sequence + numbers, there would need to be a single global lock to allow + safely accessing and updating it. + And if we are not going to have a single global lock, we need + to carefully manage the numbers on a per-node basis. + Recall from the answer to a previous Quick Quiz that the consequences + of applying a previously sampled quiescent state to the wrong + grace period are quite severe. +</font></td></tr> +<tr><td> </td></tr> +</table> + +<p>The <tt>->cpu_no_qs</tt> flag indicates that the +CPU has not yet passed through a quiescent state, +while the <tt>->core_needs_qs</tt> flag indicates that the +RCU core needs a quiescent state from the corresponding CPU. +The <tt>->gpwrap</tt> field indicates that the corresponding +CPU has remained idle for so long that the +<tt>gp_seq</tt> counter is in danger of overflow, which +will cause the CPU to disregard the values of its counters on +its next exit from idle. +Finally, the <tt>rcu_qs_ctr_snap</tt> field is used to detect +cases where a given operation has resulted in a quiescent state +for all flavors of RCU, for example, <tt>cond_resched()</tt> +when RCU has indicated a need for quiescent states. + +<h5>RCU Callback Handling</h5> + +<p>In the absence of CPU-hotplug events, RCU callbacks are invoked by +the same CPU that registered them. +This is strictly a cache-locality optimization: callbacks can and +do get invoked on CPUs other than the one that registered them. +After all, if the CPU that registered a given callback has gone +offline before the callback can be invoked, there really is no other +choice. + +</p><p>This portion of the <tt>rcu_data</tt> structure is declared +as follows: + +<pre> + 1 struct rcu_segcblist cblist; + 2 long qlen_last_fqs_check; + 3 unsigned long n_cbs_invoked; + 4 unsigned long n_nocbs_invoked; + 5 unsigned long n_cbs_orphaned; + 6 unsigned long n_cbs_adopted; + 7 unsigned long n_force_qs_snap; + 8 long blimit; +</pre> + +<p>The <tt>->cblist</tt> structure is the segmented callback list +described earlier. +The CPU advances the callbacks in its <tt>rcu_data</tt> structure +whenever it notices that another RCU grace period has completed. +The CPU detects the completion of an RCU grace period by noticing +that the value of its <tt>rcu_data</tt> structure's +<tt>->gp_seq</tt> field differs from that of its leaf +<tt>rcu_node</tt> structure. +Recall that each <tt>rcu_node</tt> structure's +<tt>->gp_seq</tt> field is updated at the beginnings and ends of each +grace period. + +<p> +The <tt>->qlen_last_fqs_check</tt> and +<tt>->n_force_qs_snap</tt> coordinate the forcing of quiescent +states from <tt>call_rcu()</tt> and friends when callback +lists grow excessively long. + +</p><p>The <tt>->n_cbs_invoked</tt>, +<tt>->n_cbs_orphaned</tt>, and <tt>->n_cbs_adopted</tt> +fields count the number of callbacks invoked, +sent to other CPUs when this CPU goes offline, +and received from other CPUs when those other CPUs go offline. +The <tt>->n_nocbs_invoked</tt> is used when the CPU's callbacks +are offloaded to a kthread. + +<p> +Finally, the <tt>->blimit</tt> counter is the maximum number of +RCU callbacks that may be invoked at a given time. + +<h5>Dyntick-Idle Handling</h5> + +<p>This portion of the <tt>rcu_data</tt> structure is declared +as follows: + +<pre> + 1 int dynticks_snap; + 2 unsigned long dynticks_fqs; +</pre> + +The <tt>->dynticks_snap</tt> field is used to take a snapshot +of the corresponding CPU's dyntick-idle state when forcing +quiescent states, and is therefore accessed from other CPUs. +Finally, the <tt>->dynticks_fqs</tt> field is used to +count the number of times this CPU is determined to be in +dyntick-idle state, and is used for tracing and debugging purposes. + +<h3><a name="The rcu_dynticks Structure"> +The <tt>rcu_dynticks</tt> Structure</a></h3> + +<p>The <tt>rcu_dynticks</tt> maintains the per-CPU dyntick-idle state +for the corresponding CPU. +Unlike the other structures, <tt>rcu_dynticks</tt> is not +replicated over the different flavors of RCU. +The fields in this structure may be accessed only from the corresponding +CPU (and from tracing) unless otherwise stated. +Its fields are as follows: + +<pre> + 1 long dynticks_nesting; + 2 long dynticks_nmi_nesting; + 3 atomic_t dynticks; + 4 bool rcu_need_heavy_qs; + 5 unsigned long rcu_qs_ctr; + 6 bool rcu_urgent_qs; +</pre> + +<p>The <tt>->dynticks_nesting</tt> field counts the +nesting depth of process execution, so that in normal circumstances +this counter has value zero or one. +NMIs, irqs, and tracers are counted by the <tt>->dynticks_nmi_nesting</tt> +field. +Because NMIs cannot be masked, changes to this variable have to be +undertaken carefully using an algorithm provided by Andy Lutomirski. +The initial transition from idle adds one, and nested transitions +add two, so that a nesting level of five is represented by a +<tt>->dynticks_nmi_nesting</tt> value of nine. +This counter can therefore be thought of as counting the number +of reasons why this CPU cannot be permitted to enter dyntick-idle +mode, aside from process-level transitions. + +<p>However, it turns out that when running in non-idle kernel context, +the Linux kernel is fully capable of entering interrupt handlers that +never exit and perhaps also vice versa. +Therefore, whenever the <tt>->dynticks_nesting</tt> field is +incremented up from zero, the <tt>->dynticks_nmi_nesting</tt> field +is set to a large positive number, and whenever the +<tt>->dynticks_nesting</tt> field is decremented down to zero, +the the <tt>->dynticks_nmi_nesting</tt> field is set to zero. +Assuming that the number of misnested interrupts is not sufficient +to overflow the counter, this approach corrects the +<tt>->dynticks_nmi_nesting</tt> field every time the corresponding +CPU enters the idle loop from process context. + +</p><p>The <tt>->dynticks</tt> field counts the corresponding +CPU's transitions to and from dyntick-idle mode, so that this counter +has an even value when the CPU is in dyntick-idle mode and an odd +value otherwise. + +</p><p>The <tt>->rcu_need_heavy_qs</tt> field is used +to record the fact that the RCU core code would really like to +see a quiescent state from the corresponding CPU, so much so that +it is willing to call for heavy-weight dyntick-counter operations. +This flag is checked by RCU's context-switch and <tt>cond_resched()</tt> +code, which provide a momentary idle sojourn in response. + +</p><p>The <tt>->rcu_qs_ctr</tt> field is used to record +quiescent states from <tt>cond_resched()</tt>. +Because <tt>cond_resched()</tt> can execute quite frequently, this +must be quite lightweight, as in a non-atomic increment of this +per-CPU field. + +</p><p>Finally, the <tt>->rcu_urgent_qs</tt> field is used to record +the fact that the RCU core code would really like to see a quiescent +state from the corresponding CPU, with the various other fields indicating +just how badly RCU wants this quiescent state. +This flag is checked by RCU's context-switch and <tt>cond_resched()</tt> +code, which, if nothing else, non-atomically increment <tt>->rcu_qs_ctr</tt> +in response. + +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Why not simply combine the <tt>->dynticks_nesting</tt> + and <tt>->dynticks_nmi_nesting</tt> counters into a + single counter that just counts the number of reasons that + the corresponding CPU is non-idle? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + Because this would fail in the presence of interrupts whose + handlers never return and of handlers that manage to return + from a made-up interrupt. +</font></td></tr> +<tr><td> </td></tr> +</table> + +<p>Additional fields are present for some special-purpose +builds, and are discussed separately. + +<h3><a name="The rcu_head Structure"> +The <tt>rcu_head</tt> Structure</a></h3> + +<p>Each <tt>rcu_head</tt> structure represents an RCU callback. +These structures are normally embedded within RCU-protected data +structures whose algorithms use asynchronous grace periods. +In contrast, when using algorithms that block waiting for RCU grace periods, +RCU users need not provide <tt>rcu_head</tt> structures. + +</p><p>The <tt>rcu_head</tt> structure has fields as follows: + +<pre> + 1 struct rcu_head *next; + 2 void (*func)(struct rcu_head *head); +</pre> + +<p>The <tt>->next</tt> field is used +to link the <tt>rcu_head</tt> structures together in the +lists within the <tt>rcu_data</tt> structures. +The <tt>->func</tt> field is a pointer to the function +to be called when the callback is ready to be invoked, and +this function is passed a pointer to the <tt>rcu_head</tt> +structure. +However, <tt>kfree_rcu()</tt> uses the <tt>->func</tt> +field to record the offset of the <tt>rcu_head</tt> +structure within the enclosing RCU-protected data structure. + +</p><p>Both of these fields are used internally by RCU. +From the viewpoint of RCU users, this structure is an +opaque “cookie”. + +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Given that the callback function <tt>->func</tt> + is passed a pointer to the <tt>rcu_head</tt> structure, + how is that function supposed to find the beginning of the + enclosing RCU-protected data structure? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + In actual practice, there is a separate callback function per + type of RCU-protected data structure. + The callback function can therefore use the <tt>container_of()</tt> + macro in the Linux kernel (or other pointer-manipulation facilities + in other software environments) to find the beginning of the + enclosing structure. +</font></td></tr> +<tr><td> </td></tr> +</table> + +<h3><a name="RCU-Specific Fields in the task_struct Structure"> +RCU-Specific Fields in the <tt>task_struct</tt> Structure</a></h3> + +<p>The <tt>CONFIG_PREEMPT_RCU</tt> implementation uses some +additional fields in the <tt>task_struct</tt> structure: + +<pre> + 1 #ifdef CONFIG_PREEMPT_RCU + 2 int rcu_read_lock_nesting; + 3 union rcu_special rcu_read_unlock_special; + 4 struct list_head rcu_node_entry; + 5 struct rcu_node *rcu_blocked_node; + 6 #endif /* #ifdef CONFIG_PREEMPT_RCU */ + 7 #ifdef CONFIG_TASKS_RCU + 8 unsigned long rcu_tasks_nvcsw; + 9 bool rcu_tasks_holdout; +10 struct list_head rcu_tasks_holdout_list; +11 int rcu_tasks_idle_cpu; +12 #endif /* #ifdef CONFIG_TASKS_RCU */ +</pre> + +<p>The <tt>->rcu_read_lock_nesting</tt> field records the +nesting level for RCU read-side critical sections, and +the <tt>->rcu_read_unlock_special</tt> field is a bitmask +that records special conditions that require <tt>rcu_read_unlock()</tt> +to do additional work. +The <tt>->rcu_node_entry</tt> field is used to form lists of +tasks that have blocked within preemptible-RCU read-side critical +sections and the <tt>->rcu_blocked_node</tt> field references +the <tt>rcu_node</tt> structure whose list this task is a member of, +or <tt>NULL</tt> if it is not blocked within a preemptible-RCU +read-side critical section. + +<p>The <tt>->rcu_tasks_nvcsw</tt> field tracks the number of +voluntary context switches that this task had undergone at the +beginning of the current tasks-RCU grace period, +<tt>->rcu_tasks_holdout</tt> is set if the current tasks-RCU +grace period is waiting on this task, <tt>->rcu_tasks_holdout_list</tt> +is a list element enqueuing this task on the holdout list, +and <tt>->rcu_tasks_idle_cpu</tt> tracks which CPU this +idle task is running, but only if the task is currently running, +that is, if the CPU is currently idle. + +<h3><a name="Accessor Functions"> +Accessor Functions</a></h3> + +<p>The following listing shows the +<tt>rcu_get_root()</tt>, <tt>rcu_for_each_node_breadth_first</tt>, +<tt>rcu_for_each_nonleaf_node_breadth_first()</tt>, and +<tt>rcu_for_each_leaf_node()</tt> function and macros: + +<pre> + 1 static struct rcu_node *rcu_get_root(struct rcu_state *rsp) + 2 { + 3 return &rsp->node[0]; + 4 } + 5 + 6 #define rcu_for_each_node_breadth_first(rsp, rnp) \ + 7 for ((rnp) = &(rsp)->node[0]; \ + 8 (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++) + 9 + 10 #define rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) \ + 11 for ((rnp) = &(rsp)->node[0]; \ + 12 (rnp) < (rsp)->level[NUM_RCU_LVLS - 1]; (rnp)++) + 13 + 14 #define rcu_for_each_leaf_node(rsp, rnp) \ + 15 for ((rnp) = (rsp)->level[NUM_RCU_LVLS - 1]; \ + 16 (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++) +</pre> + +<p>The <tt>rcu_get_root()</tt> simply returns a pointer to the +first element of the specified <tt>rcu_state</tt> structure's +<tt>->node[]</tt> array, which is the root <tt>rcu_node</tt> +structure. + +</p><p>As noted earlier, the <tt>rcu_for_each_node_breadth_first()</tt> +macro takes advantage of the layout of the <tt>rcu_node</tt> +structures in the <tt>rcu_state</tt> structure's +<tt>->node[]</tt> array, performing a breadth-first traversal by +simply traversing the array in order. +The <tt>rcu_for_each_nonleaf_node_breadth_first()</tt> macro operates +similarly, but traverses only the first part of the array, thus excluding +the leaf <tt>rcu_node</tt> structures. +Finally, the <tt>rcu_for_each_leaf_node()</tt> macro traverses only +the last part of the array, thus traversing only the leaf +<tt>rcu_node</tt> structures. + +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + What do <tt>rcu_for_each_nonleaf_node_breadth_first()</tt> and + <tt>rcu_for_each_leaf_node()</tt> do if the <tt>rcu_node</tt> tree + contains only a single node? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + In the single-node case, + <tt>rcu_for_each_nonleaf_node_breadth_first()</tt> is a no-op + and <tt>rcu_for_each_leaf_node()</tt> traverses the single node. +</font></td></tr> +<tr><td> </td></tr> +</table> + +<h3><a name="Summary"> +Summary</a></h3> + +So each flavor of RCU is represented by an <tt>rcu_state</tt> structure, +which contains a combining tree of <tt>rcu_node</tt> and +<tt>rcu_data</tt> structures. +Finally, in <tt>CONFIG_NO_HZ_IDLE</tt> kernels, each CPU's dyntick-idle +state is tracked by an <tt>rcu_dynticks</tt> structure. + +If you made it this far, you are well prepared to read the code +walkthroughs in the other articles in this series. + +<h3><a name="Acknowledgments"> +Acknowledgments</a></h3> + +I owe thanks to Cyrill Gorcunov, Mathieu Desnoyers, Dhaval Giani, Paul +Turner, Abhishek Srivastava, Matt Kowalczyk, and Serge Hallyn +for helping me get this document into a more human-readable state. + +<h3><a name="Legal Statement"> +Legal Statement</a></h3> + +<p>This work represents the view of the author and does not necessarily +represent the view of IBM. + +</p><p>Linux is a registered trademark of Linus Torvalds. + +</p><p>Other company, product, and service names may be trademarks or +service marks of others. + +</body></html> diff --git a/Documentation/RCU/Design/Data-Structures/HugeTreeClassicRCU.svg b/Documentation/RCU/Design/Data-Structures/HugeTreeClassicRCU.svg new file mode 100644 index 000000000..2bf12b468 --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/HugeTreeClassicRCU.svg @@ -0,0 +1,939 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:37:22 2015 --> + +<!-- Magnification: 3.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="15.1in" + height="11.2in" + viewBox="-66 -66 18087 13407" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="HugeTreeClassicRCU.fig"> + <metadata + id="metadata224"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs222"> + <marker + inkscape:stockid="Arrow1Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow1Mend" + style="overflow:visible;"> + <path + id="path3982" + d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " + style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;" + transform="scale(0.4) rotate(180) translate(10,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="1134" + inkscape:window-height="789" + id="namedview220" + showgrid="false" + inkscape:zoom="0.60515873" + inkscape:cx="679.5" + inkscape:cy="504" + inkscape:window-x="786" + inkscape:window-y="24" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="450" + y="0" + width="17100" + height="8325" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect6" /> + <!-- Line: box --> + <rect + x="11025" + y="3600" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect8" /> + <!-- Line: box --> + <rect + x="4275" + y="3600" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect10" /> + <!-- Line: box --> + <rect + x="5400" + y="6300" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect12" /> + <!-- Line: box --> + <rect + x="9900" + y="6300" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect14" /> + <!-- Line: box --> + <rect + x="14400" + y="6300" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect16" /> + <!-- Line: box --> + <rect + x="900" + y="6300" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect18" /> + <!-- Line: box --> + <rect + x="7650" + y="900" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect20" /> + <!-- Line --> + <polyline + points="3150,9225 3150,7746 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline22" /> + <!-- Arrowhead on XXXpoint 3150 9225 - 3150 7560--> + <!-- Circle --> + <circle + cx="8550" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle26" /> + <!-- Circle --> + <circle + cx="9000" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle28" /> + <!-- Circle --> + <circle + cx="9450" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle30" /> + <!-- Line --> + <polyline + points="6750,6300 8250,5010 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline32" /> + <!-- Arrowhead on XXXpoint 6750 6300 - 8391 4890--> + <!-- Line --> + <polyline + points="11250,6300 9747,5010 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline36" /> + <!-- Arrowhead on XXXpoint 11250 6300 - 9606 4890--> + <!-- Circle --> + <circle + cx="13950" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle40" /> + <!-- Circle --> + <circle + cx="13500" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle42" /> + <!-- Circle --> + <circle + cx="13050" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle44" /> + <!-- Circle --> + <circle + cx="9450" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle46" /> + <!-- Circle --> + <circle + cx="9000" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle48" /> + <!-- Circle --> + <circle + cx="8550" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle50" /> + <!-- Circle --> + <circle + cx="4950" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle52" /> + <!-- Circle --> + <circle + cx="4500" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle54" /> + <!-- Circle --> + <circle + cx="4050" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle56" /> + <!-- Circle --> + <circle + cx="1800" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle58" /> + <!-- Circle --> + <circle + cx="2250" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle60" /> + <!-- Circle --> + <circle + cx="2700" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle62" /> + <!-- Circle --> + <circle + cx="15300" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle64" /> + <!-- Circle --> + <circle + cx="15750" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle66" /> + <!-- Circle --> + <circle + cx="16200" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle68" /> + <!-- Circle --> + <circle + cx="10800" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle70" /> + <!-- Circle --> + <circle + cx="11250" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle72" /> + <!-- Circle --> + <circle + cx="11700" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle74" /> + <!-- Circle --> + <circle + cx="6300" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle76" /> + <!-- Circle --> + <circle + cx="6750" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle78" /> + <!-- Circle --> + <circle + cx="7200" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle80" /> + <!-- Line: box --> + <rect + x="0" + y="11475" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect82" /> + <!-- Line: box --> + <rect + x="1800" + y="9225" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect84" /> + <!-- Line: box --> + <rect + x="4500" + y="11475" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect86" /> + <!-- Line: box --> + <rect + x="6300" + y="9270" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect88" /> + <!-- Line: box --> + <rect + x="8955" + y="11475" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect90" /> + <!-- Line: box --> + <rect + x="10755" + y="9270" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect92" /> + <!-- Line: box --> + <rect + x="13455" + y="11475" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect94" /> + <!-- Line: box --> + <rect + x="15255" + y="9270" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect96" /> + <!-- Line --> + <polyline + points="11700,3600 10197,2310 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline98" /> + <!-- Arrowhead on XXXpoint 11700 3600 - 10056 2190--> + <!-- Line --> + <polyline + points="6300,3600 7800,2310 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline102" /> + <!-- Arrowhead on XXXpoint 6300 3600 - 7941 2190--> + <!-- Line --> + <polyline + points="3150,6300 4650,5010 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline106" /> + <!-- Arrowhead on XXXpoint 3150 6300 - 4791 4890--> + <!-- Line --> + <polyline + points="14850,6300 13347,5010 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline110" /> + <!-- Arrowhead on XXXpoint 14850 6300 - 13206 4890--> + <!-- Line --> + <polyline + points="1350,11475 1350,7746 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline114" /> + <!-- Arrowhead on XXXpoint 1350 11475 - 1350 7560--> + <!-- Line --> + <polyline + points="16650,9225 16650,7746 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline118" /> + <!-- Arrowhead on XXXpoint 16650 9225 - 16650 7560--> + <!-- Line --> + <polyline + points="14850,11475 14850,7746 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline122" /> + <!-- Arrowhead on XXXpoint 14850 11475 - 14850 7560--> + <!-- Line --> + <polyline + points="12150,9225 12150,7746 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline126" /> + <!-- Arrowhead on XXXpoint 12150 9225 - 12150 7560--> + <!-- Line --> + <polyline + points="10350,11475 10350,7746 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline130" /> + <!-- Arrowhead on XXXpoint 10350 11475 - 10350 7560--> + <!-- Line --> + <polyline + points="7650,9225 7650,7746 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline134" /> + <!-- Arrowhead on XXXpoint 7650 9225 - 7650 7560--> + <!-- Line --> + <polyline + points="5850,11475 5850,7746 " + style="stroke:#00d1d1;stroke-width:44.99790066;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline138" /> + <!-- Arrowhead on XXXpoint 5850 11475 - 5850 7560--> + <!-- Text --> + <text + xml:space="preserve" + x="12375" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text142">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="12375" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text144">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5625" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text146">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5625" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text148">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="6750" + y="6750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text150">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="6750" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text152">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="11250" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text154">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="11250" + y="6750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text156">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="15750" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text158">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="15750" + y="6750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text160">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="6750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text162">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text164">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="1350" + y="13050" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text166">CPU 0</text> + <!-- Text --> + <text + xml:space="preserve" + x="1350" + y="11925" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text168">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1350" + y="12375" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text170">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="10800" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text172">CPU 15</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="9675" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text174">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="10125" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text176">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="5850" + y="11925" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text178">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5850" + y="12375" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text180">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="5850" + y="13050" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text182">CPU 21823</text> + <!-- Text --> + <text + xml:space="preserve" + x="7650" + y="10845" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text184">CPU 21839</text> + <!-- Text --> + <text + xml:space="preserve" + x="7650" + y="10170" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text186">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="7650" + y="9720" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text188">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="10305" + y="11925" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text190">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="10305" + y="12375" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text192">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="10305" + y="13050" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text194">CPU 43679</text> + <!-- Text --> + <text + xml:space="preserve" + x="12105" + y="10845" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text196">CPU 43695</text> + <!-- Text --> + <text + xml:space="preserve" + x="12105" + y="10170" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text198">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="12105" + y="9720" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text200">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="14805" + y="11925" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text202">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="14805" + y="12375" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text204">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="14805" + y="13050" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text206">CPU 65519</text> + <!-- Text --> + <text + xml:space="preserve" + x="16605" + y="10845" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text208">CPU 65535</text> + <!-- Text --> + <text + xml:space="preserve" + x="16605" + y="10170" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text210">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="16605" + y="9720" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text212">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="675" + y="450" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="start" + id="text214">struct rcu_state</text> + <!-- Text --> + <text + xml:space="preserve" + x="9000" + y="1350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text216">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="9000" + y="1800" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text218">rcu_node</text> + </g> +</svg> diff --git a/Documentation/RCU/Design/Data-Structures/TreeLevel.svg b/Documentation/RCU/Design/Data-Structures/TreeLevel.svg new file mode 100644 index 000000000..7a7eb3bac --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/TreeLevel.svg @@ -0,0 +1,828 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:41:29 2015 --> + +<!-- Magnification: 3.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="17.7in" + height="10.4in" + viewBox="-66 -66 21237 12507" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="TreeLevel.fig"> + <metadata + id="metadata216"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs214"> + <marker + inkscape:stockid="Arrow1Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow1Mend" + style="overflow:visible;"> + <path + id="path3974" + d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " + style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;" + transform="scale(0.4) rotate(180) translate(10,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="1023" + inkscape:window-height="1148" + id="namedview212" + showgrid="false" + inkscape:zoom="0.55869424" + inkscape:cx="796.50006" + inkscape:cy="467.99997" + inkscape:window-x="897" + inkscape:window-y="24" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="0" + y="0" + width="20655" + height="8325" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect6" /> + <!-- Line: box --> + <rect + x="14130" + y="3600" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect8" /> + <!-- Line: box --> + <rect + x="7380" + y="3600" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect10" /> + <!-- Line: box --> + <rect + x="8505" + y="6300" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect12" /> + <!-- Line: box --> + <rect + x="13005" + y="6300" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect14" /> + <!-- Line: box --> + <rect + x="17505" + y="6300" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect16" /> + <!-- Line: box --> + <rect + x="4005" + y="6300" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect18" /> + <!-- Line: box --> + <rect + x="10755" + y="900" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect20" /> + <!-- Line --> + <polyline + points="6255,9225 6255,7746 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline22" /> + <!-- Arrowhead on XXXpoint 6255 9225 - 6255 7560--> + <!-- Circle --> + <circle + cx="11655" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle26" /> + <!-- Circle --> + <circle + cx="12105" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle28" /> + <!-- Circle --> + <circle + cx="12555" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle30" /> + <!-- Line --> + <polyline + points="9855,6300 11355,5010 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline32" /> + <!-- Arrowhead on XXXpoint 9855 6300 - 11496 4890--> + <!-- Line --> + <polyline + points="14355,6300 12852,5010 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline36" /> + <!-- Arrowhead on XXXpoint 14355 6300 - 12711 4890--> + <!-- Circle --> + <circle + cx="17055" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle40" /> + <!-- Circle --> + <circle + cx="16605" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle42" /> + <!-- Circle --> + <circle + cx="16155" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle44" /> + <!-- Circle --> + <circle + cx="12555" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle46" /> + <!-- Circle --> + <circle + cx="12105" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle48" /> + <!-- Circle --> + <circle + cx="11655" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle50" /> + <!-- Circle --> + <circle + cx="8055" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle52" /> + <!-- Circle --> + <circle + cx="7605" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle54" /> + <!-- Circle --> + <circle + cx="7155" + cy="6975" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle56" /> + <!-- Circle --> + <circle + cx="4905" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle58" /> + <!-- Circle --> + <circle + cx="5355" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle60" /> + <!-- Circle --> + <circle + cx="5805" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle62" /> + <!-- Circle --> + <circle + cx="18405" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle64" /> + <!-- Circle --> + <circle + cx="18855" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle66" /> + <!-- Circle --> + <circle + cx="19305" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle68" /> + <!-- Circle --> + <circle + cx="13905" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle70" /> + <!-- Circle --> + <circle + cx="14355" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle72" /> + <!-- Circle --> + <circle + cx="14805" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle74" /> + <!-- Circle --> + <circle + cx="9405" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle76" /> + <!-- Circle --> + <circle + cx="9855" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle78" /> + <!-- Circle --> + <circle + cx="10305" + cy="8775" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle80" /> + <!-- Line: box --> + <rect + x="225" + y="1125" + width="3150" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:21; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect82" /> + <!-- Line: box --> + <rect + x="225" + y="2250" + width="3150" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:21; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect84" /> + <!-- Line: box --> + <rect + x="225" + y="3375" + width="3150" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:21; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect86" /> + <!-- Line --> + <polyline + points="14805,3600 13302,2310 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline88" /> + <!-- Arrowhead on XXXpoint 14805 3600 - 13161 2190--> + <!-- Line --> + <polyline + points="9405,3600 10905,2310 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline92" /> + <!-- Arrowhead on XXXpoint 9405 3600 - 11046 2190--> + <!-- Line --> + <polyline + points="6255,6300 7755,5010 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline96" /> + <!-- Arrowhead on XXXpoint 6255 6300 - 7896 4890--> + <!-- Line --> + <polyline + points="17955,6300 16452,5010 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline100" /> + <!-- Arrowhead on XXXpoint 17955 6300 - 16311 4890--> + <!-- Line --> + <polyline + points="4455,11025 4455,7746 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline104" /> + <!-- Arrowhead on XXXpoint 4455 11025 - 4455 7560--> + <!-- Line --> + <polyline + points="19755,9225 19755,7746 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline108" /> + <!-- Arrowhead on XXXpoint 19755 9225 - 19755 7560--> + <!-- Line --> + <polyline + points="17955,11025 17955,7746 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline112" /> + <!-- Arrowhead on XXXpoint 17955 11025 - 17955 7560--> + <!-- Line --> + <polyline + points="15255,9225 15255,7746 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline116" /> + <!-- Arrowhead on XXXpoint 15255 9225 - 15255 7560--> + <!-- Line --> + <polyline + points="13455,11025 13455,7746 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline120" /> + <!-- Arrowhead on XXXpoint 13455 11025 - 13455 7560--> + <!-- Line --> + <polyline + points="10755,9225 10755,7746 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline124" /> + <!-- Arrowhead on XXXpoint 10755 9225 - 10755 7560--> + <!-- Line --> + <polyline + points="8955,11025 8955,7746 " + style="stroke:#00d1d1;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline128" /> + <!-- Arrowhead on XXXpoint 8955 11025 - 8955 7560--> + <!-- Line: box --> + <rect + x="12105" + y="11025" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect132" /> + <!-- Line: box --> + <rect + x="13905" + y="9225" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect134" /> + <!-- Line: box --> + <rect + x="16605" + y="11025" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect136" /> + <!-- Line: box --> + <rect + x="18405" + y="9225" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect138" /> + <!-- Line: box --> + <rect + x="9405" + y="9225" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect140" /> + <!-- Line: box --> + <rect + x="7605" + y="11025" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect142" /> + <!-- Line: box --> + <rect + x="4905" + y="9225" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect144" /> + <!-- Line: box --> + <rect + x="3105" + y="11025" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect146" /> + <!-- Line --> + <polyline + points="3375,1575 10701,1575 " + style="stroke:#000000;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline148" /> + <!-- Arrowhead on XXXpoint 3375 1575 - 10890 1575--> + <!-- Line --> + <polyline + points="3375,3825 4050,3825 4050,5400 2700,5400 2700,6975 3951,6975 " + style="stroke:#000000;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline152" /> + <!-- Arrowhead on XXXpoint 2700 6975 - 4140 6975--> + <!-- Line --> + <polyline + points="3375,2700 5175,2700 5175,4275 7326,4275 " + style="stroke:#000000;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline156" /> + <!-- Arrowhead on XXXpoint 5175 4275 - 7515 4275--> + <!-- Text --> + <text + xml:space="preserve" + x="15480" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text160">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="15480" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text162">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="8730" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text164">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="8730" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text166">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="9855" + y="6750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text168">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="9855" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text170">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="14355" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text172">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="14355" + y="6750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text174">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="18855" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text176">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="18855" + y="6750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text178">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5355" + y="6750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text180">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5355" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text182">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="450" + y="1800" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="324" + text-anchor="start" + id="text184">->level[0]</text> + <!-- Text --> + <text + xml:space="preserve" + x="450" + y="2925" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="324" + text-anchor="start" + id="text186">->level[1]</text> + <!-- Text --> + <text + xml:space="preserve" + x="450" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="324" + text-anchor="start" + id="text188">->level[2]</text> + <!-- Text --> + <text + xml:space="preserve" + x="12105" + y="1350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text190">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="12105" + y="1800" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text192">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="6255" + y="10125" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text194">CPU 15</text> + <!-- Text --> + <text + xml:space="preserve" + x="4455" + y="11925" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text196">CPU 0</text> + <!-- Text --> + <text + xml:space="preserve" + x="19755" + y="10125" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text198">CPU 65535</text> + <!-- Text --> + <text + xml:space="preserve" + x="17955" + y="11925" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text200">CPU 65519</text> + <!-- Text --> + <text + xml:space="preserve" + x="15255" + y="10125" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text202">CPU 43695</text> + <!-- Text --> + <text + xml:space="preserve" + x="13455" + y="11925" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text204">CPU 43679</text> + <!-- Text --> + <text + xml:space="preserve" + x="10755" + y="10125" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text206">CPU 21839</text> + <!-- Text --> + <text + xml:space="preserve" + x="8955" + y="11925" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text208">CPU 21823</text> + <!-- Text --> + <text + xml:space="preserve" + x="225" + y="450" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="start" + id="text210">struct rcu_state</text> + </g> +</svg> diff --git a/Documentation/RCU/Design/Data-Structures/TreeMapping.svg b/Documentation/RCU/Design/Data-Structures/TreeMapping.svg new file mode 100644 index 000000000..729cfa9e6 --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/TreeMapping.svg @@ -0,0 +1,305 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:43:22 2015 --> + +<!-- Magnification: 1.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="3.1in" + height="0.9in" + viewBox="-12 -12 3699 1074" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="TreeMapping.fig"> + <metadata + id="metadata66"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs64"> + <marker + inkscape:stockid="Arrow2Lend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow2Lend" + style="overflow:visible;"> + <path + id="path3836" + style="fill-rule:evenodd;stroke-width:0.62500000;stroke-linejoin:round;" + d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.9730900,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z " + transform="scale(1.1) rotate(180) translate(1,0)" /> + </marker> + <marker + inkscape:stockid="Arrow2Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow2Mend" + style="overflow:visible;"> + <path + id="path3842" + style="fill-rule:evenodd;stroke-width:0.62500000;stroke-linejoin:round;" + d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.9730900,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z " + transform="scale(0.6) rotate(180) translate(0,0)" /> + </marker> + <marker + inkscape:stockid="Arrow1Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow1Mend" + style="overflow:visible;"> + <path + id="path3824" + d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " + style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;" + transform="scale(0.4) rotate(180) translate(10,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="991" + inkscape:window-height="606" + id="namedview62" + showgrid="false" + inkscape:zoom="3.0752688" + inkscape:cx="139.5" + inkscape:cy="40.5" + inkscape:window-x="891" + inkscape:window-y="177" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="0" + y="0" + width="3675" + height="1050" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect6" /> + <!-- Line: box --> + <rect + x="75" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect8" /> + <!-- Line: box --> + <rect + x="600" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect10" /> + <!-- Line: box --> + <rect + x="1125" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect12" /> + <!-- Line: box --> + <rect + x="1650" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect14" /> + <!-- Line: box --> + <rect + x="2175" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect16" /> + <!-- Line: box --> + <rect + x="3225" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect18" /> + <!-- Line --> + <polyline + points="675,375 675,150 300,150 300,358 " + style="stroke:#000000;stroke-width:7.00088889;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline20" /> + <!-- Arrowhead on XXXpoint 300 150 - 300 390--> + <!-- Line --> + <polyline + points="1200,675 1200,900 300,900 300,691 " + style="stroke:#000000;stroke-width:7.00088889;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline24" /> + <!-- Arrowhead on XXXpoint 300 900 - 300 660--> + <!-- Line --> + <polyline + points="1725,375 1725,150 900,150 900,358 " + style="stroke:#000000;stroke-width:7.00088889;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline28" /> + <!-- Arrowhead on XXXpoint 900 150 - 900 390--> + <!-- Line --> + <polyline + points="2250,375 2250,75 825,75 825,358 " + style="stroke:#000000;stroke-width:7.00088889;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline32" /> + <!-- Arrowhead on XXXpoint 825 75 - 825 390--> + <!-- Line --> + <polyline + points="2775,675 2775,900 1425,900 1425,691 " + style="stroke:#000000;stroke-width:7.00088889;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline36" /> + <!-- Arrowhead on XXXpoint 1425 900 - 1425 660--> + <!-- Line --> + <polyline + points="3300,675 3300,975 1350,975 1350,691 " + style="stroke:#000000;stroke-width:7.00088889;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline40" /> + <!-- Arrowhead on XXXpoint 1350 975 - 1350 660--> + <!-- Line: box --> + <rect + x="2700" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect44" /> + <!-- Text --> + <text + xml:space="preserve" + x="300" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text46">0:7 </text> + <!-- Text --> + <text + xml:space="preserve" + x="1350" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text48">4:7 </text> + <!-- Text --> + <text + xml:space="preserve" + x="1875" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text50">0:1 </text> + <!-- Text --> + <text + xml:space="preserve" + x="2400" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text52">2:3 </text> + <!-- Text --> + <text + xml:space="preserve" + x="2925" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text54">4:5 </text> + <!-- Text --> + <text + xml:space="preserve" + x="3450" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text56">6:7 </text> + <!-- Text --> + <text + xml:space="preserve" + x="825" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text58">0:3 </text> + <!-- Text --> + <text + xml:space="preserve" + x="3600" + y="150" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="end" + id="text60">struct rcu_state</text> + </g> +</svg> diff --git a/Documentation/RCU/Design/Data-Structures/TreeMappingLevel.svg b/Documentation/RCU/Design/Data-Structures/TreeMappingLevel.svg new file mode 100644 index 000000000..5b416a4b8 --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/TreeMappingLevel.svg @@ -0,0 +1,380 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:45:19 2015 --> + +<!-- Magnification: 1.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="3.1in" + height="1.8in" + viewBox="-12 -12 3699 2124" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="TreeMappingLevel.svg"> + <metadata + id="metadata98"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title /> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs96"> + <marker + inkscape:stockid="Arrow2Lend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow2Lend" + style="overflow:visible;"> + <path + id="path3868" + style="fill-rule:evenodd;stroke-width:0.62500000;stroke-linejoin:round;" + d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.9730900,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z " + transform="scale(1.1) rotate(180) translate(1,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="1598" + inkscape:window-height="1211" + id="namedview94" + showgrid="false" + inkscape:zoom="5.2508961" + inkscape:cx="139.5" + inkscape:cy="81" + inkscape:window-x="840" + inkscape:window-y="122" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="0" + y="0" + width="3675" + height="2100" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect6" /> + <!-- Line: box --> + <rect + x="75" + y="1350" + width="750" + height="225" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect8" /> + <!-- Line: box --> + <rect + x="75" + y="1575" + width="750" + height="225" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect10" /> + <!-- Line: box --> + <rect + x="75" + y="1800" + width="750" + height="225" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect12" /> + <!-- Arc --> + <path + style="stroke:#000000;stroke-width:7;stroke-linecap:butt;" + d="M 1800,900 A 118 118 0 0 0 1800 1125 " + id="path14" /> + <!-- Arc --> + <path + style="stroke:#000000;stroke-width:7;stroke-linecap:butt;" + d="M 750,900 A 75 75 0 0 0 750 1050 " + id="path16" /> + <!-- Line --> + <polyline + points="750,900 750,691 " + style="stroke:#000000;stroke-width:7.00025806;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline18" /> + <!-- Arrowhead on XXXpoint 750 900 - 750 660--> + <!-- Line: box --> + <rect + x="75" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect22" /> + <!-- Line: box --> + <rect + x="600" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect24" /> + <!-- Line: box --> + <rect + x="1650" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect26" /> + <!-- Line: box --> + <rect + x="2175" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect28" /> + <!-- Line: box --> + <rect + x="3225" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect30" /> + <!-- Line --> + <polyline + points="675,375 675,150 300,150 300,358 " + style="stroke:#000000;stroke-width:7.00025806;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline32" /> + <!-- Arrowhead on XXXpoint 300 150 - 300 390--> + <!-- Line --> + <polyline + points="1725,375 1725,150 900,150 900,358 " + style="stroke:#000000;stroke-width:7.00025806;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline36" /> + <!-- Arrowhead on XXXpoint 900 150 - 900 390--> + <!-- Line --> + <polyline + points="2250,375 2250,75 825,75 825,358 " + style="stroke:#000000;stroke-width:7.00025806;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline40" /> + <!-- Arrowhead on XXXpoint 825 75 - 825 390--> + <!-- Line --> + <polyline + points="2775,675 2775,975 1425,975 1425,691 " + style="stroke:#000000;stroke-width:7.00025806;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline44" /> + <!-- Arrowhead on XXXpoint 1425 975 - 1425 660--> + <!-- Line: box --> + <rect + x="2700" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect48" /> + <!-- Line: box --> + <rect + x="1125" + y="375" + width="375" + height="300" + rx="0" + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect50" /> + <!-- Line --> + <polyline + points="3300,675 3300,1050 1350,1050 1350,691 " + style="stroke:#000000;stroke-width:7.00025806;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline52" /> + <!-- Arrowhead on XXXpoint 1350 1050 - 1350 660--> + <!-- Line --> + <polyline + points="825,1425 975,1425 975,1200 225,1200 225,691 " + style="stroke:#000000;stroke-width:7.00025806;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline56" /> + <!-- Arrowhead on XXXpoint 225 1200 - 225 660--> + <!-- Line --> + <polyline + points="1200,675 1200,975 300,975 300,691 " + style="stroke:#000000;stroke-width:7.00025806;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline60" /> + <!-- Arrowhead on XXXpoint 300 975 - 300 660--> + <!-- Text --> + <text + xml:space="preserve" + x="150" + y="1500" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="108" + text-anchor="start" + id="text64">->level[0]</text> + <!-- Text --> + <text + xml:space="preserve" + x="150" + y="1725" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="108" + text-anchor="start" + id="text66">->level[1]</text> + <!-- Text --> + <text + xml:space="preserve" + x="150" + y="1950" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="108" + text-anchor="start" + id="text68">->level[2]</text> + <!-- Text --> + <text + xml:space="preserve" + x="300" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text70">0:7 </text> + <!-- Text --> + <text + xml:space="preserve" + x="1350" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text72">4:7 </text> + <!-- Text --> + <text + xml:space="preserve" + x="1875" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text74">0:1 </text> + <!-- Text --> + <text + xml:space="preserve" + x="2400" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text76">2:3 </text> + <!-- Text --> + <text + xml:space="preserve" + x="2925" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text78">4:5 </text> + <!-- Text --> + <text + xml:space="preserve" + x="3450" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text80">6:7 </text> + <!-- Text --> + <text + xml:space="preserve" + x="825" + y="525" + fill="#000000" + font-family="Times" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="middle" + id="text82">0:3 </text> + <!-- Text --> + <text + xml:space="preserve" + x="3600" + y="150" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="normal" + font-size="96" + text-anchor="end" + id="text84">struct rcu_state</text> + <!-- Line --> + <polyline + points="825,1875 1800,1875 1800,1125 " + style="stroke:#000000;stroke-width:7.00025806;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:none" + id="polyline86" /> + <!-- Line --> + <polyline + points="1800,900 1800,691 " + style="stroke:#000000;stroke-width:7.00025806;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow2Lend)" + id="polyline88" /> + <!-- Arrowhead on XXXpoint 1800 900 - 1800 660--> + <!-- Line --> + <polyline + points="825,1650 1200,1650 1200,1125 750,1125 750,1050 " + style="stroke:#000000;stroke-width:7; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline92" /> + </g> +</svg> diff --git a/Documentation/RCU/Design/Data-Structures/blkd_task.svg b/Documentation/RCU/Design/Data-Structures/blkd_task.svg new file mode 100644 index 000000000..00e810bb8 --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/blkd_task.svg @@ -0,0 +1,843 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:35:03 2015 --> + +<!-- Magnification: 2.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="10.1in" + height="8.6in" + viewBox="-44 -44 12088 10288" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="blkd_task.fig"> + <metadata + id="metadata212"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs210"> + <marker + inkscape:stockid="Arrow1Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow1Mend" + style="overflow:visible;"> + <path + id="path3970" + d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " + style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;" + transform="scale(0.4) rotate(180) translate(10,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="1087" + inkscape:window-height="1144" + id="namedview208" + showgrid="false" + inkscape:zoom="1.0495049" + inkscape:cx="454.50003" + inkscape:cy="387.00003" + inkscape:window-x="833" + inkscape:window-y="28" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="450" + y="0" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect6" /> + <!-- Line: box --> + <rect + x="4950" + y="4950" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect8" /> + <!-- Line: box --> + <rect + x="750" + y="600" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect10" /> + <!-- Line --> + <polyline + points="5250,8100 5688,5912 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline12" /> + <!-- Arrowhead on XXXpoint 5250 8100 - 5710 5790--> + <polyline + points="5714 6068 5704 5822 5598 6044 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline14" /> + <!-- Line --> + <polyline + points="4050,9300 4486,7262 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline16" /> + <!-- Arrowhead on XXXpoint 4050 9300 - 4512 7140--> + <polyline + points="4514 7418 4506 7172 4396 7394 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline18" /> + <!-- Line --> + <polyline + points="1040,9300 1476,7262 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline20" /> + <!-- Arrowhead on XXXpoint 1040 9300 - 1502 7140--> + <polyline + points="1504 7418 1496 7172 1386 7394 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline22" /> + <!-- Line --> + <polyline + points="2240,8100 2676,6062 " + style="stroke:#00ff00;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="polyline24" /> + <!-- Arrowhead on XXXpoint 2240 8100 - 2702 5940--> + <polyline + points="2704 6218 2696 5972 2586 6194 " + style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8; " + id="polyline26" /> + <!-- Line: box --> + <rect + x="0" + y="450" + width="6300" + height="7350" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; " + id="rect28" /> + <!-- Line: box --> + <rect + x="300" + y="1050" + width="5700" + height="3750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect30" /> + <!-- Line --> + <polyline + points="1350,3450 2350,2590 " + style="stroke:#00d1d1;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline32" /> + <!-- Arrowhead on XXXpoint 1350 3450 - 2444 2510--> + <!-- Line --> + <polyline + points="4950,3450 3948,2590 " + style="stroke:#00d1d1;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline36" /> + <!-- Arrowhead on XXXpoint 4950 3450 - 3854 2510--> + <!-- Line --> + <polyline + points="4050,6600 4050,4414 " + style="stroke:#00d1d1;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline40" /> + <!-- Arrowhead on XXXpoint 4050 6600 - 4050 4290--> + <!-- Line --> + <polyline + points="1050,6600 1050,4414 " + style="stroke:#00d1d1;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline44" /> + <!-- Arrowhead on XXXpoint 1050 6600 - 1050 4290--> + <!-- Line --> + <polyline + points="2250,5400 2250,4414 " + style="stroke:#00d1d1;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline48" /> + <!-- Arrowhead on XXXpoint 2250 5400 - 2250 4290--> + <!-- Line --> + <polyline + points="2250,8100 2250,6364 " + style="stroke:#00ff00;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline52" /> + <!-- Arrowhead on XXXpoint 2250 8100 - 2250 6240--> + <!-- Line --> + <polyline + points="1050,9300 1050,7564 " + style="stroke:#00ff00;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline56" /> + <!-- Arrowhead on XXXpoint 1050 9300 - 1050 7440--> + <!-- Line --> + <polyline + points="4050,9300 4050,7564 " + style="stroke:#00ff00;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline60" /> + <!-- Arrowhead on XXXpoint 4050 9300 - 4050 7440--> + <!-- Line --> + <polyline + points="5250,8100 5250,6364 " + style="stroke:#00ff00;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline64" /> + <!-- Arrowhead on XXXpoint 5250 8100 - 5250 6240--> + <!-- Circle --> + <circle + cx="2850" + cy="3900" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle68" /> + <!-- Circle --> + <circle + cx="3150" + cy="3900" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle70" /> + <!-- Circle --> + <circle + cx="3450" + cy="3900" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle72" /> + <!-- Circle --> + <circle + cx="1350" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle74" /> + <!-- Circle --> + <circle + cx="1650" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle76" /> + <!-- Circle --> + <circle + cx="1950" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle78" /> + <!-- Circle --> + <circle + cx="4350" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle80" /> + <!-- Circle --> + <circle + cx="4650" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle82" /> + <!-- Circle --> + <circle + cx="4950" + cy="5100" + r="76" + style="fill:#000000;stroke:#000000;stroke-width:14;" + id="circle84" /> + <!-- Line: box --> + <rect + x="750" + y="3450" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect86" /> + <!-- Line: box --> + <rect + x="300" + y="6600" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect88" /> + <!-- Line: box --> + <rect + x="4500" + y="5400" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect90" /> + <!-- Line: box --> + <rect + x="3300" + y="6600" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect92" /> + <!-- Line: box --> + <rect + x="2250" + y="1650" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect94" /> + <!-- Line: box --> + <rect + x="0" + y="9300" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect96" /> + <!-- Line: box --> + <rect + x="1350" + y="8100" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect98" /> + <!-- Line: box --> + <rect + x="3000" + y="9300" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect100" /> + <!-- Line: box --> + <rect + x="4350" + y="8100" + width="2100" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#00ff00; " + id="rect102" /> + <!-- Line: box --> + <rect + x="1500" + y="5400" + width="1500" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect104" /> + <!-- Line --> + <polygon + points="5550,3450 7350,2850 7350,5100 5550,4350 5550,3450 " + style="stroke:#000000;stroke-width:14; stroke-linejoin:miter; stroke-linecap:butt; stroke-dasharray:120 120;fill:#ffbfbf; " + id="polygon106" /> + <!-- Line --> + <polyline + points="9300,3150 10734,3150 " + style="stroke:#000000;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline108" /> + <!-- Arrowhead on XXXpoint 9300 3150 - 10860 3150--> + <!-- Line: box --> + <rect + x="10800" + y="2850" + width="1200" + height="750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect112" /> + <!-- Line --> + <polyline + points="11400,3600 11400,4284 " + style="stroke:#000000;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline114" /> + <!-- Arrowhead on XXXpoint 11400 3600 - 11400 4410--> + <!-- Line: box --> + <rect + x="10800" + y="4350" + width="1200" + height="750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect118" /> + <!-- Line --> + <polyline + points="11400,5100 11400,5784 " + style="stroke:#000000;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline120" /> + <!-- Arrowhead on XXXpoint 11400 5100 - 11400 5910--> + <!-- Line: box --> + <rect + x="10800" + y="5850" + width="1200" + height="750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect124" /> + <!-- Line --> + <polyline + points="9300,3900 9900,3900 9900,4650 10734,4650 " + style="stroke:#000000;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline126" /> + <!-- Arrowhead on XXXpoint 9900 4650 - 10860 4650--> + <!-- Line --> + <polyline + points="9300,4650 9600,4650 9600,6150 10734,6150 " + style="stroke:#000000;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline130" /> + <!-- Arrowhead on XXXpoint 9600 6150 - 10860 6150--> + <!-- Text --> + <text + xml:space="preserve" + x="6450" + y="300" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text134">rcu_bh</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="1950" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text136">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="3150" + y="2250" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text138">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="1650" + y="3750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text140">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1650" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text142">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="5700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text144">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2250" + y="6000" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text146">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="6900" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text148">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text150">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="5250" + y="5700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text152">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5250" + y="6000" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text154">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="6900" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text156">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="7200" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text158">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="450" + y="1350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="start" + id="text160">struct rcu_state</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="9600" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text162">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1050" + y="9900" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text164">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="9600" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text166">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="4050" + y="9900" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text168">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="2400" + y="8400" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text170">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2400" + y="8700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text172">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="5400" + y="8400" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text174">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5400" + y="8700" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text176">rcu_dynticks</text> + <!-- Text --> + <text + xml:space="preserve" + x="6000" + y="750" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="192" + text-anchor="end" + id="text178">rcu_sched</text> + <!-- Text --> + <text + xml:space="preserve" + x="11400" + y="3300" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="216" + text-anchor="middle" + id="text180">T3</text> + <!-- Text --> + <text + xml:space="preserve" + x="11400" + y="4800" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="216" + text-anchor="middle" + id="text182">T2</text> + <!-- Text --> + <text + xml:space="preserve" + x="11400" + y="6300" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="216" + text-anchor="middle" + id="text184">T1</text> + <!-- Line --> + <polyline + points="5250,5400 5250,4414 " + style="stroke:#00d1d1;stroke-width:30.00057884;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline186" /> + <!-- Arrowhead on XXXpoint 5250 5400 - 5250 4290--> + <!-- Line: box --> + <rect + x="3750" + y="3450" + width="1800" + height="900" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect190" /> + <!-- Line: box --> + <rect + x="7350" + y="2850" + width="1950" + height="750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect192" /> + <!-- Line: box --> + <rect + x="7350" + y="3600" + width="1950" + height="750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect194" /> + <!-- Line: box --> + <rect + x="7350" + y="4350" + width="1950" + height="750" + rx="0" + style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect196" /> + <!-- Text --> + <text + xml:space="preserve" + x="4650" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text198">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="4650" + y="3750" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="middle" + id="text200">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="7500" + y="3300" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="start" + id="text202">blkd_tasks</text> + <!-- Text --> + <text + xml:space="preserve" + x="7500" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="start" + id="text204">gp_tasks</text> + <!-- Text --> + <text + xml:space="preserve" + x="7500" + y="4800" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="192" + text-anchor="start" + id="text206">exp_tasks</text> + </g> +</svg> diff --git a/Documentation/RCU/Design/Data-Structures/nxtlist.svg b/Documentation/RCU/Design/Data-Structures/nxtlist.svg new file mode 100644 index 000000000..0223e79c3 --- /dev/null +++ b/Documentation/RCU/Design/Data-Structures/nxtlist.svg @@ -0,0 +1,386 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:39:46 2015 --> + +<!-- Magnification: 3.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="10.4in" + height="10.4in" + viewBox="-66 -66 12507 12507" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="segcblist.svg"> + <metadata + id="metadata94"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title /> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs92"> + <marker + inkscape:stockid="Arrow1Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow1Mend" + style="overflow:visible;"> + <path + id="path3852" + d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " + style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;" + transform="scale(0.4) rotate(180) translate(10,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="925" + inkscape:window-height="928" + id="namedview90" + showgrid="false" + inkscape:zoom="0.80021373" + inkscape:cx="467.99997" + inkscape:cy="467.99997" + inkscape:window-x="948" + inkscape:window-y="73" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="0" + y="0" + width="7875" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect6" /> + <!-- Line: box --> + <rect + x="0" + y="1125" + width="7875" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect8" /> + <!-- Line: box --> + <rect + x="0" + y="2250" + width="7875" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect10" /> + <!-- Line: box --> + <rect + x="0" + y="3375" + width="7875" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect12" /> + <!-- Line: box --> + <rect + x="0" + y="4500" + width="7875" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; " + id="rect14" /> + <!-- Line: box --> + <rect + x="10575" + y="0" + width="1800" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect16" /> + <!-- Line: box --> + <rect + x="10575" + y="1125" + width="1800" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect18" /> + <!-- Line --> + <polyline + points="11475,2250 11475,3276 " + style="stroke:#000000;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline20" /> + <!-- Arrowhead on XXXpoint 11475 2250 - 11475 3465--> + <!-- Line: box --> + <rect + x="10575" + y="6750" + width="1800" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect24" /> + <!-- Line: box --> + <rect + x="10575" + y="7875" + width="1800" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect26" /> + <!-- Line: box --> + <rect + x="10575" + y="10125" + width="1800" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect28" /> + <!-- Line: box --> + <rect + x="10575" + y="11250" + width="1800" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect30" /> + <!-- Line: box --> + <rect + x="10575" + y="3375" + width="1800" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect32" /> + <!-- Line --> + <polyline + points="11475,5625 11475,6651 " + style="stroke:#000000;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline34" /> + <!-- Arrowhead on XXXpoint 11475 5625 - 11475 6840--> + <!-- Line --> + <polyline + points="7875,225 10476,225 " + style="stroke:#000000;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline38" /> + <!-- Arrowhead on XXXpoint 7875 225 - 10665 225--> + <!-- Line --> + <polyline + points="7875,1350 9675,1350 9675,675 7971,675 " + style="stroke:#000000;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline42" /> + <!-- Arrowhead on XXXpoint 9675 675 - 7785 675--> + <!-- Line --> + <polyline + points="7875,2475 9675,2475 9675,4725 10476,4725 " + style="stroke:#000000;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline46" /> + <!-- Arrowhead on XXXpoint 9675 4725 - 10665 4725--> + <!-- Line --> + <polyline + points="7875,3600 9225,3600 9225,5175 10476,5175 " + style="stroke:#000000;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline50" /> + <!-- Arrowhead on XXXpoint 9225 5175 - 10665 5175--> + <!-- Line --> + <polyline + points="7875,4725 8775,4725 8775,11475 10476,11475 " + style="stroke:#000000;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline54" /> + <!-- Arrowhead on XXXpoint 8775 11475 - 10665 11475--> + <!-- Line: box --> + <rect + x="10575" + y="4500" + width="1800" + height="1125" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect58" /> + <!-- Line --> + <polyline + points="11475,9000 11475,10026 " + style="stroke:#000000;stroke-width:45.00382345;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline60" /> + <!-- Arrowhead on XXXpoint 11475 9000 - 11475 10215--> + <!-- Text --> + <text + xml:space="preserve" + x="225" + y="675" + font-style="normal" + font-weight="bold" + font-size="324" + id="text64" + style="font-size:324px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;font-family:Courier">->head</text> + <!-- Text --> + <text + xml:space="preserve" + x="225" + y="1800" + font-style="normal" + font-weight="bold" + font-size="324" + id="text66" + style="font-size:324px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;font-family:Courier">->tails[RCU_DONE_TAIL]</text> + <!-- Text --> + <text + xml:space="preserve" + x="225" + y="2925" + font-style="normal" + font-weight="bold" + font-size="324" + id="text68" + style="font-size:324px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;font-family:Courier">->tails[RCU_WAIT_TAIL]</text> + <!-- Text --> + <text + xml:space="preserve" + x="225" + y="4050" + font-style="normal" + font-weight="bold" + font-size="324" + id="text70" + style="font-size:324px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;font-family:Courier">->tails[RCU_NEXT_READY_TAIL]</text> + <!-- Text --> + <text + xml:space="preserve" + x="225" + y="5175" + font-style="normal" + font-weight="bold" + font-size="324" + id="text72" + style="font-size:324px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;font-family:Courier">->tails[RCU_NEXT_TAIL]</text> + <!-- Text --> + <text + xml:space="preserve" + x="11475" + y="675" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text74">CB 1</text> + <!-- Text --> + <text + xml:space="preserve" + x="11475" + y="1800" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text76">next</text> + <!-- Text --> + <text + xml:space="preserve" + x="11475" + y="7425" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text78">CB 3</text> + <!-- Text --> + <text + xml:space="preserve" + x="11475" + y="8550" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text80">next</text> + <!-- Text --> + <text + xml:space="preserve" + x="11475" + y="10800" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text82">CB 4</text> + <!-- Text --> + <text + xml:space="preserve" + x="11475" + y="11925" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text84">next</text> + <!-- Text --> + <text + xml:space="preserve" + x="11475" + y="4050" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text86">CB 2</text> + <!-- Text --> + <text + xml:space="preserve" + x="11475" + y="5175" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text88">next</text> + </g> +</svg> |
