Update Linux to v5.4.2
Change-Id: Idf6911045d9d382da2cfe01b1edff026404ac8fd
diff --git a/Documentation/RCU/00-INDEX b/Documentation/RCU/00-INDEX
deleted file mode 100644
index f46980c..0000000
--- a/Documentation/RCU/00-INDEX
+++ /dev/null
@@ -1,34 +0,0 @@
-00-INDEX
- - This file
-arrayRCU.txt
- - Using RCU to Protect Read-Mostly Arrays
-checklist.txt
- - Review Checklist for RCU Patches
-listRCU.txt
- - Using RCU to Protect Read-Mostly Linked Lists
-lockdep.txt
- - RCU and lockdep checking
-lockdep-splat.txt
- - RCU Lockdep splats explained.
-NMI-RCU.txt
- - Using RCU to Protect Dynamic NMI Handlers
-rcu_dereference.txt
- - Proper care and feeding of return values from rcu_dereference()
-rcubarrier.txt
- - RCU and Unloadable Modules
-rculist_nulls.txt
- - RCU list primitives for use with SLAB_TYPESAFE_BY_RCU
-rcuref.txt
- - Reference-count design for elements of lists/arrays protected by RCU
-rcu.txt
- - RCU Concepts
-RTFP.txt
- - List of RCU papers (bibliography) going back to 1980.
-stallwarn.txt
- - RCU CPU stall warnings (module parameter rcu_cpu_stall_suppress)
-torture.txt
- - RCU Torture Test Operation (CONFIG_RCU_TORTURE_TEST)
-UP.txt
- - RCU on Uniprocessor Systems
-whatisRCU.txt
- - What is RCU?
diff --git a/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBH.svg b/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBH.svg
deleted file mode 100644
index 9bbb194..0000000
--- a/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBH.svg
+++ /dev/null
@@ -1,499 +0,0 @@
-<?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
deleted file mode 100644
index 21ba782..0000000
--- a/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBHdyntick.svg
+++ /dev/null
@@ -1,695 +0,0 @@
-<?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
deleted file mode 100644
index 15adcac..0000000
--- a/Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntick.svg
+++ /dev/null
@@ -1,741 +0,0 @@
-<?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
index bbc3801..3a1a4f8 100644
--- a/Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntickCB.svg
+++ b/Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntickCB.svg
@@ -13,12 +13,12 @@
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"
+ width="7.4000001in"
+ height="7.9000001in"
+ viewBox="-44 -44 8938 9526.283"
id="svg2"
version="1.1"
- inkscape:version="0.48.4 r9939"
+ inkscape:version="0.92.2pre0 (973e216, 2017-07-25)"
sodipodi:docname="BigTreePreemptRCUBHdyntickCB.svg">
<metadata
id="metadata212">
@@ -37,15 +37,46 @@
<marker
inkscape:stockid="Arrow1Mend"
orient="auto"
- refY="0.0"
- refX="0.0"
+ refY="0"
+ refX="0"
+ id="marker1177"
+ style="overflow:visible"
+ inkscape:isstock="true">
+ <path
+ id="path897"
+ d="M 0,0 5,-5 -12.5,0 5,5 Z"
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1.00000003pt;stroke-opacity:1"
+ transform="matrix(-0.4,0,0,-0.4,-4,0)"
+ inkscape:connector-curvature="0" />
+ </marker>
+ <marker
+ inkscape:stockid="Arrow1Lend"
+ orient="auto"
+ refY="0"
+ refX="0"
+ id="Arrow1Lend"
+ style="overflow:visible"
+ inkscape:isstock="true">
+ <path
+ id="path891"
+ d="M 0,0 5,-5 -12.5,0 5,5 Z"
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1.00000003pt;stroke-opacity:1"
+ transform="matrix(-0.8,0,0,-0.8,-10,0)"
+ inkscape:connector-curvature="0" />
+ </marker>
+ <marker
+ inkscape:stockid="Arrow1Mend"
+ orient="auto"
+ refY="0"
+ refX="0"
id="Arrow1Mend"
- style="overflow:visible;">
+ 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)" />
+ d="M 0,0 5,-5 -12.5,0 5,5 Z"
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1.00000003pt"
+ transform="matrix(-0.4,0,0,-0.4,-4,0)"
+ inkscape:connector-curvature="0" />
</marker>
</defs>
<sodipodi:namedview
@@ -57,802 +88,575 @@
guidetolerance="10"
inkscape:pageopacity="0"
inkscape:pageshadow="2"
- inkscape:window-width="881"
- inkscape:window-height="1128"
+ inkscape:window-width="1920"
+ inkscape:window-height="1019"
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:cx="166.25478"
+ inkscape:cy="362.18693"
+ inkscape:window-x="0"
+ inkscape:window-y="0"
+ inkscape:window-maximized="1"
inkscape:current-layer="g4" />
<g
- style="stroke-width:.025in; fill:none"
- id="g4">
+ style="fill:none;stroke-width:0.025in"
+ id="g4"
+ transform="translate(0,-2415.6743)">
<!-- 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" />
+ style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8"
+ id="polyline20"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- 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" />
+ style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8"
+ id="polyline24"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- 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" />
+ style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8"
+ id="polyline28"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- 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" />
+ style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8"
+ id="polyline32"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- 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" />
+ style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8"
+ id="polyline36"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- 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" />
+ style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8"
+ id="polyline40"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- Line: box -->
<rect
- x="0"
- y="900"
+ x="12.340758"
+ y="2442.5947"
width="6300"
- height="7350"
+ height="7045.3135"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; "
+ style="fill:#ffffff;stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
id="rect42" />
<!-- Line: box -->
<rect
- x="300"
- y="1500"
+ x="312.34076"
+ y="3017.7224"
width="5700"
- height="3750"
+ height="3594.5476"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; "
+ style="fill:#ffff00;stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
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" />
+ style="stroke:#00d1d1;stroke-width:29.99464035;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline46"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- 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" />
+ style="stroke:#00d1d1;stroke-width:29.99464035;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline50"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- 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" />
+ style="stroke:#00d1d1;stroke-width:29.99464035;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline54"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- 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" />
+ style="stroke:#00d1d1;stroke-width:29.99464035;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline58"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- 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" />
+ style="stroke:#00d1d1;stroke-width:29.99464035;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline62"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- 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" />
+ <ellipse
+ cx="2862.3408"
+ cy="5749.5786"
+ style="fill:#000000;stroke:#000000;stroke-width:13.70675087"
+ id="circle86"
+ rx="76"
+ ry="72.849495" />
<!-- Circle -->
- <circle
- cx="3150"
- cy="4350"
- r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
- id="circle88" />
+ <ellipse
+ cx="3162.3408"
+ cy="5749.5786"
+ style="fill:#000000;stroke:#000000;stroke-width:13.70675087"
+ id="circle88"
+ rx="76"
+ ry="72.849495" />
<!-- Circle -->
- <circle
- cx="3450"
- cy="4350"
- r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
- id="circle90" />
+ <ellipse
+ cx="3462.3408"
+ cy="5749.5786"
+ style="fill:#000000;stroke:#000000;stroke-width:13.70675087"
+ id="circle90"
+ rx="76"
+ ry="72.849495" />
<!-- Circle -->
- <circle
- cx="1350"
- cy="5550"
- r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
- id="circle92" />
+ <ellipse
+ cx="1362.3407"
+ cy="6899.834"
+ style="fill:#000000;stroke:#000000;stroke-width:13.70675087"
+ id="circle92"
+ rx="76"
+ ry="72.849495" />
<!-- Circle -->
- <circle
- cx="1650"
- cy="5550"
- r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
- id="circle94" />
+ <ellipse
+ cx="1662.3407"
+ cy="6899.834"
+ style="fill:#000000;stroke:#000000;stroke-width:13.70675087"
+ id="circle94"
+ rx="76"
+ ry="72.849495" />
<!-- Circle -->
- <circle
- cx="1950"
- cy="5550"
- r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
- id="circle96" />
+ <ellipse
+ cx="1962.3407"
+ cy="6899.834"
+ style="fill:#000000;stroke:#000000;stroke-width:13.70675087"
+ id="circle96"
+ rx="76"
+ ry="72.849495" />
<!-- Circle -->
- <circle
- cx="4350"
- cy="5550"
- r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
- id="circle98" />
+ <ellipse
+ cx="4362.3408"
+ cy="6899.834"
+ style="fill:#000000;stroke:#000000;stroke-width:13.70675087"
+ id="circle98"
+ rx="76"
+ ry="72.849495" />
<!-- Circle -->
- <circle
- cx="4650"
- cy="5550"
- r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
- id="circle100" />
+ <ellipse
+ cx="4662.3408"
+ cy="6899.834"
+ style="fill:#000000;stroke:#000000;stroke-width:13.70675087"
+ id="circle100"
+ rx="76"
+ ry="72.849495" />
<!-- Circle -->
- <circle
- cx="4950"
- cy="5550"
- r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
- id="circle102" />
+ <ellipse
+ cx="4962.3408"
+ cy="6899.834"
+ style="fill:#000000;stroke:#000000;stroke-width:13.70675087"
+ id="circle102"
+ rx="76"
+ ry="72.849495" />
<!-- Line: box -->
<rect
- x="7350"
- y="7950"
+ x="6745.3027"
+ y="8146.0654"
width="1500"
- height="900"
+ height="862.69141"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; "
+ style="stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
id="rect104" />
<!-- Line: box -->
<rect
- x="7350"
- y="9450"
+ x="6745.3027"
+ y="9583.8857"
width="1500"
- height="900"
+ height="862.69141"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; "
+ style="stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
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" />
+ style="stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Mend)"
+ id="polyline108"
+ transform="matrix(1,0,0,0.95854605,-604.69715,525.62477)" />
<!-- Arrowhead on XXXpoint 8100 8850 - 8100 9510-->
<!-- Line: box -->
<rect
- x="7350"
- y="10950"
+ x="6745.3027"
+ y="11021.704"
width="1500"
- height="900"
+ height="862.69141"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; "
+ style="stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
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" />
+ style="stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Mend)"
+ id="polyline114"
+ transform="matrix(1,0,0,0.95854605,-604.69715,525.62477)" />
<!-- Arrowhead on XXXpoint 8100 10350 - 8100 11010-->
<!-- Line: box -->
<rect
- x="750"
- y="3900"
+ x="762.34076"
+ y="5318.2324"
width="1800"
- height="900"
+ height="862.69141"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; "
+ style="fill:#ffbfbf;stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
id="rect118" />
<!-- Line: box -->
<rect
- x="300"
- y="7050"
+ x="312.34076"
+ y="8337.6533"
width="1500"
- height="900"
+ height="862.69141"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; "
+ style="fill:#87cfff;stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
id="rect120" />
<!-- Line: box -->
<rect
- x="3750"
- y="3900"
+ x="3762.3408"
+ y="5318.2324"
width="1800"
- height="900"
+ height="862.69141"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; "
+ style="fill:#ffbfbf;stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
id="rect122" />
<!-- Line: box -->
<rect
- x="4500"
- y="5850"
+ x="4512.3408"
+ y="7187.3975"
width="1500"
- height="900"
+ height="862.69141"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; "
+ style="fill:#87cfff;stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
id="rect124" />
<!-- Line: box -->
<rect
- x="3300"
- y="7050"
+ x="3312.3408"
+ y="8337.6533"
width="1500"
- height="900"
+ height="862.69141"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; "
+ style="fill:#87cfff;stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
id="rect126" />
<!-- Line: box -->
<rect
- x="2250"
- y="2100"
+ x="2262.3408"
+ y="3592.8503"
width="1800"
- height="900"
+ height="862.69141"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; "
+ style="fill:#ffbfbf;stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
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 -->
+ <!-- Line: box -->
+ <!-- Line: box -->
<!-- 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"
+ x="1512.3407"
+ y="7187.3975"
width="1500"
- height="900"
+ height="862.69141"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; "
+ style="fill:#87cfff;stroke:#000000;stroke-width:29.37160873;stroke-linecap:butt;stroke-linejoin:miter"
id="rect138" />
<!-- Text -->
<text
xml:space="preserve"
- x="8100"
- y="8250"
- fill="#000000"
- font-family="Courier"
+ x="7338.3037"
+ y="8614.0625"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text140">struct</text>
+ id="text140"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">struct</text>
<!-- Text -->
<text
xml:space="preserve"
- x="8100"
- y="8550"
- fill="#000000"
- font-family="Courier"
+ x="7338.3037"
+ y="8907.7783"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text142">rcu_head</text>
+ id="text142"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">rcu_head</text>
<!-- Text -->
<text
xml:space="preserve"
- x="8100"
- y="9750"
- fill="#000000"
- font-family="Courier"
+ x="7338.3037"
+ y="10082.644"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text144">struct</text>
+ id="text144"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">struct</text>
<!-- Text -->
<text
xml:space="preserve"
- x="8100"
- y="10050"
- fill="#000000"
- font-family="Courier"
+ x="7338.3037"
+ y="10376.36"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text146">rcu_head</text>
+ id="text146"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">rcu_head</text>
<!-- Text -->
<text
xml:space="preserve"
- x="8100"
- y="11250"
- fill="#000000"
- font-family="Courier"
+ x="7338.3037"
+ y="11551.224"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text148">struct</text>
+ id="text148"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">struct</text>
<!-- Text -->
<text
xml:space="preserve"
- x="8100"
- y="11550"
- fill="#000000"
- font-family="Courier"
+ x="7338.3037"
+ y="11844.94"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text150">rcu_head</text>
+ id="text150"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">rcu_head</text>
<!-- Text -->
<text
xml:space="preserve"
- x="6000"
- y="1200"
- fill="#000000"
- font-family="Helvetica"
+ x="5886.4043"
+ y="2788.5688"
font-style="normal"
font-weight="normal"
font-size="192"
- text-anchor="end"
- id="text152">rcu_sched</text>
+ id="text152"
+ style="font-style:normal;font-weight:normal;font-size:187.978302px;font-family:Helvetica;text-anchor:end;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">rcu_state</text>
+ <!-- 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"
+ x="3096.1016"
+ y="3963.4336"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text156">struct</text>
+ id="text156"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">struct</text>
<!-- Text -->
<text
xml:space="preserve"
- x="3150"
- y="2700"
- fill="#000000"
- font-family="Courier"
+ x="3096.1016"
+ y="4257.1494"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text158">rcu_node</text>
+ id="text158"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">rcu_node</text>
<!-- Text -->
<text
xml:space="preserve"
- x="1650"
- y="4200"
- fill="#000000"
- font-family="Courier"
+ x="1627.5209"
+ y="5725.7305"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text160">struct</text>
+ id="text160"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">struct</text>
<!-- Text -->
<text
xml:space="preserve"
- x="1650"
- y="4500"
- fill="#000000"
- font-family="Courier"
+ x="1627.5209"
+ y="6019.4463"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text162">rcu_node</text>
+ id="text162"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">rcu_node</text>
<!-- Text -->
<text
xml:space="preserve"
- x="4650"
- y="4500"
- fill="#000000"
- font-family="Courier"
+ x="4564.6821"
+ y="6019.4463"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text164">rcu_node</text>
+ id="text164"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">rcu_node</text>
<!-- Text -->
<text
xml:space="preserve"
- x="4650"
- y="4200"
- fill="#000000"
- font-family="Courier"
+ x="4564.6821"
+ y="5725.7305"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text166">struct</text>
+ id="text166"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">struct</text>
<!-- Text -->
<text
xml:space="preserve"
- x="2250"
- y="6150"
- fill="#000000"
- font-family="Courier"
+ x="2214.9531"
+ y="7634.8848"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text168">struct</text>
+ id="text168"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">struct</text>
<!-- Text -->
<text
xml:space="preserve"
- x="2250"
- y="6450"
- fill="#000000"
- font-family="Courier"
+ x="2214.9531"
+ y="7928.6011"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text170">rcu_data</text>
+ id="text170"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">rcu_data</text>
<!-- Text -->
<text
xml:space="preserve"
- x="1050"
- y="7350"
- fill="#000000"
- font-family="Courier"
+ x="1040.0886"
+ y="8809.749"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text172">struct</text>
+ id="text172"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">struct</text>
<!-- Text -->
<text
xml:space="preserve"
- x="1050"
- y="7650"
- fill="#000000"
- font-family="Courier"
+ x="1040.0886"
+ y="9103.4648"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text174">rcu_data</text>
+ id="text174"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">rcu_data</text>
<!-- Text -->
<text
xml:space="preserve"
- x="5250"
- y="6150"
- fill="#000000"
- font-family="Courier"
+ x="5152.1138"
+ y="7634.8848"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text176">struct</text>
+ id="text176"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">struct</text>
<!-- Text -->
<text
xml:space="preserve"
- x="5250"
- y="6450"
- fill="#000000"
- font-family="Courier"
+ x="5152.1138"
+ y="7928.6011"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text178">rcu_data</text>
+ id="text178"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">rcu_data</text>
<!-- Text -->
<text
xml:space="preserve"
- x="4050"
- y="7350"
- fill="#000000"
- font-family="Courier"
+ x="3977.2495"
+ y="8809.749"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text180">struct</text>
+ id="text180"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">struct</text>
<!-- Text -->
<text
xml:space="preserve"
- x="4050"
- y="7650"
- fill="#000000"
- font-family="Courier"
+ x="3977.2495"
+ y="9103.4648"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text182">rcu_data</text>
+ id="text182"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:middle;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">rcu_data</text>
<!-- Text -->
<text
xml:space="preserve"
- x="450"
- y="1800"
- fill="#000000"
- font-family="Courier"
+ x="452.6564"
+ y="3376.0012"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="start"
- id="text184">struct rcu_state</text>
+ id="text184"
+ style="font-style:normal;font-weight:bold;font-size:187.978302px;font-family:Courier;text-anchor:start;fill:#000000;stroke-width:0.02447634in"
+ transform="scale(1.0213945,0.97905363)">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" />
+ style="stroke:#00d1d1;stroke-width:29.99464035;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline204"
+ transform="matrix(1,0,0,0.95854605,12.340758,1579.9033)" />
<!-- Arrowhead on XXXpoint 5250 5850 - 5250 4740-->
+ <path
+ style="fill:none;stroke:#000000;stroke-width:34.24744034;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;marker-end:url(#marker1177)"
+ d="m 6000.1472,7564.2558 c 1498.5508,0 1498.5508,0 1498.5508,0 v 520.0252"
+ id="path886"
+ inkscape:connector-curvature="0" />
</g>
</svg>
diff --git a/Documentation/RCU/Design/Data-Structures/Data-Structures.html b/Documentation/RCU/Design/Data-Structures/Data-Structures.html
index f5120a0..c30c195 100644
--- a/Documentation/RCU/Design/Data-Structures/Data-Structures.html
+++ b/Documentation/RCU/Design/Data-Structures/Data-Structures.html
@@ -23,8 +23,6 @@
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">
@@ -127,9 +125,11 @@
</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.
+On the other hand, you can set both <tt>CONFIG_RCU_FANOUT</tt> and
+<tt>CONFIG_RCU_FANOUT_LEAF</tt> to be as small as 2, which would result
+in a 16-CPU test using a 4-level tree.
+This can be useful for testing large-system capabilities on small test
+machines.
</p><p>This multi-level combining tree allows us to get most of the
performance and scalability
@@ -154,44 +154,8 @@
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)
+RCU callbacks, either directly via <tt>call_rcu()</tt>
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
@@ -214,9 +178,6 @@
<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
@@ -272,11 +233,6 @@
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.
@@ -287,14 +243,14 @@
<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.
+the <tt>rcu_state</tt>, <tt>rcu_node</tt> and <tt>rcu_data</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.
+represents the state of RCU in the system.
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
@@ -389,7 +345,7 @@
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.
+zero, then 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.
@@ -419,10 +375,10 @@
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.
+<p>The <tt>->name</tt> and <tt>->abbr</tt> fields distinguish
+between preemptible RCU (“rcu_preempt” and “p”)
+and non-preemptible RCU (“rcu_sched” and “s”).
+These fields are used for diagnostic and tracing purposes.
<h3><a name="The rcu_node Structure">
The <tt>rcu_node</tt> Structure</a></h3>
@@ -971,25 +927,31 @@
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.
+all at once at callback-invocation time (<tt>rcu_do_batch</tt>), due
+to which <tt>->head</tt> may be set to NULL if there are no not-done
+callbacks remaining in the <tt>rcu_segcblist</tt>.
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.
+callbacks are placed back on the <tt>RCU_DONE_TAIL</tt> segment and
+<tt>->head</tt> once again points to the start of the segment.
+In short, the head field can briefly be <tt>NULL</tt> even though the
+CPU has callbacks present the entire time.
+Therefore, it is not appropriate to test the <tt>->head</tt> pointer
+for <tt>NULL</tt>.
+
+<p>In contrast, the <tt>->len</tt> and <tt>->len_lazy</tt> counts
+are adjusted only after the corresponding callbacks have been invoked.
+This means that the <tt>->len</tt> count is zero only if
+the <tt>rcu_segcblist</tt> structure really is devoid of callbacks.
Of course, off-CPU sampling of the <tt>->len</tt> count requires
-the use of appropriate synchronization, for example, memory barriers.
+careful 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.
+<p>The <tt>rcu_data</tt> maintains the per-CPU state for the RCU subsystem.
The fields in this structure may be accessed only from the corresponding
CPU (and from tracing) unless otherwise stated.
This structure is the
@@ -1015,30 +977,19 @@
<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;
+ 2 struct rcu_node *mynode;
+ 3 unsigned long grpmask;
+ 4 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.
+corresponding CPU 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.
+These two fields are constant and therefore do not require synchronization.
-</p><p>The <tt>->grpmask</tt> field indicates the bit in
+<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.
@@ -1057,12 +1008,12 @@
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.
+<p>The <tt>->gp_seq</tt> field is the counterpart of the field of the same
+name in the <tt>rcu_state</tt> and <tt>rcu_node</tt> structures. The
+<tt>->gp_seq_needed</tt> field is the counterpart of the field of the same
+name in the rcu_node</tt> structure.
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
@@ -1103,10 +1054,6 @@
<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>
@@ -1179,26 +1126,22 @@
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:
+<p>
+This portion of the rcu_data structure is declared 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;
+ 5 bool rcu_urgent_qs;
</pre>
+<p>These fields in the rcu_data structure maintain the per-CPU dyntick-idle
+state for the corresponding CPU.
+The fields may be accessed only from the corresponding CPU (and from tracing)
+unless otherwise stated.
+
<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.
@@ -1227,9 +1170,11 @@
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.
+CPU's transitions to and from either dyntick-idle or user mode, so
+that this counter has an even value when the CPU is in dyntick-idle
+mode or user mode and an odd value otherwise. The transitions to/from
+user mode need to be counted for user mode adaptive-ticks support
+(see timers/NO_HZ.txt).
</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
@@ -1238,19 +1183,12 @@
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.
+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 path
+(<tt>rcu_note_context_switch</tt>) and the cond_resched code.
<table>
<tr><th> </th></tr>
@@ -1372,8 +1310,7 @@
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_get_root()</tt>, <tt>rcu_for_each_node_breadth_first</tt> and
<tt>rcu_for_each_leaf_node()</tt> function and macros:
<pre>
@@ -1386,13 +1323,9 @@
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)++)
+ 10 #define rcu_for_each_leaf_node(rsp, rnp) \
+ 11 for ((rnp) = (rsp)->level[NUM_RCU_LVLS - 1]; \
+ 12 (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++)
</pre>
<p>The <tt>rcu_get_root()</tt> simply returns a pointer to the
@@ -1405,10 +1338,7 @@
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
+Similarly, 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.
@@ -1416,15 +1346,14 @@
<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
+ What does
<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.
+ <tt>rcu_for_each_leaf_node()</tt> traverses the single node.
</font></td></tr>
<tr><td> </td></tr>
</table>
@@ -1432,11 +1361,11 @@
<h3><a name="Summary">
Summary</a></h3>
-So each flavor of RCU is represented by an <tt>rcu_state</tt> structure,
+So the state 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.
+state is tracked by dynticks-related fields in the <tt>rcu_data</tt> structure.
If you made it this far, you are well prepared to read the code
walkthroughs in the other articles in this series.
diff --git a/Documentation/RCU/Design/Data-Structures/blkd_task.svg b/Documentation/RCU/Design/Data-Structures/blkd_task.svg
index 00e810b..bed13e9 100644
--- a/Documentation/RCU/Design/Data-Structures/blkd_task.svg
+++ b/Documentation/RCU/Design/Data-Structures/blkd_task.svg
@@ -14,12 +14,12 @@
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"
+ height="6.5999999in"
+ viewBox="-44 -44 12088 7895.4414"
id="svg2"
version="1.1"
- inkscape:version="0.48.4 r9939"
- sodipodi:docname="blkd_task.fig">
+ inkscape:version="0.92.2pre0 (973e216, 2017-07-25)"
+ sodipodi:docname="blkd_task.svg">
<metadata
id="metadata212">
<rdf:RDF>
@@ -37,15 +37,16 @@
<marker
inkscape:stockid="Arrow1Mend"
orient="auto"
- refY="0.0"
- refX="0.0"
+ refY="0"
+ refX="0"
id="Arrow1Mend"
- style="overflow:visible;">
+ 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)" />
+ d="M 0,0 5,-5 -12.5,0 5,5 Z"
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1.00000003pt"
+ transform="matrix(-0.4,0,0,-0.4,-4,0)"
+ inkscape:connector-curvature="0" />
</marker>
</defs>
<sodipodi:namedview
@@ -57,787 +58,574 @@
guidetolerance="10"
inkscape:pageopacity="0"
inkscape:pageshadow="2"
- inkscape:window-width="1087"
- inkscape:window-height="1144"
+ inkscape:window-width="1920"
+ inkscape:window-height="1019"
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" />
+ inkscape:cx="456.40569"
+ inkscape:cy="348.88682"
+ inkscape:window-x="0"
+ inkscape:window-y="0"
+ inkscape:window-maximized="1"
+ inkscape:current-layer="g4"
+ showguides="false" />
<g
- style="stroke-width:.025in; fill:none"
- id="g4">
+ style="fill:none;stroke-width:0.025in"
+ id="g4"
+ transform="translate(0,-2393.6637)">
<!-- 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" />
+ style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8"
+ id="polyline14"
+ transform="translate(23.757862,2185.7233)" />
<!-- 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" />
+ style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8"
+ id="polyline18"
+ transform="translate(23.757862,2185.7233)" />
<!-- 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" />
+ style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8"
+ id="polyline22"
+ transform="translate(23.757862,2185.7233)" />
<!-- 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" />
+ style="stroke:#00ff00;stroke-width:14;stroke-miterlimit:8"
+ id="polyline26"
+ transform="translate(23.757862,2185.7233)" />
<!-- Line: box -->
<rect
- x="0"
- y="450"
+ x="23.757858"
+ y="2635.7231"
width="6300"
height="7350"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffffff; "
+ style="fill:#ffffff;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
id="rect28" />
<!-- Line: box -->
<rect
- x="300"
- y="1050"
+ x="323.75787"
+ y="3235.7231"
width="5700"
height="3750"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; "
+ style="fill:#ffff00;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
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" />
+ style="stroke:#00d1d1;stroke-width:30.00057793;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline32"
+ transform="translate(23.757862,2185.7233)" />
<!-- 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" />
+ style="stroke:#00d1d1;stroke-width:30.00057793;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline36"
+ transform="translate(23.757862,2185.7233)" />
<!-- 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" />
+ style="stroke:#00d1d1;stroke-width:30.00057793;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline40"
+ transform="translate(23.757862,2185.7233)" />
<!-- 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" />
+ style="stroke:#00d1d1;stroke-width:30.00057793;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline44"
+ transform="translate(23.757862,2185.7233)" />
<!-- 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" />
+ style="stroke:#00d1d1;stroke-width:30.00057793;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline48"
+ transform="translate(23.757862,2185.7233)" />
<!-- 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"
+ cx="2873.7581"
+ cy="6085.7236"
r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
+ style="fill:#000000;stroke:#000000;stroke-width:14"
id="circle68" />
<!-- Circle -->
<circle
- cx="3150"
- cy="3900"
+ cx="3173.7581"
+ cy="6085.7236"
r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
+ style="fill:#000000;stroke:#000000;stroke-width:14"
id="circle70" />
<!-- Circle -->
<circle
- cx="3450"
- cy="3900"
+ cx="3473.7581"
+ cy="6085.7236"
r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
+ style="fill:#000000;stroke:#000000;stroke-width:14"
id="circle72" />
<!-- Circle -->
<circle
- cx="1350"
- cy="5100"
+ cx="1373.7578"
+ cy="7285.7236"
r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
+ style="fill:#000000;stroke:#000000;stroke-width:14"
id="circle74" />
<!-- Circle -->
<circle
- cx="1650"
- cy="5100"
+ cx="1673.7578"
+ cy="7285.7236"
r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
+ style="fill:#000000;stroke:#000000;stroke-width:14"
id="circle76" />
<!-- Circle -->
<circle
- cx="1950"
- cy="5100"
+ cx="1973.7578"
+ cy="7285.7236"
r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
+ style="fill:#000000;stroke:#000000;stroke-width:14"
id="circle78" />
<!-- Circle -->
<circle
- cx="4350"
- cy="5100"
+ cx="4373.7578"
+ cy="7285.7236"
r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
+ style="fill:#000000;stroke:#000000;stroke-width:14"
id="circle80" />
<!-- Circle -->
<circle
- cx="4650"
- cy="5100"
+ cx="4673.7578"
+ cy="7285.7236"
r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
+ style="fill:#000000;stroke:#000000;stroke-width:14"
id="circle82" />
<!-- Circle -->
<circle
- cx="4950"
- cy="5100"
+ cx="4973.7578"
+ cy="7285.7236"
r="76"
- style="fill:#000000;stroke:#000000;stroke-width:14;"
+ style="fill:#000000;stroke:#000000;stroke-width:14"
id="circle84" />
<!-- Line: box -->
<rect
- x="750"
- y="3450"
+ x="773.75781"
+ y="5635.7236"
width="1800"
height="900"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; "
+ style="fill:#ffbfbf;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
id="rect86" />
<!-- Line: box -->
<rect
- x="300"
- y="6600"
+ x="323.75787"
+ y="8785.7227"
width="1500"
height="900"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; "
+ style="fill:#87cfff;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
id="rect88" />
<!-- Line: box -->
<rect
- x="4500"
- y="5400"
+ x="4523.7578"
+ y="7585.7236"
width="1500"
height="900"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; "
+ style="fill:#87cfff;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
id="rect90" />
<!-- Line: box -->
<rect
- x="3300"
- y="6600"
+ x="3323.7581"
+ y="8785.7227"
width="1500"
height="900"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; "
+ style="fill:#87cfff;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
id="rect92" />
<!-- Line: box -->
<rect
- x="2250"
- y="1650"
+ x="2273.7581"
+ y="3835.7231"
width="1800"
height="900"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; "
+ style="fill:#ffbfbf;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
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 -->
+ <!-- Line: box -->
+ <!-- Line: box -->
<!-- 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"
+ x="1523.7578"
+ y="7585.7236"
width="1500"
height="900"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#87cfff; "
+ style="fill:#87cfff;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
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" />
+ points="7350,2850 7350,5100 5550,4350 5550,3450 "
+ style="fill:#ffbfbf;stroke:#000000;stroke-width:14;stroke-linecap:butt;stroke-linejoin:miter;stroke-dasharray:120, 120"
+ id="polygon106"
+ transform="translate(23.757862,2185.7233)" />
<!-- 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" />
+ style="stroke:#000000;stroke-width:30.00057793;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline108"
+ transform="translate(23.757862,2185.7233)" />
<!-- Arrowhead on XXXpoint 9300 3150 - 10860 3150-->
<!-- Line: box -->
<rect
- x="10800"
- y="2850"
+ x="10823.758"
+ y="5035.7236"
width="1200"
height="750"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; "
+ style="stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
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" />
+ style="stroke:#000000;stroke-width:30.00057793;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline114"
+ transform="translate(23.757862,2185.7233)" />
<!-- Arrowhead on XXXpoint 11400 3600 - 11400 4410-->
<!-- Line: box -->
<rect
- x="10800"
- y="4350"
+ x="10823.758"
+ y="6535.7236"
width="1200"
height="750"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; "
+ style="stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
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" />
+ style="stroke:#000000;stroke-width:30.00057793;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline120"
+ transform="translate(23.757862,2185.7233)" />
<!-- Arrowhead on XXXpoint 11400 5100 - 11400 5910-->
<!-- Line: box -->
<rect
- x="10800"
- y="5850"
+ x="10823.758"
+ y="8035.7236"
width="1200"
height="750"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; "
+ style="stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
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" />
+ style="stroke:#000000;stroke-width:30.00057793;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline126"
+ transform="translate(23.757862,2185.7233)" />
<!-- 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" />
+ style="stroke:#000000;stroke-width:30.00057793;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline130"
+ transform="translate(23.757862,2185.7233)" />
<!-- Arrowhead on XXXpoint 9600 6150 - 10860 6150-->
<!-- Text -->
+ <!-- Text -->
<text
xml:space="preserve"
- x="6450"
- y="300"
- fill="#000000"
- font-family="Helvetica"
+ x="3173.7581"
+ y="4135.7231"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text136"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">struct</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="3173.7581"
+ y="4435.7236"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text138"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">rcu_node</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="1673.7578"
+ y="5935.7236"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text140"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">struct</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="1673.7578"
+ y="6235.7236"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text142"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">rcu_node</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="2273.7581"
+ y="7885.7236"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text144"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">struct</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="2273.7581"
+ y="8185.7236"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text146"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">rcu_data</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="1073.7578"
+ y="9085.7227"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text148"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">struct</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="1073.7578"
+ y="9385.7227"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text150"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">rcu_data</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="5273.7578"
+ y="7885.7236"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text152"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">struct</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="5273.7578"
+ y="8185.7236"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text154"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">rcu_data</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="4073.7578"
+ y="9085.7227"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text156"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">struct</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="4073.7578"
+ y="9385.7227"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text158"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">rcu_data</text>
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="473.75784"
+ y="3535.7231"
+ font-style="normal"
+ font-weight="bold"
+ font-size="192"
+ id="text160"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:start;fill:#000000">struct rcu_state</text>
+ <!-- Text -->
+ <!-- Text -->
+ <!-- Text -->
+ <!-- Text -->
+ <!-- Text -->
+ <!-- Text -->
+ <!-- Text -->
+ <!-- Text -->
+ <!-- Text -->
+ <text
+ xml:space="preserve"
+ x="6023.7578"
+ y="2935.7231"
font-style="normal"
font-weight="normal"
font-size="192"
- text-anchor="end"
- id="text134">rcu_bh</text>
+ id="text178"
+ style="font-style:normal;font-weight:normal;font-size:192px;font-family:Helvetica;text-anchor:end;fill:#000000">rcu_state</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"
+ x="11423.758"
+ y="5485.7236"
font-style="normal"
font-weight="normal"
font-size="216"
- text-anchor="middle"
- id="text180">T3</text>
+ id="text180"
+ style="font-style:normal;font-weight:normal;font-size:216px;font-family:Helvetica;text-anchor:middle;fill:#000000">T3</text>
<!-- Text -->
<text
xml:space="preserve"
- x="11400"
- y="4800"
- fill="#000000"
- font-family="Helvetica"
+ x="11423.758"
+ y="6985.7236"
font-style="normal"
font-weight="normal"
font-size="216"
- text-anchor="middle"
- id="text182">T2</text>
+ id="text182"
+ style="font-style:normal;font-weight:normal;font-size:216px;font-family:Helvetica;text-anchor:middle;fill:#000000">T2</text>
<!-- Text -->
<text
xml:space="preserve"
- x="11400"
- y="6300"
- fill="#000000"
- font-family="Helvetica"
+ x="11423.758"
+ y="8485.7227"
font-style="normal"
font-weight="normal"
font-size="216"
- text-anchor="middle"
- id="text184">T1</text>
+ id="text184"
+ style="font-style:normal;font-weight:normal;font-size:216px;font-family:Helvetica;text-anchor:middle;fill:#000000">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" />
+ style="stroke:#00d1d1;stroke-width:30.00057793;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)"
+ id="polyline186"
+ transform="translate(23.757862,2185.7233)" />
<!-- Arrowhead on XXXpoint 5250 5400 - 5250 4290-->
<!-- Line: box -->
<rect
- x="3750"
- y="3450"
+ x="3773.7581"
+ y="5635.7236"
width="1800"
height="900"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; "
+ style="fill:#ffbfbf;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
id="rect190" />
<!-- Line: box -->
<rect
- x="7350"
- y="2850"
+ x="7373.7578"
+ y="5035.7236"
width="1950"
height="750"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; "
+ style="fill:#ffbfbf;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
id="rect192" />
<!-- Line: box -->
<rect
- x="7350"
- y="3600"
+ x="7373.7578"
+ y="5785.7236"
width="1950"
height="750"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; "
+ style="fill:#ffbfbf;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
id="rect194" />
<!-- Line: box -->
<rect
- x="7350"
- y="4350"
+ x="7373.7578"
+ y="6535.7236"
width="1950"
height="750"
rx="0"
- style="stroke:#000000;stroke-width:30; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; "
+ style="fill:#ffbfbf;stroke:#000000;stroke-width:30;stroke-linecap:butt;stroke-linejoin:miter"
id="rect196" />
<!-- Text -->
<text
xml:space="preserve"
- x="4650"
- y="4050"
- fill="#000000"
- font-family="Courier"
+ x="4673.7578"
+ y="6235.7236"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text198">rcu_node</text>
+ id="text198"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">rcu_node</text>
<!-- Text -->
<text
xml:space="preserve"
- x="4650"
- y="3750"
- fill="#000000"
- font-family="Courier"
+ x="4673.7578"
+ y="5935.7236"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="middle"
- id="text200">struct</text>
+ id="text200"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:middle;fill:#000000">struct</text>
<!-- Text -->
<text
xml:space="preserve"
- x="7500"
- y="3300"
- fill="#000000"
- font-family="Courier"
+ x="7523.7578"
+ y="5485.7236"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="start"
- id="text202">blkd_tasks</text>
+ id="text202"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:start;fill:#000000">blkd_tasks</text>
<!-- Text -->
<text
xml:space="preserve"
- x="7500"
- y="4050"
- fill="#000000"
- font-family="Courier"
+ x="7523.7578"
+ y="6235.7236"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="start"
- id="text204">gp_tasks</text>
+ id="text204"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:start;fill:#000000">gp_tasks</text>
<!-- Text -->
<text
xml:space="preserve"
- x="7500"
- y="4800"
- fill="#000000"
- font-family="Courier"
+ x="7523.7578"
+ y="6985.7236"
font-style="normal"
font-weight="bold"
font-size="192"
- text-anchor="start"
- id="text206">exp_tasks</text>
+ id="text206"
+ style="font-style:normal;font-weight:bold;font-size:192px;font-family:Courier;text-anchor:start;fill:#000000">exp_tasks</text>
</g>
</svg>
diff --git a/Documentation/RCU/Design/Expedited-Grace-Periods/ExpSchedFlow.svg b/Documentation/RCU/Design/Expedited-Grace-Periods/ExpSchedFlow.svg
index e4233ac..6189ffc 100644
--- a/Documentation/RCU/Design/Expedited-Grace-Periods/ExpSchedFlow.svg
+++ b/Documentation/RCU/Design/Expedited-Grace-Periods/ExpSchedFlow.svg
@@ -328,13 +328,13 @@
inkscape:window-height="1148"
id="namedview90"
showgrid="true"
- inkscape:zoom="0.80021373"
- inkscape:cx="462.49289"
- inkscape:cy="473.6718"
+ inkscape:zoom="0.69092787"
+ inkscape:cx="476.34085"
+ inkscape:cy="712.80957"
inkscape:window-x="770"
inkscape:window-y="24"
inkscape:window-maximized="0"
- inkscape:current-layer="g4114-9-3-9"
+ inkscape:current-layer="g4"
inkscape:snap-grids="false"
fit-margin-top="5"
fit-margin-right="5"
@@ -813,14 +813,18 @@
<text
sodipodi:linespacing="125%"
id="text4110-5-7-6-2-4-0"
- y="841.88086"
+ y="670.74316"
x="1460.1007"
style="font-size:267.24359131px;font-style:normal;font-weight:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans"
xml:space="preserve"><tspan
- y="841.88086"
+ y="670.74316"
x="1460.1007"
sodipodi:role="line"
- id="tspan4925-1-2-4-5">reched_cpu()</tspan></text>
+ id="tspan4925-1-2-4-5">Request</tspan><tspan
+ y="1004.7976"
+ x="1460.1007"
+ sodipodi:role="line"
+ id="tspan3100">context switch</tspan></text>
</g>
</g>
</svg>
diff --git a/Documentation/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-Periods.html b/Documentation/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-Periods.html
index 7394f03..57300db 100644
--- a/Documentation/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-Periods.html
+++ b/Documentation/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-Periods.html
@@ -12,10 +12,9 @@
lower efficiency and significant disturbance to attain shorter latencies.
<p>
-There are three flavors of RCU (RCU-bh, RCU-preempt, and RCU-sched),
-but only two flavors of expedited grace periods because the RCU-bh
-expedited grace period maps onto the RCU-sched expedited grace period.
-Each of the remaining two implementations is covered in its own section.
+There are two flavors of RCU (RCU-preempt and RCU-sched), with an earlier
+third RCU-bh flavor having been implemented in terms of the other two.
+Each of the two implementations is covered in its own section.
<ol>
<li> <a href="#Expedited Grace Period Design">
@@ -57,6 +56,7 @@
RCU-preempt Expedited Grace Periods</a></h2>
<p>
+<tt>CONFIG_PREEMPT=y</tt> kernels implement RCU-preempt.
The overall flow of the handling of a given CPU by an RCU-preempt
expedited grace period is shown in the following diagram:
@@ -73,10 +73,10 @@
in quiescent states.
Otherwise, the expedited grace period will use
<tt>smp_call_function_single()</tt> to send the CPU an IPI, which
-is handled by <tt>sync_rcu_exp_handler()</tt>.
+is handled by <tt>rcu_exp_handler()</tt>.
<p>
-However, because this is preemptible RCU, <tt>sync_rcu_exp_handler()</tt>
+However, because this is preemptible RCU, <tt>rcu_exp_handler()</tt>
can check to see if the CPU is currently running in an RCU read-side
critical section.
If not, the handler can immediately report a quiescent state.
@@ -140,30 +140,30 @@
RCU-sched Expedited Grace Periods</a></h2>
<p>
+<tt>CONFIG_PREEMPT=n</tt> kernels implement RCU-sched.
The overall flow of the handling of a given CPU by an RCU-sched
expedited grace period is shown in the following diagram:
<p><img src="ExpSchedFlow.svg" alt="ExpSchedFlow.svg" width="55%">
<p>
-As with RCU-preempt's <tt>synchronize_rcu_expedited()</tt>,
-<tt>synchronize_sched_expedited()</tt> ignores offline and
+As with RCU-preempt, RCU-sched's
+<tt>synchronize_rcu_expedited()</tt> ignores offline and
idle CPUs, again because they are in remotely detectable
quiescent states.
-However, the <tt>synchronize_rcu_expedited()</tt> handler
-is <tt>sync_sched_exp_handler()</tt>, and because the
+However, because the
<tt>rcu_read_lock_sched()</tt> and <tt>rcu_read_unlock_sched()</tt>
leave no trace of their invocation, in general it is not possible to tell
whether or not the current CPU is in an RCU read-side critical section.
-The best that <tt>sync_sched_exp_handler()</tt> can do is to check
+The best that RCU-sched's <tt>rcu_exp_handler()</tt> can do is to check
for idle, on the off-chance that the CPU went idle while the IPI
was in flight.
-If the CPU is idle, then tt>sync_sched_exp_handler()</tt> reports
+If the CPU is idle, then <tt>rcu_exp_handler()</tt> reports
the quiescent state.
-<p>
-Otherwise, the handler invokes <tt>resched_cpu()</tt>, which forces
-a future context switch.
+<p> Otherwise, the handler forces a future context switch by setting the
+NEED_RESCHED flag of the current task's thread flag and the CPU preempt
+counter.
At the time of the context switch, the CPU reports the quiescent state.
Should the CPU go offline first, it will report the quiescent state
at that time.
@@ -299,19 +299,18 @@
idle CPUs in the mask passed to <tt>rcu_report_exp_cpu_mult()</tt>.
<p>
-For RCU-sched, there is an additional check for idle in the IPI
-handler, <tt>sync_sched_exp_handler()</tt>.
+For RCU-sched, there is an additional check:
If the IPI has interrupted the idle loop, then
-<tt>sync_sched_exp_handler()</tt> invokes <tt>rcu_report_exp_rdp()</tt>
+<tt>rcu_exp_handler()</tt> invokes <tt>rcu_report_exp_rdp()</tt>
to report the corresponding quiescent state.
<p>
For RCU-preempt, there is no specific check for idle in the
-IPI handler (<tt>sync_rcu_exp_handler()</tt>), but because
+IPI handler (<tt>rcu_exp_handler()</tt>), but because
RCU read-side critical sections are not permitted within the
-idle loop, if <tt>sync_rcu_exp_handler()</tt> sees that the CPU is within
+idle loop, if <tt>rcu_exp_handler()</tt> sees that the CPU is within
RCU read-side critical section, the CPU cannot possibly be idle.
-Otherwise, <tt>sync_rcu_exp_handler()</tt> invokes
+Otherwise, <tt>rcu_exp_handler()</tt> invokes
<tt>rcu_report_exp_rdp()</tt> to report the corresponding quiescent
state, regardless of whether or not that quiescent state was due to
the CPU being idle.
@@ -626,6 +625,8 @@
<p>
With this refinement, synchronous grace periods can now be used from
task context pretty much any time during the life of the kernel.
+That is, aside from some points in the suspend, hibernate, or shutdown
+code path.
<h3><a name="Summary">
Summary</a></h3>
diff --git a/Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html b/Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html
index a346ce0..c64f8d2 100644
--- a/Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html
+++ b/Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html
@@ -34,12 +34,11 @@
period is guaranteed to see the effects of all accesses following the end
of that grace period that are within RCU read-side critical sections.
-<p>This guarantee is particularly pervasive for <tt>synchronize_sched()</tt>,
-for which RCU-sched read-side critical sections include any region
+<p>Note well that RCU-sched read-side critical sections include any region
of code for which preemption is disabled.
Given that each individual machine instruction can be thought of as
an extremely small region of preemption-disabled code, one can think of
-<tt>synchronize_sched()</tt> as <tt>smp_mb()</tt> on steroids.
+<tt>synchronize_rcu()</tt> as <tt>smp_mb()</tt> on steroids.
<p>RCU updaters use this guarantee by splitting their updates into
two phases, one of which is executed before the grace period and
@@ -77,7 +76,7 @@
<tt>smp_mb__after_unlock_lock()</tt> immediately after successful
acquisition of the lock.
-<p>Therefore, for any given <tt>rcu_node</tt> struction, any access
+<p>Therefore, for any given <tt>rcu_node</tt> structure, any access
happening before one of the above lock-release functions will be seen
by all CPUs as happening before any access happening after a later
one of the above lock-acquisition functions.
@@ -485,13 +484,13 @@
noted by <tt>rcu_node_context_switch()</tt> on the left.
On the other hand, if the CPU takes a scheduler-clock interrupt
while executing in usermode, a quiescent state will be noted by
-<tt>rcu_check_callbacks()</tt> on the right.
+<tt>rcu_sched_clock_irq()</tt> on the right.
Either way, the passage through a quiescent state will be noted
in a per-CPU variable.
<p>The next time an <tt>RCU_SOFTIRQ</tt> handler executes on
this CPU (for example, after the next scheduler-clock
-interrupt), <tt>__rcu_process_callbacks()</tt> will invoke
+interrupt), <tt>rcu_core()</tt> will invoke
<tt>rcu_check_quiescent_state()</tt>, which will notice the
recorded quiescent state, and invoke
<tt>rcu_report_qs_rdp()</tt>.
@@ -651,7 +650,7 @@
These callbacks are identified by <tt>rcu_advance_cbs()</tt>,
which is usually invoked by <tt>__note_gp_changes()</tt>.
As shown in the diagram below, this invocation can be triggered by
-the scheduling-clock interrupt (<tt>rcu_check_callbacks()</tt> on
+the scheduling-clock interrupt (<tt>rcu_sched_clock_irq()</tt> on
the left) or by idle entry (<tt>rcu_cleanup_after_idle()</tt> on
the right, but only for kernels build with
<tt>CONFIG_RCU_FAST_NO_HZ=y</tt>).
diff --git a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-callback-invocation.svg b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-callback-invocation.svg
index 8324083..3fcf0c1 100644
--- a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-callback-invocation.svg
+++ b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-callback-invocation.svg
@@ -349,7 +349,7 @@
font-weight="bold"
font-size="192"
id="text202-7-5"
- style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_check_callbacks()</text>
+ style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_sched_clock_irq()</text>
<rect
x="7069.6187"
y="5087.4678"
diff --git a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp.svg b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp.svg
index acd73c7..2bcd742 100644
--- a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp.svg
+++ b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp.svg
@@ -3902,7 +3902,7 @@
font-style="normal"
y="-4418.6582"
x="3745.7725"
- xml:space="preserve">rcu_check_callbacks()</text>
+ xml:space="preserve">rcu_sched_clock_irq()</text>
</g>
<g
transform="translate(-850.30204,55463.106)"
@@ -3924,7 +3924,7 @@
font-style="normal"
y="-4418.6582"
x="3745.7725"
- xml:space="preserve">rcu_process_callbacks()</text>
+ xml:space="preserve">rcu_core()</text>
<text
style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier"
id="text202-7-5-3-27-0"
@@ -3933,7 +3933,7 @@
font-style="normal"
y="-4165.7954"
x="3745.7725"
- xml:space="preserve">rcu_check_quiescent_state())</text>
+ xml:space="preserve">rcu_check_quiescent_state()</text>
<text
style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier"
id="text202-7-5-3-27-0-9"
@@ -4968,7 +4968,7 @@
font-weight="bold"
font-size="192"
id="text202-7-5-19"
- style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_check_callbacks()</text>
+ style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_sched_clock_irq()</text>
<rect
x="5314.2671"
y="82817.688"
diff --git a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-qs.svg b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-qs.svg
index 149bec2..779c9ac 100644
--- a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-qs.svg
+++ b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-qs.svg
@@ -775,7 +775,7 @@
font-style="normal"
y="-4418.6582"
x="3745.7725"
- xml:space="preserve">rcu_check_callbacks()</text>
+ xml:space="preserve">rcu_sched_clock_irq()</text>
</g>
<g
transform="translate(399.7744,828.86448)"
@@ -797,7 +797,7 @@
font-style="normal"
y="-4418.6582"
x="3745.7725"
- xml:space="preserve">rcu_process_callbacks()</text>
+ xml:space="preserve">rcu_core()</text>
<text
style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier"
id="text202-7-5-3-27-0"
@@ -806,7 +806,7 @@
font-style="normal"
y="-4165.7954"
x="3745.7725"
- xml:space="preserve">rcu_check_quiescent_state())</text>
+ xml:space="preserve">rcu_check_quiescent_state()</text>
<text
style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier"
id="text202-7-5-3-27-0-9"
diff --git a/Documentation/RCU/Design/Requirements/Requirements.html b/Documentation/RCU/Design/Requirements/Requirements.html
index 4969022..467251f 100644
--- a/Documentation/RCU/Design/Requirements/Requirements.html
+++ b/Documentation/RCU/Design/Requirements/Requirements.html
@@ -900,8 +900,6 @@
Grace Periods Don't Partition Read-Side Critical Sections</a>
<li> <a href="#Read-Side Critical Sections Don't Partition Grace Periods">
Read-Side Critical Sections Don't Partition Grace Periods</a>
-<li> <a href="#Disabling Preemption Does Not Block Grace Periods">
- Disabling Preemption Does Not Block Grace Periods</a>
</ol>
<h3><a name="Readers Impose Minimal Ordering">Readers Impose Minimal Ordering</a></h3>
@@ -1259,56 +1257,6 @@
<tr><td> </td></tr>
</table>
-<h3><a name="Disabling Preemption Does Not Block Grace Periods">
-Disabling Preemption Does Not Block Grace Periods</a></h3>
-
-<p>
-There was a time when disabling preemption on any given CPU would block
-subsequent grace periods.
-However, this was an accident of implementation and is not a requirement.
-And in the current Linux-kernel implementation, disabling preemption
-on a given CPU in fact does not block grace periods, as Oleg Nesterov
-<a href="https://lkml.kernel.org/g/20150614193825.GA19582@redhat.com">demonstrated</a>.
-
-<p>
-If you need a preempt-disable region to block grace periods, you need to add
-<tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>, for example
-as follows:
-
-<blockquote>
-<pre>
- 1 preempt_disable();
- 2 rcu_read_lock();
- 3 do_something();
- 4 rcu_read_unlock();
- 5 preempt_enable();
- 6
- 7 /* Spinlocks implicitly disable preemption. */
- 8 spin_lock(&mylock);
- 9 rcu_read_lock();
-10 do_something();
-11 rcu_read_unlock();
-12 spin_unlock(&mylock);
-</pre>
-</blockquote>
-
-<p>
-In theory, you could enter the RCU read-side critical section first,
-but it is more efficient to keep the entire RCU read-side critical
-section contained in the preempt-disable region as shown above.
-Of course, RCU read-side critical sections that extend outside of
-preempt-disable regions will work correctly, but such critical sections
-can be preempted, which forces <tt>rcu_read_unlock()</tt> to do
-more work.
-And no, this is <i>not</i> an invitation to enclose all of your RCU
-read-side critical sections within preempt-disable regions, because
-doing so would degrade real-time response.
-
-<p>
-This non-requirement appeared with preemptible RCU.
-If you need a grace period that waits on non-preemptible code regions, use
-<a href="#Sched Flavor">RCU-sched</a>.
-
<h2><a name="Parallelism Facts of Life">Parallelism Facts of Life</a></h2>
<p>
@@ -1383,6 +1331,7 @@
<ol>
<li> <a href="#Specialization">Specialization</a>
<li> <a href="#Performance and Scalability">Performance and Scalability</a>
+<li> <a href="#Forward Progress">Forward Progress</a>
<li> <a href="#Composability">Composability</a>
<li> <a href="#Corner Cases">Corner Cases</a>
</ol>
@@ -1647,7 +1596,7 @@
16 struct foo *p;
17
18 spin_lock(&gp_lock);
-19 p = rcu_dereference(gp);
+19 p = rcu_access_pointer(gp);
20 if (!p) {
21 spin_unlock(&gp_lock);
22 return false;
@@ -1824,6 +1773,106 @@
RCU thus provides a range of tools to allow updaters to strike the
required tradeoff between latency, flexibility and CPU overhead.
+<h3><a name="Forward Progress">Forward Progress</a></h3>
+
+<p>
+In theory, delaying grace-period completion and callback invocation
+is harmless.
+In practice, not only are memory sizes finite but also callbacks sometimes
+do wakeups, and sufficiently deferred wakeups can be difficult
+to distinguish from system hangs.
+Therefore, RCU must provide a number of mechanisms to promote forward
+progress.
+
+<p>
+These mechanisms are not foolproof, nor can they be.
+For one simple example, an infinite loop in an RCU read-side critical
+section must by definition prevent later grace periods from ever completing.
+For a more involved example, consider a 64-CPU system built with
+<tt>CONFIG_RCU_NOCB_CPU=y</tt> and booted with <tt>rcu_nocbs=1-63</tt>,
+where CPUs 1 through 63 spin in tight loops that invoke
+<tt>call_rcu()</tt>.
+Even if these tight loops also contain calls to <tt>cond_resched()</tt>
+(thus allowing grace periods to complete), CPU 0 simply will
+not be able to invoke callbacks as fast as the other 63 CPUs can
+register them, at least not until the system runs out of memory.
+In both of these examples, the Spiderman principle applies: With great
+power comes great responsibility.
+However, short of this level of abuse, RCU is required to
+ensure timely completion of grace periods and timely invocation of
+callbacks.
+
+<p>
+RCU takes the following steps to encourage timely completion of
+grace periods:
+
+<ol>
+<li> If a grace period fails to complete within 100 milliseconds,
+ RCU causes future invocations of <tt>cond_resched()</tt> on
+ the holdout CPUs to provide an RCU quiescent state.
+ RCU also causes those CPUs' <tt>need_resched()</tt> invocations
+ to return <tt>true</tt>, but only after the corresponding CPU's
+ next scheduling-clock.
+<li> CPUs mentioned in the <tt>nohz_full</tt> kernel boot parameter
+ can run indefinitely in the kernel without scheduling-clock
+ interrupts, which defeats the above <tt>need_resched()</tt>
+ strategem.
+ RCU will therefore invoke <tt>resched_cpu()</tt> on any
+ <tt>nohz_full</tt> CPUs still holding out after
+ 109 milliseconds.
+<li> In kernels built with <tt>CONFIG_RCU_BOOST=y</tt>, if a given
+ task that has been preempted within an RCU read-side critical
+ section is holding out for more than 500 milliseconds,
+ RCU will resort to priority boosting.
+<li> If a CPU is still holding out 10 seconds into the grace
+ period, RCU will invoke <tt>resched_cpu()</tt> on it regardless
+ of its <tt>nohz_full</tt> state.
+</ol>
+
+<p>
+The above values are defaults for systems running with <tt>HZ=1000</tt>.
+They will vary as the value of <tt>HZ</tt> varies, and can also be
+changed using the relevant Kconfig options and kernel boot parameters.
+RCU currently does not do much sanity checking of these
+parameters, so please use caution when changing them.
+Note that these forward-progress measures are provided only for RCU,
+not for
+<a href="#Sleepable RCU">SRCU</a> or
+<a href="#Tasks RCU">Tasks RCU</a>.
+
+<p>
+RCU takes the following steps in <tt>call_rcu()</tt> to encourage timely
+invocation of callbacks when any given non-<tt>rcu_nocbs</tt> CPU has
+10,000 callbacks, or has 10,000 more callbacks than it had the last time
+encouragement was provided:
+
+<ol>
+<li> Starts a grace period, if one is not already in progress.
+<li> Forces immediate checking for quiescent states, rather than
+ waiting for three milliseconds to have elapsed since the
+ beginning of the grace period.
+<li> Immediately tags the CPU's callbacks with their grace period
+ completion numbers, rather than waiting for the <tt>RCU_SOFTIRQ</tt>
+ handler to get around to it.
+<li> Lifts callback-execution batch limits, which speeds up callback
+ invocation at the expense of degrading realtime response.
+</ol>
+
+<p>
+Again, these are default values when running at <tt>HZ=1000</tt>,
+and can be overridden.
+Again, these forward-progress measures are provided only for RCU,
+not for
+<a href="#Sleepable RCU">SRCU</a> or
+<a href="#Tasks RCU">Tasks RCU</a>.
+Even for RCU, callback-invocation forward progress for <tt>rcu_nocbs</tt>
+CPUs is much less well-developed, in part because workloads benefiting
+from <tt>rcu_nocbs</tt> CPUs tend to invoke <tt>call_rcu()</tt>
+relatively infrequently.
+If workloads emerge that need both <tt>rcu_nocbs</tt> CPUs and high
+<tt>call_rcu()</tt> invocation rates, then additional forward-progress
+work will be required.
+
<h3><a name="Composability">Composability</a></h3>
<p>
@@ -2080,6 +2129,8 @@
<li> <a href="#Hotplug CPU">Hotplug CPU</a>.
<li> <a href="#Scheduler and RCU">Scheduler and RCU</a>.
<li> <a href="#Tracing and RCU">Tracing and RCU</a>.
+<li> <a href="#Accesses to User Memory and RCU">
+Accesses to User Memory and RCU</a>.
<li> <a href="#Energy Efficiency">Energy Efficiency</a>.
<li> <a href="#Scheduling-Clock Interrupts and RCU">
Scheduling-Clock Interrupts and RCU</a>.
@@ -2165,14 +2216,9 @@
on what operations those callbacks could invoke.
<p>
-Perhaps surprisingly, <tt>synchronize_rcu()</tt>,
-<a href="#Bottom-Half Flavor"><tt>synchronize_rcu_bh()</tt></a>
-(<a href="#Bottom-Half Flavor">discussed below</a>),
-<a href="#Sched Flavor"><tt>synchronize_sched()</tt></a>,
+Perhaps surprisingly, <tt>synchronize_rcu()</tt> and
<tt>synchronize_rcu_expedited()</tt>,
-<tt>synchronize_rcu_bh_expedited()</tt>, and
-<tt>synchronize_sched_expedited()</tt>
-will all operate normally
+will operate normally
during very early boot, the reason being that there is only one CPU
and preemption is disabled.
This means that the call <tt>synchronize_rcu()</tt> (or friends)
@@ -2269,12 +2315,23 @@
The name notwithstanding, some Linux-kernel architectures
can have nested NMIs, which RCU must handle correctly.
Andy Lutomirski
-<a href="https://lkml.kernel.org/g/CALCETrXLq1y7e_dKFPgou-FKHB6Pu-r8+t-6Ds+8=va7anBWDA@mail.gmail.com">surprised me</a>
+<a href="https://lkml.kernel.org/r/CALCETrXLq1y7e_dKFPgou-FKHB6Pu-r8+t-6Ds+8=va7anBWDA@mail.gmail.com">surprised me</a>
with this requirement;
he also kindly surprised me with
-<a href="https://lkml.kernel.org/g/CALCETrXSY9JpW3uE6H8WYk81sg56qasA2aqmjMPsq5dOtzso=g@mail.gmail.com">an algorithm</a>
+<a href="https://lkml.kernel.org/r/CALCETrXSY9JpW3uE6H8WYk81sg56qasA2aqmjMPsq5dOtzso=g@mail.gmail.com">an algorithm</a>
that meets this requirement.
+<p>
+Furthermore, NMI handlers can be interrupted by what appear to RCU
+to be normal interrupts.
+One way that this can happen is for code that directly invokes
+<tt>rcu_irq_enter()</tt> and <tt>rcu_irq_exit()</tt> to be called
+from an NMI handler.
+This astonishing fact of life prompted the current code structure,
+which has <tt>rcu_irq_enter()</tt> invoking <tt>rcu_nmi_enter()</tt>
+and <tt>rcu_irq_exit()</tt> invoking <tt>rcu_nmi_exit()</tt>.
+And yes, I also learned of this requirement the hard way.
+
<h3><a name="Loadable Modules">Loadable Modules</a></h3>
<p>
@@ -2290,7 +2347,7 @@
<p>
Unfortunately, there is no way to cancel an RCU callback;
once you invoke <tt>call_rcu()</tt>, the callback function is
-going to eventually be invoked, unless the system goes down first.
+eventually going to be invoked, unless the system goes down first.
Because it is normally considered socially irresponsible to crash the system
in response to a module unload request, we need some other way
to deal with in-flight RCU callbacks.
@@ -2394,30 +2451,9 @@
<p>
RCU depends on the scheduler, and the scheduler uses RCU to
protect some of its data structures.
-This means the scheduler is forbidden from acquiring
-the runqueue locks and the priority-inheritance locks
-in the middle of an outermost RCU read-side critical section unless either
-(1) it releases them before exiting that same
-RCU read-side critical section, or
-(2) interrupts are disabled across
-that entire RCU read-side critical section.
-This same prohibition also applies (recursively!) to any lock that is acquired
-while holding any lock to which this prohibition applies.
-Adhering to this rule prevents preemptible RCU from invoking
-<tt>rcu_read_unlock_special()</tt> while either runqueue or
-priority-inheritance locks are held, thus avoiding deadlock.
-
-<p>
-Prior to v4.4, it was only necessary to disable preemption across
-RCU read-side critical sections that acquired scheduler locks.
-In v4.4, expedited grace periods started using IPIs, and these
-IPIs could force a <tt>rcu_read_unlock()</tt> to take the slowpath.
-Therefore, this expedited-grace-period change required disabling of
-interrupts, not just preemption.
-
-<p>
-For RCU's part, the preemptible-RCU <tt>rcu_read_unlock()</tt>
-implementation must be written carefully to avoid similar deadlocks.
+The preemptible-RCU <tt>rcu_read_unlock()</tt>
+implementation must therefore be written carefully to avoid deadlocks
+involving the scheduler's runqueue and priority-inheritance locks.
In particular, <tt>rcu_read_unlock()</tt> must tolerate an
interrupt where the interrupt handler invokes both
<tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>.
@@ -2426,7 +2462,7 @@
interrupt handler's use of RCU.
<p>
-This pair of mutual scheduler-RCU requirements came as a
+This scheduler-RCU requirement came as a
<a href="https://lwn.net/Articles/453002/">complete surprise</a>.
<p>
@@ -2437,15 +2473,48 @@
<tt>CONFIG_NO_HZ_FULL=y</tt>
<a href="http://www.rdrop.com/users/paulmck/scalability/paper/BareMetal.2015.01.15b.pdf">did come as a surprise [PDF]</a>.
RCU has made good progress towards meeting this requirement, even
-for context-switch-have <tt>CONFIG_NO_HZ_FULL=y</tt> workloads,
+for context-switch-heavy <tt>CONFIG_NO_HZ_FULL=y</tt> workloads,
but there is room for further improvement.
+<p>
+It is forbidden to hold any of scheduler's runqueue or priority-inheritance
+spinlocks across an <tt>rcu_read_unlock()</tt> unless interrupts have been
+disabled across the entire RCU read-side critical section, that is,
+up to and including the matching <tt>rcu_read_lock()</tt>.
+Violating this restriction can result in deadlocks involving these
+scheduler spinlocks.
+There was hope that this restriction might be lifted when interrupt-disabled
+calls to <tt>rcu_read_unlock()</tt> started deferring the reporting of
+the resulting RCU-preempt quiescent state until the end of the corresponding
+interrupts-disabled region.
+Unfortunately, timely reporting of the corresponding quiescent state
+to expedited grace periods requires a call to <tt>raise_softirq()</tt>,
+which can acquire these scheduler spinlocks.
+In addition, real-time systems using RCU priority boosting
+need this restriction to remain in effect because deferred
+quiescent-state reporting would also defer deboosting, which in turn
+would degrade real-time latencies.
+
+<p>
+In theory, if a given RCU read-side critical section could be
+guaranteed to be less than one second in duration, holding a scheduler
+spinlock across that critical section's <tt>rcu_read_unlock()</tt>
+would require only that preemption be disabled across the entire
+RCU read-side critical section, not interrupts.
+Unfortunately, given the possibility of vCPU preemption, long-running
+interrupts, and so on, it is not possible in practice to guarantee
+that a given RCU read-side critical section will complete in less than
+one second.
+Therefore, as noted above, if scheduler spinlocks are held across
+a given call to <tt>rcu_read_unlock()</tt>, interrupts must be
+disabled across the entire RCU read-side critical section.
+
<h3><a name="Tracing and RCU">Tracing and RCU</a></h3>
<p>
It is possible to use tracing on RCU code, but tracing itself
uses RCU.
-For this reason, <tt>rcu_dereference_raw_notrace()</tt>
+For this reason, <tt>rcu_dereference_raw_check()</tt>
is provided for use by tracing, which avoids the destructive
recursion that could otherwise ensue.
This API is also used by virtualization in some architectures,
@@ -2454,6 +2523,75 @@
The tracing folks both located the requirement and provided the
needed fix, so this surprise requirement was relatively painless.
+<h3><a name="Accesses to User Memory and RCU">
+Accesses to User Memory and RCU</a></h3>
+
+<p>
+The kernel needs to access user-space memory, for example, to access
+data referenced by system-call parameters.
+The <tt>get_user()</tt> macro does this job.
+
+<p>
+However, user-space memory might well be paged out, which means
+that <tt>get_user()</tt> might well page-fault and thus block while
+waiting for the resulting I/O to complete.
+It would be a very bad thing for the compiler to reorder
+a <tt>get_user()</tt> invocation into an RCU read-side critical
+section.
+For example, suppose that the source code looked like this:
+
+<blockquote>
+<pre>
+ 1 rcu_read_lock();
+ 2 p = rcu_dereference(gp);
+ 3 v = p->value;
+ 4 rcu_read_unlock();
+ 5 get_user(user_v, user_p);
+ 6 do_something_with(v, user_v);
+</pre>
+</blockquote>
+
+<p>
+The compiler must not be permitted to transform this source code into
+the following:
+
+<blockquote>
+<pre>
+ 1 rcu_read_lock();
+ 2 p = rcu_dereference(gp);
+ 3 get_user(user_v, user_p); // BUG: POSSIBLE PAGE FAULT!!!
+ 4 v = p->value;
+ 5 rcu_read_unlock();
+ 6 do_something_with(v, user_v);
+</pre>
+</blockquote>
+
+<p>
+If the compiler did make this transformation in a
+<tt>CONFIG_PREEMPT=n</tt> kernel build, and if <tt>get_user()</tt> did
+page fault, the result would be a quiescent state in the middle
+of an RCU read-side critical section.
+This misplaced quiescent state could result in line 4 being
+a use-after-free access, which could be bad for your kernel's
+actuarial statistics.
+Similar examples can be constructed with the call to <tt>get_user()</tt>
+preceding the <tt>rcu_read_lock()</tt>.
+
+<p>
+Unfortunately, <tt>get_user()</tt> doesn't have any particular
+ordering properties, and in some architectures the underlying <tt>asm</tt>
+isn't even marked <tt>volatile</tt>.
+And even if it was marked <tt>volatile</tt>, the above access to
+<tt>p->value</tt> is not volatile, so the compiler would not have any
+reason to keep those two accesses in order.
+
+<p>
+Therefore, the Linux-kernel definitions of <tt>rcu_read_lock()</tt>
+and <tt>rcu_read_unlock()</tt> must act as compiler barriers,
+at least for outermost instances of <tt>rcu_read_lock()</tt> and
+<tt>rcu_read_unlock()</tt> within a nested set of RCU read-side critical
+sections.
+
<h3><a name="Energy Efficiency">Energy Efficiency</a></h3>
<p>
@@ -2850,15 +2988,22 @@
described in a separate section.
<ol>
-<li> <a href="#Bottom-Half Flavor">Bottom-Half Flavor</a>
-<li> <a href="#Sched Flavor">Sched Flavor</a>
+<li> <a href="#Bottom-Half Flavor">Bottom-Half Flavor (Historical)</a>
+<li> <a href="#Sched Flavor">Sched Flavor (Historical)</a>
<li> <a href="#Sleepable RCU">Sleepable RCU</a>
<li> <a href="#Tasks RCU">Tasks RCU</a>
-<li> <a href="#Waiting for Multiple Grace Periods">
- Waiting for Multiple Grace Periods</a>
</ol>
-<h3><a name="Bottom-Half Flavor">Bottom-Half Flavor</a></h3>
+<h3><a name="Bottom-Half Flavor">Bottom-Half Flavor (Historical)</a></h3>
+
+<p>
+The RCU-bh flavor of RCU has since been expressed in terms of
+the other RCU flavors as part of a consolidation of the three
+flavors into a single flavor.
+The read-side API remains, and continues to disable softirq and to
+be accounted for by lockdep.
+Much of the material in this section is therefore strictly historical
+in nature.
<p>
The softirq-disable (AKA “bottom-half”,
@@ -2918,8 +3063,20 @@
<tt>call_rcu_bh()</tt>,
<tt>rcu_barrier_bh()</tt>, and
<tt>rcu_read_lock_bh_held()</tt>.
+However, the update-side APIs are now simple wrappers for other RCU
+flavors, namely RCU-sched in CONFIG_PREEMPT=n kernels and RCU-preempt
+otherwise.
-<h3><a name="Sched Flavor">Sched Flavor</a></h3>
+<h3><a name="Sched Flavor">Sched Flavor (Historical)</a></h3>
+
+<p>
+The RCU-sched flavor of RCU has since been expressed in terms of
+the other RCU flavors as part of a consolidation of the three
+flavors into a single flavor.
+The read-side API remains, and continues to disable preemption and to
+be accounted for by lockdep.
+Much of the material in this section is therefore strictly historical
+in nature.
<p>
Before preemptible RCU, waiting for an RCU grace period had the
@@ -3013,7 +3170,7 @@
sections, then that domain's grace periods will also be blocked forever.
Of course, one good way to block forever is to deadlock, which can
happen if any operation in a given domain's SRCU read-side critical
-section can block waiting, either directly or indirectly, for that domain's
+section can wait, either directly or indirectly, for that domain's
grace period to elapse.
For example, this results in a self-deadlock:
@@ -3053,12 +3210,18 @@
guarantees a full memory barrier.
<p>
-Also unlike other RCU flavors, SRCU's callbacks-wait function
-<tt>srcu_barrier()</tt> may be invoked from CPU-hotplug notifiers,
-though this is not necessarily a good idea.
-The reason that this is possible is that SRCU is insensitive
-to whether or not a CPU is online, which means that <tt>srcu_barrier()</tt>
-need not exclude CPU-hotplug operations.
+Also unlike other RCU flavors, <tt>synchronize_srcu()</tt> may <b>not</b>
+be invoked from CPU-hotplug notifiers, due to the fact that SRCU grace
+periods make use of timers and the possibility of timers being temporarily
+“stranded” on the outgoing CPU.
+This stranding of timers means that timers posted to the outgoing CPU
+will not fire until late in the CPU-hotplug process.
+The problem is that if a notifier is waiting on an SRCU grace period,
+that grace period is waiting on a timer, and that timer is stranded on the
+outgoing CPU, then the notifier will never be awakened, in other words,
+deadlock has occurred.
+This same situation of course also prohibits <tt>srcu_barrier()</tt>
+from being invoked from CPU-hotplug notifiers.
<p>
SRCU also differs from other RCU flavors in that SRCU's expedited and
@@ -3139,94 +3302,14 @@
<tt>call_rcu_tasks()</tt>,
<tt>synchronize_rcu_tasks()</tt>, and
<tt>rcu_barrier_tasks()</tt>.
-
-<h3><a name="Waiting for Multiple Grace Periods">
-Waiting for Multiple Grace Periods</a></h3>
-
-<p>
-Perhaps you have an RCU protected data structure that is accessed from
-RCU read-side critical sections, from softirq handlers, and from
-hardware interrupt handlers.
-That is three flavors of RCU, the normal flavor, the bottom-half flavor,
-and the sched flavor.
-How to wait for a compound grace period?
-
-<p>
-The best approach is usually to “just say no!” and
-insert <tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>
-around each RCU read-side critical section, regardless of what
-environment it happens to be in.
-But suppose that some of the RCU read-side critical sections are
-on extremely hot code paths, and that use of <tt>CONFIG_PREEMPT=n</tt>
-is not a viable option, so that <tt>rcu_read_lock()</tt> and
-<tt>rcu_read_unlock()</tt> are not free.
-What then?
-
-<p>
-You <i>could</i> wait on all three grace periods in succession, as follows:
-
-<blockquote>
-<pre>
- 1 synchronize_rcu();
- 2 synchronize_rcu_bh();
- 3 synchronize_sched();
-</pre>
-</blockquote>
-
-<p>
-This works, but triples the update-side latency penalty.
-In cases where this is not acceptable, <tt>synchronize_rcu_mult()</tt>
-may be used to wait on all three flavors of grace period concurrently:
-
-<blockquote>
-<pre>
- 1 synchronize_rcu_mult(call_rcu, call_rcu_bh, call_rcu_sched);
-</pre>
-</blockquote>
-
-<p>
-But what if it is necessary to also wait on SRCU?
-This can be done as follows:
-
-<blockquote>
-<pre>
- 1 static void call_my_srcu(struct rcu_head *head,
- 2 void (*func)(struct rcu_head *head))
- 3 {
- 4 call_srcu(&my_srcu, head, func);
- 5 }
- 6
- 7 synchronize_rcu_mult(call_rcu, call_rcu_bh, call_rcu_sched, call_my_srcu);
-</pre>
-</blockquote>
-
-<p>
-If you needed to wait on multiple different flavors of SRCU
-(but why???), you would need to create a wrapper function resembling
-<tt>call_my_srcu()</tt> for each SRCU flavor.
-
-<table>
-<tr><th> </th></tr>
-<tr><th align="left">Quick Quiz:</th></tr>
-<tr><td>
- But what if I need to wait for multiple RCU flavors, but I also need
- the grace periods to be expedited?
-</td></tr>
-<tr><th align="left">Answer:</th></tr>
-<tr><td bgcolor="#ffffff"><font color="ffffff">
- If you are using expedited grace periods, there should be less penalty
- for waiting on them in succession.
- But if that is nevertheless a problem, you can use workqueues
- or multiple kthreads to wait on the various expedited grace
- periods concurrently.
-</font></td></tr>
-<tr><td> </td></tr>
-</table>
-
-<p>
-Again, it is usually better to adjust the RCU read-side critical sections
-to use a single flavor of RCU, but when this is not feasible, you can use
-<tt>synchronize_rcu_mult()</tt>.
+In <tt>CONFIG_PREEMPT=n</tt> kernels, trampolines cannot be preempted,
+so these APIs map to
+<tt>call_rcu()</tt>,
+<tt>synchronize_rcu()</tt>, and
+<tt>rcu_barrier()</tt>, respectively.
+In <tt>CONFIG_PREEMPT=y</tt> kernels, trampolines can be preempted,
+and these three APIs are therefore implemented by separate functions
+that check for voluntary context switches.
<h2><a name="Possible Future Changes">Possible Future Changes</a></h2>
@@ -3238,12 +3321,6 @@
latency.
<p>
-Expedited grace periods scan the CPUs, so their latency and overhead
-increases with increasing numbers of CPUs.
-If this becomes a serious problem on large systems, it will be necessary
-to do some redesign to avoid this scalability problem.
-
-<p>
RCU disables CPU hotplug in a few places, perhaps most notably in the
<tt>rcu_barrier()</tt> operations.
If there is a strong reason to use <tt>rcu_barrier()</tt> in CPU-hotplug
@@ -3288,11 +3365,6 @@
alternatives.
<p>
-There is an embarrassingly large number of flavors of RCU, and this
-number has been increasing over time.
-Perhaps it will be possible to combine some at some future date.
-
-<p>
RCU's various kthreads are reasonably recent additions.
It is quite likely that adjustments will be required to more gracefully
handle extreme loads.
@@ -3303,6 +3375,11 @@
originating <tt>call_rcu()</tt> instance, though probably not
in production kernels.
+<p>
+Additional work may be required to provide reasonable forward-progress
+guarantees under heavy load for grace periods and for callback
+invocation.
+
<h2><a name="Summary">Summary</a></h2>
<p>
diff --git a/Documentation/RCU/NMI-RCU.txt b/Documentation/RCU/NMI-RCU.txt
index 687777f..881353f 100644
--- a/Documentation/RCU/NMI-RCU.txt
+++ b/Documentation/RCU/NMI-RCU.txt
@@ -81,18 +81,19 @@
up any data structures used by the old NMI handler until execution
of it completes on all other CPUs.
-One way to accomplish this is via synchronize_sched(), perhaps as
+One way to accomplish this is via synchronize_rcu(), perhaps as
follows:
unset_nmi_callback();
- synchronize_sched();
+ synchronize_rcu();
kfree(my_nmi_data);
-This works because synchronize_sched() blocks until all CPUs complete
-any preemption-disabled segments of code that they were executing.
-Since NMI handlers disable preemption, synchronize_sched() is guaranteed
+This works because (as of v4.20) synchronize_rcu() blocks until all
+CPUs complete any preemption-disabled segments of code that they were
+executing.
+Since NMI handlers disable preemption, synchronize_rcu() is guaranteed
not to return until all ongoing NMI handlers exit. It is therefore safe
-to free up the handler's data as soon as synchronize_sched() returns.
+to free up the handler's data as soon as synchronize_rcu() returns.
Important note: for this to work, the architecture in question must
invoke nmi_enter() and nmi_exit() on NMI entry and exit, respectively.
diff --git a/Documentation/RCU/UP.txt b/Documentation/RCU/UP.rst
similarity index 77%
rename from Documentation/RCU/UP.txt
rename to Documentation/RCU/UP.rst
index 90ec534..e26dda2 100644
--- a/Documentation/RCU/UP.txt
+++ b/Documentation/RCU/UP.rst
@@ -1,17 +1,19 @@
-RCU on Uniprocessor Systems
+.. _up_doc:
+RCU on Uniprocessor Systems
+===========================
A common misconception is that, on UP systems, the call_rcu() primitive
may immediately invoke its function. The basis of this misconception
is that since there is only one CPU, it should not be necessary to
wait for anything else to get done, since there are no other CPUs for
-anything else to be happening on. Although this approach will -sort- -of-
+anything else to be happening on. Although this approach will *sort of*
work a surprising amount of the time, it is a very bad idea in general.
This document presents three examples that demonstrate exactly how bad
an idea this is.
-
Example 1: softirq Suicide
+--------------------------
Suppose that an RCU-based algorithm scans a linked list containing
elements A, B, and C in process context, and can delete elements from
@@ -28,8 +30,8 @@
This same problem can occur if call_rcu() is invoked from a hardware
interrupt handler.
-
Example 2: Function-Call Fatality
+---------------------------------
Of course, one could avert the suicide described in the preceding example
by having call_rcu() directly invoke its arguments only if it was called
@@ -46,11 +48,13 @@
underlying RCU, namely that call_rcu() defers invoking its arguments until
all RCU read-side critical sections currently executing have completed.
-Quick Quiz #1: why is it -not- legal to invoke synchronize_rcu() in
- this case?
+Quick Quiz #1:
+ Why is it *not* legal to invoke synchronize_rcu() in this case?
+:ref:`Answers to Quick Quiz <answer_quick_quiz_up>`
Example 3: Death by Deadlock
+----------------------------
Suppose that call_rcu() is invoked while holding a lock, and that the
callback function must acquire this same lock. In this case, if
@@ -76,27 +80,30 @@
If call_rcu() directly invokes the callback, painful locking restrictions
or API changes would be required.
-Quick Quiz #2: What locking restriction must RCU callbacks respect?
+Quick Quiz #2:
+ What locking restriction must RCU callbacks respect?
+:ref:`Answers to Quick Quiz <answer_quick_quiz_up>`
Summary
+-------
Permitting call_rcu() to immediately invoke its arguments breaks RCU,
even on a UP system. So do not do it! Even on a UP system, the RCU
-infrastructure -must- respect grace periods, and -must- invoke callbacks
+infrastructure *must* respect grace periods, and *must* invoke callbacks
from a known environment in which no locks are held.
-It -is- safe for synchronize_sched() and synchronize_rcu_bh() to return
-immediately on an UP system. It is also safe for synchronize_rcu()
-to return immediately on UP systems, except when running preemptable
-RCU.
+Note that it *is* safe for synchronize_rcu() to return immediately on
+UP systems, including PREEMPT SMP builds running on UP systems.
-Quick Quiz #3: Why can't synchronize_rcu() return immediately on
- UP systems running preemptable RCU?
+Quick Quiz #3:
+ Why can't synchronize_rcu() return immediately on UP systems running
+ preemptable RCU?
+.. _answer_quick_quiz_up:
Answer to Quick Quiz #1:
- Why is it -not- legal to invoke synchronize_rcu() in this case?
+ Why is it *not* legal to invoke synchronize_rcu() in this case?
Because the calling function is scanning an RCU-protected linked
list, and is therefore within an RCU read-side critical section.
@@ -106,12 +113,13 @@
Answer to Quick Quiz #2:
What locking restriction must RCU callbacks respect?
- Any lock that is acquired within an RCU callback must be
- acquired elsewhere using an _irq variant of the spinlock
- primitive. For example, if "mylock" is acquired by an
- RCU callback, then a process-context acquisition of this
- lock must use something like spin_lock_irqsave() to
- acquire the lock.
+ Any lock that is acquired within an RCU callback must be acquired
+ elsewhere using an _bh variant of the spinlock primitive.
+ For example, if "mylock" is acquired by an RCU callback, then
+ a process-context acquisition of this lock must use something
+ like spin_lock_bh() to acquire the lock. Please note that
+ it is also OK to use _irq variants of spinlocks, for example,
+ spin_lock_irqsave().
If the process-context code were to simply use spin_lock(),
then, since RCU callbacks can be invoked from softirq context,
@@ -121,7 +129,7 @@
This restriction might seem gratuitous, since very few RCU
callbacks acquire locks directly. However, a great many RCU
- callbacks do acquire locks -indirectly-, for example, via
+ callbacks do acquire locks *indirectly*, for example, via
the kfree() primitive.
Answer to Quick Quiz #3:
diff --git a/Documentation/RCU/checklist.txt b/Documentation/RCU/checklist.txt
index 4974771..e98ff26 100644
--- a/Documentation/RCU/checklist.txt
+++ b/Documentation/RCU/checklist.txt
@@ -63,7 +63,7 @@
pointer must be covered by rcu_read_lock(), rcu_read_lock_bh(),
rcu_read_lock_sched(), or by the appropriate update-side lock.
Disabling of preemption can serve as rcu_read_lock_sched(), but
- is less readable.
+ is less readable and prevents lockdep from detecting locking issues.
Letting RCU-protected pointers "leak" out of an RCU read-side
critical section is every bid as bad as letting them leak out
@@ -182,16 +182,13 @@
when publicizing a pointer to a structure that can
be traversed by an RCU read-side critical section.
-5. If call_rcu(), or a related primitive such as call_rcu_bh(),
- call_rcu_sched(), or call_srcu() is used, the callback function
- will be called from softirq context. In particular, it cannot
- block.
+5. If call_rcu() or call_srcu() is used, the callback function will
+ be called from softirq context. In particular, it cannot block.
-6. Since synchronize_rcu() can block, it cannot be called from
- any sort of irq context. The same rule applies for
- synchronize_rcu_bh(), synchronize_sched(), synchronize_srcu(),
- synchronize_rcu_expedited(), synchronize_rcu_bh_expedited(),
- synchronize_sched_expedite(), and synchronize_srcu_expedited().
+6. Since synchronize_rcu() can block, it cannot be called
+ from any sort of irq context. The same rule applies
+ for synchronize_srcu(), synchronize_rcu_expedited(), and
+ synchronize_srcu_expedited().
The expedited forms of these primitives have the same semantics
as the non-expedited forms, but expediting is both expensive and
@@ -212,20 +209,20 @@
of the system, especially to real-time workloads running on
the rest of the system.
-7. If the updater uses call_rcu() or synchronize_rcu(), then the
- corresponding readers must use rcu_read_lock() and
- rcu_read_unlock(). If the updater uses call_rcu_bh() or
- synchronize_rcu_bh(), then the corresponding readers must
- use rcu_read_lock_bh() and rcu_read_unlock_bh(). If the
- updater uses call_rcu_sched() or synchronize_sched(), then
- the corresponding readers must disable preemption, possibly
- by calling rcu_read_lock_sched() and rcu_read_unlock_sched().
- If the updater uses synchronize_srcu() or call_srcu(), then
- the corresponding readers must use srcu_read_lock() and
+7. As of v4.20, a given kernel implements only one RCU flavor,
+ which is RCU-sched for PREEMPT=n and RCU-preempt for PREEMPT=y.
+ If the updater uses call_rcu() or synchronize_rcu(),
+ then the corresponding readers my use rcu_read_lock() and
+ rcu_read_unlock(), rcu_read_lock_bh() and rcu_read_unlock_bh(),
+ or any pair of primitives that disables and re-enables preemption,
+ for example, rcu_read_lock_sched() and rcu_read_unlock_sched().
+ If the updater uses synchronize_srcu() or call_srcu(),
+ then the corresponding readers must use srcu_read_lock() and
srcu_read_unlock(), and with the same srcu_struct. The rules for
the expedited primitives are the same as for their non-expedited
counterparts. Mixing things up will result in confusion and
- broken kernels.
+ broken kernels, and has even resulted in an exploitable security
+ issue.
One exception to this rule: rcu_read_lock() and rcu_read_unlock()
may be substituted for rcu_read_lock_bh() and rcu_read_unlock_bh()
@@ -285,15 +282,10 @@
here is that superuser already has lots of ways to crash
the machine.
- d. Use call_rcu_bh() rather than call_rcu(), in order to take
- advantage of call_rcu_bh()'s faster grace periods. (This
- is only a partial solution, though.)
-
- e. Periodically invoke synchronize_rcu(), permitting a limited
+ d. Periodically invoke synchronize_rcu(), permitting a limited
number of updates per grace period.
- The same cautions apply to call_rcu_bh(), call_rcu_sched(),
- call_srcu(), and kfree_rcu().
+ The same cautions apply to call_srcu() and kfree_rcu().
Note that although these primitives do take action to avoid memory
exhaustion when any given CPU has too many callbacks, a determined
@@ -324,37 +316,14 @@
will break Alpha, cause aggressive compilers to generate bad code,
and confuse people trying to read your code.
-11. Note that synchronize_rcu() -only- guarantees to wait until
- all currently executing rcu_read_lock()-protected RCU read-side
- critical sections complete. It does -not- necessarily guarantee
- that all currently running interrupts, NMIs, preempt_disable()
- code, or idle loops will complete. Therefore, if your
- read-side critical sections are protected by something other
- than rcu_read_lock(), do -not- use synchronize_rcu().
-
- Similarly, disabling preemption is not an acceptable substitute
- for rcu_read_lock(). Code that attempts to use preemption
- disabling where it should be using rcu_read_lock() will break
- in CONFIG_PREEMPT=y kernel builds.
-
- If you want to wait for interrupt handlers, NMI handlers, and
- code under the influence of preempt_disable(), you instead
- need to use synchronize_irq() or synchronize_sched().
-
- This same limitation also applies to synchronize_rcu_bh()
- and synchronize_srcu(), as well as to the asynchronous and
- expedited forms of the three primitives, namely call_rcu(),
- call_rcu_bh(), call_srcu(), synchronize_rcu_expedited(),
- synchronize_rcu_bh_expedited(), and synchronize_srcu_expedited().
-
-12. Any lock acquired by an RCU callback must be acquired elsewhere
+11. Any lock acquired by an RCU callback must be acquired elsewhere
with softirq disabled, e.g., via spin_lock_irqsave(),
- spin_lock_bh(), etc. Failing to disable irq on a given
+ spin_lock_bh(), etc. Failing to disable softirq on a given
acquisition of that lock will result in deadlock as soon as
the RCU softirq handler happens to run your RCU callback while
interrupting that acquisition's critical section.
-13. RCU callbacks can be and are executed in parallel. In many cases,
+12. RCU callbacks can be and are executed in parallel. In many cases,
the callback code simply wrappers around kfree(), so that this
is not an issue (or, more accurately, to the extent that it is
an issue, the memory-allocator locking handles it). However,
@@ -362,15 +331,18 @@
must use whatever locking or other synchronization is required
to safely access and/or modify that data structure.
- RCU callbacks are -usually- executed on the same CPU that executed
- the corresponding call_rcu(), call_rcu_bh(), or call_rcu_sched(),
- but are by -no- means guaranteed to be. For example, if a given
- CPU goes offline while having an RCU callback pending, then that
- RCU callback will execute on some surviving CPU. (If this was
- not the case, a self-spawning RCU callback would prevent the
- victim CPU from ever going offline.)
+ Do not assume that RCU callbacks will be executed on the same
+ CPU that executed the corresponding call_rcu() or call_srcu().
+ For example, if a given CPU goes offline while having an RCU
+ callback pending, then that RCU callback will execute on some
+ surviving CPU. (If this was not the case, a self-spawning RCU
+ callback would prevent the victim CPU from ever going offline.)
+ Furthermore, CPUs designated by rcu_nocbs= might well -always-
+ have their RCU callbacks executed on some other CPUs, in fact,
+ for some real-time workloads, this is the whole point of using
+ the rcu_nocbs= kernel boot parameter.
-14. Unlike other forms of RCU, it -is- permissible to block in an
+13. Unlike other forms of RCU, it -is- permissible to block in an
SRCU read-side critical section (demarked by srcu_read_lock()
and srcu_read_unlock()), hence the "SRCU": "sleepable RCU".
Please note that if you don't need to sleep in read-side critical
@@ -408,13 +380,13 @@
SRCU's expedited primitive (synchronize_srcu_expedited())
never sends IPIs to other CPUs, so it is easier on
- real-time workloads than is synchronize_rcu_expedited(),
- synchronize_rcu_bh_expedited() or synchronize_sched_expedited().
+ real-time workloads than is synchronize_rcu_expedited().
- Note that rcu_dereference() and rcu_assign_pointer() relate to
- SRCU just as they do to other forms of RCU.
+ Note that rcu_assign_pointer() relates to SRCU just as it does to
+ other forms of RCU, but instead of rcu_dereference() you should
+ use srcu_dereference() in order to avoid lockdep splats.
-15. The whole point of call_rcu(), synchronize_rcu(), and friends
+14. The whole point of call_rcu(), synchronize_rcu(), and friends
is to wait until all pre-existing readers have finished before
carrying out some otherwise-destructive operation. It is
therefore critically important to -first- remove any path
@@ -426,13 +398,16 @@
is the caller's responsibility to guarantee that any subsequent
readers will execute safely.
-16. The various RCU read-side primitives do -not- necessarily contain
+15. The various RCU read-side primitives do -not- necessarily contain
memory barriers. You should therefore plan for the CPU
and the compiler to freely reorder code into and out of RCU
read-side critical sections. It is the responsibility of the
RCU update-side primitives to deal with this.
-17. Use CONFIG_PROVE_LOCKING, CONFIG_DEBUG_OBJECTS_RCU_HEAD, and the
+ For SRCU readers, you can use smp_mb__after_srcu_read_unlock()
+ immediately after an srcu_read_unlock() to get a full barrier.
+
+16. Use CONFIG_PROVE_LOCKING, CONFIG_DEBUG_OBJECTS_RCU_HEAD, and the
__rcu sparse checks to validate your RCU code. These can help
find problems as follows:
@@ -455,22 +430,19 @@
These debugging aids can help you find problems that are
otherwise extremely difficult to spot.
-18. If you register a callback using call_rcu(), call_rcu_bh(),
- call_rcu_sched(), or call_srcu(), and pass in a function defined
- within a loadable module, then it in necessary to wait for
- all pending callbacks to be invoked after the last invocation
- and before unloading that module. Note that it is absolutely
- -not- sufficient to wait for a grace period! The current (say)
- synchronize_rcu() implementation waits only for all previous
- callbacks registered on the CPU that synchronize_rcu() is running
- on, but it is -not- guaranteed to wait for callbacks registered
- on other CPUs.
+17. If you register a callback using call_rcu() or call_srcu(), and
+ pass in a function defined within a loadable module, then it in
+ necessary to wait for all pending callbacks to be invoked after
+ the last invocation and before unloading that module. Note that
+ it is absolutely -not- sufficient to wait for a grace period!
+ The current (say) synchronize_rcu() implementation is -not-
+ guaranteed to wait for callbacks registered on other CPUs.
+ Or even on the current CPU if that CPU recently went offline
+ and came back online.
You instead need to use one of the barrier functions:
o call_rcu() -> rcu_barrier()
- o call_rcu_bh() -> rcu_barrier_bh()
- o call_rcu_sched() -> rcu_barrier_sched()
o call_srcu() -> srcu_barrier()
However, these barrier functions are absolutely -not- guaranteed
diff --git a/Documentation/RCU/index.rst b/Documentation/RCU/index.rst
new file mode 100644
index 0000000..340a972
--- /dev/null
+++ b/Documentation/RCU/index.rst
@@ -0,0 +1,19 @@
+.. _rcu_concepts:
+
+============
+RCU concepts
+============
+
+.. toctree::
+ :maxdepth: 1
+
+ rcu
+ listRCU
+ UP
+
+.. only:: subproject and html
+
+ Indices
+ =======
+
+ * :ref:`genindex`
diff --git a/Documentation/RCU/listRCU.txt b/Documentation/RCU/listRCU.rst
similarity index 92%
rename from Documentation/RCU/listRCU.txt
rename to Documentation/RCU/listRCU.rst
index adb5a37..7956ff3 100644
--- a/Documentation/RCU/listRCU.txt
+++ b/Documentation/RCU/listRCU.rst
@@ -1,5 +1,7 @@
-Using RCU to Protect Read-Mostly Linked Lists
+.. _list_rcu_doc:
+Using RCU to Protect Read-Mostly Linked Lists
+=============================================
One of the best applications of RCU is to protect read-mostly linked lists
("struct list_head" in list.h). One big advantage of this approach
@@ -7,8 +9,8 @@
the list macros. This document describes several applications of RCU,
with the best fits first.
-
Example 1: Read-Side Action Taken Outside of Lock, No In-Place Updates
+----------------------------------------------------------------------
The best applications are cases where, if reader-writer locking were
used, the read-side lock would be dropped before taking any action
@@ -24,7 +26,7 @@
A straightforward example of this use of RCU may be found in the
system-call auditing support. For example, a reader-writer locked
-implementation of audit_filter_task() might be as follows:
+implementation of audit_filter_task() might be as follows::
static enum audit_state audit_filter_task(struct task_struct *tsk)
{
@@ -48,7 +50,7 @@
on, the list may well have been modified. This makes sense, since if
you are turning auditing off, it is OK to audit a few extra system calls.
-This means that RCU can be easily applied to the read side, as follows:
+This means that RCU can be easily applied to the read side, as follows::
static enum audit_state audit_filter_task(struct task_struct *tsk)
{
@@ -73,7 +75,7 @@
insert the read-side memory barriers that are required on DEC Alpha CPUs.
The changes to the update side are also straightforward. A reader-writer
-lock might be used as follows for deletion and insertion:
+lock might be used as follows for deletion and insertion::
static inline int audit_del_rule(struct audit_rule *rule,
struct list_head *list)
@@ -106,7 +108,7 @@
return 0;
}
-Following are the RCU equivalents for these two functions:
+Following are the RCU equivalents for these two functions::
static inline int audit_del_rule(struct audit_rule *rule,
struct list_head *list)
@@ -154,13 +156,13 @@
So, when readers can tolerate stale data and when entries are either added
or deleted, without in-place modification, it is very easy to use RCU!
-
Example 2: Handling In-Place Updates
+------------------------------------
The system-call auditing code does not update auditing rules in place.
However, if it did, reader-writer-locked code to do so might look as
follows (presumably, the field_count is only permitted to decrease,
-otherwise, the added fields would need to be filled in):
+otherwise, the added fields would need to be filled in)::
static inline int audit_upd_rule(struct audit_rule *rule,
struct list_head *list,
@@ -187,7 +189,7 @@
The RCU version creates a copy, updates the copy, then replaces the old
entry with the newly updated entry. This sequence of actions, allowing
concurrent reads while doing a copy to perform an update, is what gives
-RCU ("read-copy update") its name. The RCU code is as follows:
+RCU ("read-copy update") its name. The RCU code is as follows::
static inline int audit_upd_rule(struct audit_rule *rule,
struct list_head *list,
@@ -216,8 +218,8 @@
Again, this assumes that the caller holds audit_netlink_sem. Normally,
the reader-writer lock would become a spinlock in this sort of code.
-
Example 3: Eliminating Stale Data
+---------------------------------
The auditing examples above tolerate stale data, as do most algorithms
that are tracking external state. Because there is a delay from the
@@ -231,13 +233,16 @@
entry does not exist. For this to be helpful, the search function must
return holding the per-entry spinlock, as ipc_lock() does in fact do.
-Quick Quiz: Why does the search function need to return holding the
- per-entry lock for this deleted-flag technique to be helpful?
+Quick Quiz:
+ Why does the search function need to return holding the per-entry lock for
+ this deleted-flag technique to be helpful?
+
+:ref:`Answer to Quick Quiz <answer_quick_quiz_list>`
If the system-call audit module were to ever need to reject stale data,
one way to accomplish this would be to add a "deleted" flag and a "lock"
spinlock to the audit_entry structure, and modify audit_filter_task()
-as follows:
+as follows::
static enum audit_state audit_filter_task(struct task_struct *tsk)
{
@@ -268,7 +273,7 @@
that the list_add_rcu() was really executed before the list_del_rcu().
The audit_del_rule() function would need to set the "deleted"
-flag under the spinlock as follows:
+flag under the spinlock as follows::
static inline int audit_del_rule(struct audit_rule *rule,
struct list_head *list)
@@ -290,8 +295,8 @@
return -EFAULT; /* No matching rule */
}
-
Summary
+-------
Read-mostly list-based data structures that can tolerate stale data are
the most amenable to use of RCU. The simplest case is where entries are
@@ -302,8 +307,9 @@
in conjunction with a per-entry spinlock in order to allow the search
function to reject newly deleted data.
+.. _answer_quick_quiz_list:
-Answer to Quick Quiz
+Answer to Quick Quiz:
Why does the search function need to return holding the per-entry
lock for this deleted-flag technique to be helpful?
diff --git a/Documentation/RCU/lockdep-splat.txt b/Documentation/RCU/lockdep-splat.txt
index 238e9f6..9c01597 100644
--- a/Documentation/RCU/lockdep-splat.txt
+++ b/Documentation/RCU/lockdep-splat.txt
@@ -14,9 +14,9 @@
So let's look at an example RCU lockdep splat from 3.0-rc5, one that
has long since been fixed:
-===============================
-[ INFO: suspicious RCU usage. ]
--------------------------------
+=============================
+WARNING: suspicious RCU usage
+-----------------------------
block/cfq-iosched.c:2776 suspicious rcu_dereference_protected() usage!
other info that might help us debug this:
@@ -24,11 +24,11 @@
rcu_scheduler_active = 1, debug_locks = 0
3 locks held by scsi_scan_6/1552:
- #0: (&shost->scan_mutex){+.+.+.}, at: [<ffffffff8145efca>]
+ #0: (&shost->scan_mutex){+.+.}, at: [<ffffffff8145efca>]
scsi_scan_host_selected+0x5a/0x150
- #1: (&eq->sysfs_lock){+.+...}, at: [<ffffffff812a5032>]
+ #1: (&eq->sysfs_lock){+.+.}, at: [<ffffffff812a5032>]
elevator_exit+0x22/0x60
- #2: (&(&q->__queue_lock)->rlock){-.-...}, at: [<ffffffff812b6233>]
+ #2: (&(&q->__queue_lock)->rlock){-.-.}, at: [<ffffffff812b6233>]
cfq_exit_queue+0x43/0x190
stack backtrace:
diff --git a/Documentation/RCU/rcu.rst b/Documentation/RCU/rcu.rst
new file mode 100644
index 0000000..8dfb437
--- /dev/null
+++ b/Documentation/RCU/rcu.rst
@@ -0,0 +1,92 @@
+.. _rcu_doc:
+
+RCU Concepts
+============
+
+The basic idea behind RCU (read-copy update) is to split destructive
+operations into two parts, one that prevents anyone from seeing the data
+item being destroyed, and one that actually carries out the destruction.
+A "grace period" must elapse between the two parts, and this grace period
+must be long enough that any readers accessing the item being deleted have
+since dropped their references. For example, an RCU-protected deletion
+from a linked list would first remove the item from the list, wait for
+a grace period to elapse, then free the element. See the
+Documentation/RCU/listRCU.rst file for more information on using RCU with
+linked lists.
+
+Frequently Asked Questions
+--------------------------
+
+- Why would anyone want to use RCU?
+
+ The advantage of RCU's two-part approach is that RCU readers need
+ not acquire any locks, perform any atomic instructions, write to
+ shared memory, or (on CPUs other than Alpha) execute any memory
+ barriers. The fact that these operations are quite expensive
+ on modern CPUs is what gives RCU its performance advantages
+ in read-mostly situations. The fact that RCU readers need not
+ acquire locks can also greatly simplify deadlock-avoidance code.
+
+- How can the updater tell when a grace period has completed
+ if the RCU readers give no indication when they are done?
+
+ Just as with spinlocks, RCU readers are not permitted to
+ block, switch to user-mode execution, or enter the idle loop.
+ Therefore, as soon as a CPU is seen passing through any of these
+ three states, we know that that CPU has exited any previous RCU
+ read-side critical sections. So, if we remove an item from a
+ linked list, and then wait until all CPUs have switched context,
+ executed in user mode, or executed in the idle loop, we can
+ safely free up that item.
+
+ Preemptible variants of RCU (CONFIG_PREEMPT_RCU) get the
+ same effect, but require that the readers manipulate CPU-local
+ counters. These counters allow limited types of blocking within
+ RCU read-side critical sections. SRCU also uses CPU-local
+ counters, and permits general blocking within RCU read-side
+ critical sections. These variants of RCU detect grace periods
+ by sampling these counters.
+
+- If I am running on a uniprocessor kernel, which can only do one
+ thing at a time, why should I wait for a grace period?
+
+ See the Documentation/RCU/UP.rst file for more information.
+
+- How can I see where RCU is currently used in the Linux kernel?
+
+ Search for "rcu_read_lock", "rcu_read_unlock", "call_rcu",
+ "rcu_read_lock_bh", "rcu_read_unlock_bh", "srcu_read_lock",
+ "srcu_read_unlock", "synchronize_rcu", "synchronize_net",
+ "synchronize_srcu", and the other RCU primitives. Or grab one
+ of the cscope databases from:
+
+ (http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html).
+
+- What guidelines should I follow when writing code that uses RCU?
+
+ See the checklist.txt file in this directory.
+
+- Why the name "RCU"?
+
+ "RCU" stands for "read-copy update". The file Documentation/RCU/listRCU.rst
+ has more information on where this name came from, search for
+ "read-copy update" to find it.
+
+- I hear that RCU is patented? What is with that?
+
+ Yes, it is. There are several known patents related to RCU,
+ search for the string "Patent" in RTFP.txt to find them.
+ Of these, one was allowed to lapse by the assignee, and the
+ others have been contributed to the Linux kernel under GPL.
+ There are now also LGPL implementations of user-level RCU
+ available (http://liburcu.org/).
+
+- I hear that RCU needs work in order to support realtime kernels?
+
+ Realtime-friendly RCU can be enabled via the CONFIG_PREEMPT_RCU
+ kernel configuration parameter.
+
+- Where can I find more information on RCU?
+
+ See the RTFP.txt file in this directory.
+ Or point your browser at (http://www.rdrop.com/users/paulmck/RCU/).
diff --git a/Documentation/RCU/rcu.txt b/Documentation/RCU/rcu.txt
deleted file mode 100644
index 7d4ae11..0000000
--- a/Documentation/RCU/rcu.txt
+++ /dev/null
@@ -1,93 +0,0 @@
-RCU Concepts
-
-
-The basic idea behind RCU (read-copy update) is to split destructive
-operations into two parts, one that prevents anyone from seeing the data
-item being destroyed, and one that actually carries out the destruction.
-A "grace period" must elapse between the two parts, and this grace period
-must be long enough that any readers accessing the item being deleted have
-since dropped their references. For example, an RCU-protected deletion
-from a linked list would first remove the item from the list, wait for
-a grace period to elapse, then free the element. See the listRCU.txt
-file for more information on using RCU with linked lists.
-
-
-Frequently Asked Questions
-
-o Why would anyone want to use RCU?
-
- The advantage of RCU's two-part approach is that RCU readers need
- not acquire any locks, perform any atomic instructions, write to
- shared memory, or (on CPUs other than Alpha) execute any memory
- barriers. The fact that these operations are quite expensive
- on modern CPUs is what gives RCU its performance advantages
- in read-mostly situations. The fact that RCU readers need not
- acquire locks can also greatly simplify deadlock-avoidance code.
-
-o How can the updater tell when a grace period has completed
- if the RCU readers give no indication when they are done?
-
- Just as with spinlocks, RCU readers are not permitted to
- block, switch to user-mode execution, or enter the idle loop.
- Therefore, as soon as a CPU is seen passing through any of these
- three states, we know that that CPU has exited any previous RCU
- read-side critical sections. So, if we remove an item from a
- linked list, and then wait until all CPUs have switched context,
- executed in user mode, or executed in the idle loop, we can
- safely free up that item.
-
- Preemptible variants of RCU (CONFIG_PREEMPT_RCU) get the
- same effect, but require that the readers manipulate CPU-local
- counters. These counters allow limited types of blocking within
- RCU read-side critical sections. SRCU also uses CPU-local
- counters, and permits general blocking within RCU read-side
- critical sections. These variants of RCU detect grace periods
- by sampling these counters.
-
-o If I am running on a uniprocessor kernel, which can only do one
- thing at a time, why should I wait for a grace period?
-
- See the UP.txt file in this directory.
-
-o How can I see where RCU is currently used in the Linux kernel?
-
- Search for "rcu_read_lock", "rcu_read_unlock", "call_rcu",
- "rcu_read_lock_bh", "rcu_read_unlock_bh", "call_rcu_bh",
- "srcu_read_lock", "srcu_read_unlock", "synchronize_rcu",
- "synchronize_net", "synchronize_srcu", and the other RCU
- primitives. Or grab one of the cscope databases from:
-
- http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html
-
-o What guidelines should I follow when writing code that uses RCU?
-
- See the checklist.txt file in this directory.
-
-o Why the name "RCU"?
-
- "RCU" stands for "read-copy update". The file listRCU.txt has
- more information on where this name came from, search for
- "read-copy update" to find it.
-
-o I hear that RCU is patented? What is with that?
-
- Yes, it is. There are several known patents related to RCU,
- search for the string "Patent" in RTFP.txt to find them.
- Of these, one was allowed to lapse by the assignee, and the
- others have been contributed to the Linux kernel under GPL.
- There are now also LGPL implementations of user-level RCU
- available (http://liburcu.org/).
-
-o I hear that RCU needs work in order to support realtime kernels?
-
- Realtime-friendly RCU can be enabled via the CONFIG_PREEMPT_RCU
- kernel configuration parameter.
-
-o Where can I find more information on RCU?
-
- See the RTFP.txt file in this directory.
- Or point your browser at http://www.rdrop.com/users/paulmck/RCU/.
-
-o What are all these files in this directory?
-
- See 00-INDEX for the list.
diff --git a/Documentation/RCU/rcu_dereference.txt b/Documentation/RCU/rcu_dereference.txt
index ab96227..bf699e8 100644
--- a/Documentation/RCU/rcu_dereference.txt
+++ b/Documentation/RCU/rcu_dereference.txt
@@ -351,3 +351,106 @@
In short, rcu_dereference() is -not- optional when you are going to
dereference the resulting pointer.
+
+
+WHICH MEMBER OF THE rcu_dereference() FAMILY SHOULD YOU USE?
+
+First, please avoid using rcu_dereference_raw() and also please avoid
+using rcu_dereference_check() and rcu_dereference_protected() with a
+second argument with a constant value of 1 (or true, for that matter).
+With that caution out of the way, here is some guidance for which
+member of the rcu_dereference() to use in various situations:
+
+1. If the access needs to be within an RCU read-side critical
+ section, use rcu_dereference(). With the new consolidated
+ RCU flavors, an RCU read-side critical section is entered
+ using rcu_read_lock(), anything that disables bottom halves,
+ anything that disables interrupts, or anything that disables
+ preemption.
+
+2. If the access might be within an RCU read-side critical section
+ on the one hand, or protected by (say) my_lock on the other,
+ use rcu_dereference_check(), for example:
+
+ p1 = rcu_dereference_check(p->rcu_protected_pointer,
+ lockdep_is_held(&my_lock));
+
+
+3. If the access might be within an RCU read-side critical section
+ on the one hand, or protected by either my_lock or your_lock on
+ the other, again use rcu_dereference_check(), for example:
+
+ p1 = rcu_dereference_check(p->rcu_protected_pointer,
+ lockdep_is_held(&my_lock) ||
+ lockdep_is_held(&your_lock));
+
+4. If the access is on the update side, so that it is always protected
+ by my_lock, use rcu_dereference_protected():
+
+ p1 = rcu_dereference_protected(p->rcu_protected_pointer,
+ lockdep_is_held(&my_lock));
+
+ This can be extended to handle multiple locks as in #3 above,
+ and both can be extended to check other conditions as well.
+
+5. If the protection is supplied by the caller, and is thus unknown
+ to this code, that is the rare case when rcu_dereference_raw()
+ is appropriate. In addition, rcu_dereference_raw() might be
+ appropriate when the lockdep expression would be excessively
+ complex, except that a better approach in that case might be to
+ take a long hard look at your synchronization design. Still,
+ there are data-locking cases where any one of a very large number
+ of locks or reference counters suffices to protect the pointer,
+ so rcu_dereference_raw() does have its place.
+
+ However, its place is probably quite a bit smaller than one
+ might expect given the number of uses in the current kernel.
+ Ditto for its synonym, rcu_dereference_check( ... , 1), and
+ its close relative, rcu_dereference_protected(... , 1).
+
+
+SPARSE CHECKING OF RCU-PROTECTED POINTERS
+
+The sparse static-analysis tool checks for direct access to RCU-protected
+pointers, which can result in "interesting" bugs due to compiler
+optimizations involving invented loads and perhaps also load tearing.
+For example, suppose someone mistakenly does something like this:
+
+ p = q->rcu_protected_pointer;
+ do_something_with(p->a);
+ do_something_else_with(p->b);
+
+If register pressure is high, the compiler might optimize "p" out
+of existence, transforming the code to something like this:
+
+ do_something_with(q->rcu_protected_pointer->a);
+ do_something_else_with(q->rcu_protected_pointer->b);
+
+This could fatally disappoint your code if q->rcu_protected_pointer
+changed in the meantime. Nor is this a theoretical problem: Exactly
+this sort of bug cost Paul E. McKenney (and several of his innocent
+colleagues) a three-day weekend back in the early 1990s.
+
+Load tearing could of course result in dereferencing a mashup of a pair
+of pointers, which also might fatally disappoint your code.
+
+These problems could have been avoided simply by making the code instead
+read as follows:
+
+ p = rcu_dereference(q->rcu_protected_pointer);
+ do_something_with(p->a);
+ do_something_else_with(p->b);
+
+Unfortunately, these sorts of bugs can be extremely hard to spot during
+review. This is where the sparse tool comes into play, along with the
+"__rcu" marker. If you mark a pointer declaration, whether in a structure
+or as a formal parameter, with "__rcu", which tells sparse to complain if
+this pointer is accessed directly. It will also cause sparse to complain
+if a pointer not marked with "__rcu" is accessed using rcu_dereference()
+and friends. For example, ->rcu_protected_pointer might be declared as
+follows:
+
+ struct foo __rcu *rcu_protected_pointer;
+
+Use of "__rcu" is opt-in. If you choose not to use it, then you should
+ignore the sparse warnings.
diff --git a/Documentation/RCU/rcubarrier.txt b/Documentation/RCU/rcubarrier.txt
index 5d77590..a2782df 100644
--- a/Documentation/RCU/rcubarrier.txt
+++ b/Documentation/RCU/rcubarrier.txt
@@ -83,16 +83,15 @@
2. Execute rcu_barrier().
3. Allow the module to be unloaded.
-There are also rcu_barrier_bh(), rcu_barrier_sched(), and srcu_barrier()
-functions for the other flavors of RCU, and you of course must match
-the flavor of rcu_barrier() with that of call_rcu(). If your module
-uses multiple flavors of call_rcu(), then it must also use multiple
+There is also an srcu_barrier() function for SRCU, and you of course
+must match the flavor of rcu_barrier() with that of call_rcu(). If your
+module uses multiple flavors of call_rcu(), then it must also use multiple
flavors of rcu_barrier() when unloading that module. For example, if
-it uses call_rcu_bh(), call_srcu() on srcu_struct_1, and call_srcu() on
+it uses call_rcu(), call_srcu() on srcu_struct_1, and call_srcu() on
srcu_struct_2(), then the following three lines of code will be required
when unloading:
- 1 rcu_barrier_bh();
+ 1 rcu_barrier();
2 srcu_barrier(&srcu_struct_1);
3 srcu_barrier(&srcu_struct_2);
@@ -185,12 +184,12 @@
the timers, and only then invoke rcu_barrier() to wait for any remaining
RCU callbacks to complete.
-Of course, if you module uses call_rcu_bh(), you will need to invoke
-rcu_barrier_bh() before unloading. Similarly, if your module uses
-call_rcu_sched(), you will need to invoke rcu_barrier_sched() before
-unloading. If your module uses call_rcu(), call_rcu_bh(), -and-
-call_rcu_sched(), then you will need to invoke each of rcu_barrier(),
-rcu_barrier_bh(), and rcu_barrier_sched().
+Of course, if you module uses call_rcu(), you will need to invoke
+rcu_barrier() before unloading. Similarly, if your module uses
+call_srcu(), you will need to invoke srcu_barrier() before unloading,
+and on the same srcu_struct structure. If your module uses call_rcu()
+-and- call_srcu(), then you will need to invoke rcu_barrier() -and-
+srcu_barrier().
Implementing rcu_barrier()
@@ -223,8 +222,8 @@
ensures that all the calls to rcu_barrier_func() will have completed
before on_each_cpu() returns. Line 9 then waits for the completion.
-This code was rewritten in 2008 to support rcu_barrier_bh() and
-rcu_barrier_sched() in addition to the original rcu_barrier().
+This code was rewritten in 2008 and several times thereafter, but this
+still gives the general idea.
The rcu_barrier_func() runs on each CPU, where it invokes call_rcu()
to post an RCU callback, as follows:
diff --git a/Documentation/RCU/rculist_nulls.txt b/Documentation/RCU/rculist_nulls.txt
index 8151f01..23f115d 100644
--- a/Documentation/RCU/rculist_nulls.txt
+++ b/Documentation/RCU/rculist_nulls.txt
@@ -1,7 +1,7 @@
Using hlist_nulls to protect read-mostly linked lists and
objects using SLAB_TYPESAFE_BY_RCU allocations.
-Please read the basics in Documentation/RCU/listRCU.txt
+Please read the basics in Documentation/RCU/listRCU.rst
Using special makers (called 'nulls') is a convenient way
to solve following problem :
diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt
index 613033f..5e6429d 100644
--- a/Documentation/RCU/rcuref.txt
+++ b/Documentation/RCU/rcuref.txt
@@ -12,6 +12,7 @@
Reference counting on elements of lists which are protected by traditional
reader/writer spinlocks or semaphores are straightforward:
+CODE LISTING A:
1. 2.
add() search_and_reference()
{ {
@@ -28,7 +29,8 @@
release_referenced() delete()
{ {
... write_lock(&list_lock);
- atomic_dec(&el->rc, relfunc) ...
+ if(atomic_dec_and_test(&el->rc)) ...
+ kfree(el);
... remove_element
} write_unlock(&list_lock);
...
@@ -44,6 +46,7 @@
has already been deleted from the list/array. Use atomic_inc_not_zero()
in this scenario as follows:
+CODE LISTING B:
1. 2.
add() search_and_reference()
{ {
@@ -79,6 +82,7 @@
atomic_dec_and_test() may be moved from delete() to el_free()
as follows:
+CODE LISTING C:
1. 2.
add() search_and_reference()
{ {
@@ -114,6 +118,17 @@
any reader finds the element, that reader may safely acquire a reference
without checking the value of the reference counter.
+A clear advantage of the RCU-based pattern in listing C over the one
+in listing B is that any call to search_and_reference() that locates
+a given object will succeed in obtaining a reference to that object,
+even given a concurrent invocation of delete() for that same object.
+Similarly, a clear advantage of both listings B and C over listing A is
+that a call to delete() is not delayed even if there are an arbitrarily
+large number of calls to search_and_reference() searching for the same
+object that delete() was invoked on. Instead, all that is delayed is
+the eventual invocation of kfree(), which is usually not a problem on
+modern computer systems, even the small ones.
+
In cases where delete() can sleep, synchronize_rcu() can be called from
delete(), so that el_free() can be subsumed into delete as follows:
@@ -130,3 +145,7 @@
kfree(el);
...
}
+
+As additional examples in the kernel, the pattern in listing C is used by
+reference counting of struct pid, while the pattern in listing B is used by
+struct posix_acl.
diff --git a/Documentation/RCU/stallwarn.txt b/Documentation/RCU/stallwarn.txt
index f99cf11..f48f462 100644
--- a/Documentation/RCU/stallwarn.txt
+++ b/Documentation/RCU/stallwarn.txt
@@ -16,12 +16,9 @@
o A CPU looping with interrupts disabled.
-o A CPU looping with preemption disabled. This condition can
- result in RCU-sched stalls and, if ksoftirqd is in use, RCU-bh
- stalls.
+o A CPU looping with preemption disabled.
-o A CPU looping with bottom halves disabled. This condition can
- result in RCU-sched and RCU-bh stalls.
+o A CPU looping with bottom halves disabled.
o For !CONFIG_PREEMPT kernels, a CPU looping anywhere in the kernel
without invoking schedule(). If the looping in the kernel is
@@ -60,6 +57,12 @@
CONFIG_PREEMPT_RCU case, you might see stall-warning
messages.
+ You can use the rcutree.kthread_prio kernel boot parameter to
+ increase the scheduling priority of RCU's kthreads, which can
+ help avoid this problem. However, please note that doing this
+ can increase your system's context-switch rate and thus degrade
+ performance.
+
o A periodic interrupt whose handler takes longer than the time
interval between successive pairs of interrupts. This can
prevent RCU's kthreads and softirq handlers from running.
@@ -87,9 +90,9 @@
This resulted in a series of RCU CPU stall warnings, eventually
leading the realization that the CPU had failed.
-The RCU, RCU-sched, RCU-bh, and RCU-tasks implementations have CPU stall
-warning. Note that SRCU does -not- have CPU stall warnings. Please note
-that RCU only detects CPU stalls when there is a grace period in progress.
+The RCU, RCU-sched, and RCU-tasks implementations have CPU stall warning.
+Note that SRCU does -not- have CPU stall warnings. Please note that
+RCU only detects CPU stalls when there is a grace period in progress.
No grace period, no CPU stall warnings.
To diagnose the cause of the stall, inspect the stack traces.
@@ -156,7 +159,7 @@
This boot/sysfs parameter controls the RCU-tasks stall warning
interval. A value of zero or less suppresses RCU-tasks stall
warnings. A positive value sets the stall-warning interval
- in jiffies. An RCU-tasks stall warning starts with the line:
+ in seconds. An RCU-tasks stall warning starts with the line:
INFO: rcu_tasks detected stalls on tasks:
@@ -179,9 +182,8 @@
will normally be followed by stack dumps for each CPU. Please note that
PREEMPT_RCU builds can be stalled by tasks as well as by CPUs, and that
the tasks will be indicated by PID, for example, "P3421". It is even
-possible for a rcu_preempt_state stall to be caused by both CPUs -and-
-tasks, in which case the offending CPUs and tasks will all be called
-out in the list.
+possible for an rcu_state stall to be caused by both CPUs -and- tasks,
+in which case the offending CPUs and tasks will all be called out in the list.
CPU 2's "(3 GPs behind)" indicates that this CPU has not interacted with
the RCU core for the past three grace periods. In contrast, CPU 16's "(0
@@ -209,7 +211,7 @@
the stalled CPU is spinning with interrupts are disabled, or, in -rt
kernels, if a high-priority process is starving RCU's softirq handler.
-The "fps=" shows the number of force-quiescent-state idle/offline
+The "fqs=" shows the number of force-quiescent-state idle/offline
detection passes that the grace-period kthread has made across this
CPU since the last time that this CPU noted the beginning of a grace
period.
@@ -223,17 +225,18 @@
In kernels with CONFIG_RCU_FAST_NO_HZ, more information is printed
for each CPU:
- 0: (64628 ticks this GP) idle=dd5/3fffffffffffffff/0 softirq=82/543 last_accelerate: a345/d342 nonlazy_posted: 25 .D
+ 0: (64628 ticks this GP) idle=dd5/3fffffffffffffff/0 softirq=82/543 last_accelerate: a345/d342 Nonlazy posted: ..D
The "last_accelerate:" prints the low-order 16 bits (in hex) of the
jiffies counter when this CPU last invoked rcu_try_advance_all_cbs()
from rcu_needs_cpu() or last invoked rcu_accelerate_cbs() from
-rcu_prepare_for_idle(). The "nonlazy_posted:" prints the number
-of non-lazy callbacks posted since the last call to rcu_needs_cpu().
-Finally, an "L" indicates that there are currently no non-lazy callbacks
-("." is printed otherwise, as shown above) and "D" indicates that
-dyntick-idle processing is enabled ("." is printed otherwise, for example,
-if disabled via the "nohz=" kernel boot parameter).
+rcu_prepare_for_idle(). The "Nonlazy posted:" indicates lazy-callback
+status, so that an "l" indicates that all callbacks were lazy at the start
+of the last idle period and an "L" indicates that there are currently
+no non-lazy callbacks (in both cases, "." is printed otherwise, as
+shown above) and "D" indicates that dyntick-idle processing is enabled
+("." is printed otherwise, for example, if disabled via the "nohz="
+kernel boot parameter).
If the grace period ends just as the stall warning starts printing,
there will be a spurious stall-warning message, which will include
diff --git a/Documentation/RCU/torture.txt b/Documentation/RCU/torture.txt
index 55918b5..a41a038 100644
--- a/Documentation/RCU/torture.txt
+++ b/Documentation/RCU/torture.txt
@@ -10,173 +10,8 @@
command (perhaps grepping for "torture"). The test is started
when the module is loaded, and stops when the module is unloaded.
-
-MODULE PARAMETERS
-
-This module has the following parameters:
-
-fqs_duration Duration (in microseconds) of artificially induced bursts
- of force_quiescent_state() invocations. In RCU
- implementations having force_quiescent_state(), these
- bursts help force races between forcing a given grace
- period and that grace period ending on its own.
-
-fqs_holdoff Holdoff time (in microseconds) between consecutive calls
- to force_quiescent_state() within a burst.
-
-fqs_stutter Wait time (in seconds) between consecutive bursts
- of calls to force_quiescent_state().
-
-gp_normal Make the fake writers use normal synchronous grace-period
- primitives.
-
-gp_exp Make the fake writers use expedited synchronous grace-period
- primitives. If both gp_normal and gp_exp are set, or
- if neither gp_normal nor gp_exp are set, then randomly
- choose the primitive so that about 50% are normal and
- 50% expedited. By default, neither are set, which
- gives best overall test coverage.
-
-irqreader Says to invoke RCU readers from irq level. This is currently
- done via timers. Defaults to "1" for variants of RCU that
- permit this. (Or, more accurately, variants of RCU that do
- -not- permit this know to ignore this variable.)
-
-n_barrier_cbs If this is nonzero, RCU barrier testing will be conducted,
- in which case n_barrier_cbs specifies the number of
- RCU callbacks (and corresponding kthreads) to use for
- this testing. The value cannot be negative. If you
- specify this to be non-zero when torture_type indicates a
- synchronous RCU implementation (one for which a member of
- the synchronize_rcu() rather than the call_rcu() family is
- used -- see the documentation for torture_type below), an
- error will be reported and no testing will be carried out.
-
-nfakewriters This is the number of RCU fake writer threads to run. Fake
- writer threads repeatedly use the synchronous "wait for
- current readers" function of the interface selected by
- torture_type, with a delay between calls to allow for various
- different numbers of writers running in parallel.
- nfakewriters defaults to 4, which provides enough parallelism
- to trigger special cases caused by multiple writers, such as
- the synchronize_srcu() early return optimization.
-
-nreaders This is the number of RCU reading threads supported.
- The default is twice the number of CPUs. Why twice?
- To properly exercise RCU implementations with preemptible
- read-side critical sections.
-
-onoff_interval
- The number of seconds between each attempt to execute a
- randomly selected CPU-hotplug operation. Defaults to
- zero, which disables CPU hotplugging. In HOTPLUG_CPU=n
- kernels, rcutorture will silently refuse to do any
- CPU-hotplug operations regardless of what value is
- specified for onoff_interval.
-
-onoff_holdoff The number of seconds to wait until starting CPU-hotplug
- operations. This would normally only be used when
- rcutorture was built into the kernel and started
- automatically at boot time, in which case it is useful
- in order to avoid confusing boot-time code with CPUs
- coming and going.
-
-shuffle_interval
- The number of seconds to keep the test threads affinitied
- to a particular subset of the CPUs, defaults to 3 seconds.
- Used in conjunction with test_no_idle_hz.
-
-shutdown_secs The number of seconds to run the test before terminating
- the test and powering off the system. The default is
- zero, which disables test termination and system shutdown.
- This capability is useful for automated testing.
-
-stall_cpu The number of seconds that a CPU should be stalled while
- within both an rcu_read_lock() and a preempt_disable().
- This stall happens only once per rcutorture run.
- If you need multiple stalls, use modprobe and rmmod to
- repeatedly run rcutorture. The default for stall_cpu
- is zero, which prevents rcutorture from stalling a CPU.
-
- Note that attempts to rmmod rcutorture while the stall
- is ongoing will hang, so be careful what value you
- choose for this module parameter! In addition, too-large
- values for stall_cpu might well induce failures and
- warnings in other parts of the kernel. You have been
- warned!
-
-stall_cpu_holdoff
- The number of seconds to wait after rcutorture starts
- before stalling a CPU. Defaults to 10 seconds.
-
-stat_interval The number of seconds between output of torture
- statistics (via printk()). Regardless of the interval,
- statistics are printed when the module is unloaded.
- Setting the interval to zero causes the statistics to
- be printed -only- when the module is unloaded, and this
- is the default.
-
-stutter The length of time to run the test before pausing for this
- same period of time. Defaults to "stutter=5", so as
- to run and pause for (roughly) five-second intervals.
- Specifying "stutter=0" causes the test to run continuously
- without pausing, which is the old default behavior.
-
-test_boost Whether or not to test the ability of RCU to do priority
- boosting. Defaults to "test_boost=1", which performs
- RCU priority-inversion testing only if the selected
- RCU implementation supports priority boosting. Specifying
- "test_boost=0" never performs RCU priority-inversion
- testing. Specifying "test_boost=2" performs RCU
- priority-inversion testing even if the selected RCU
- implementation does not support RCU priority boosting,
- which can be used to test rcutorture's ability to
- carry out RCU priority-inversion testing.
-
-test_boost_interval
- The number of seconds in an RCU priority-inversion test
- cycle. Defaults to "test_boost_interval=7". It is
- usually wise for this value to be relatively prime to
- the value selected for "stutter".
-
-test_boost_duration
- The number of seconds to do RCU priority-inversion testing
- within any given "test_boost_interval". Defaults to
- "test_boost_duration=4".
-
-test_no_idle_hz Whether or not to test the ability of RCU to operate in
- a kernel that disables the scheduling-clock interrupt to
- idle CPUs. Boolean parameter, "1" to test, "0" otherwise.
- Defaults to omitting this test.
-
-torture_type The type of RCU to test, with string values as follows:
-
- "rcu": rcu_read_lock(), rcu_read_unlock() and call_rcu(),
- along with expedited, synchronous, and polling
- variants.
-
- "rcu_bh": rcu_read_lock_bh(), rcu_read_unlock_bh(), and
- call_rcu_bh(), along with expedited and synchronous
- variants.
-
- "rcu_busted": This tests an intentionally incorrect version
- of RCU in order to help test rcutorture itself.
-
- "srcu": srcu_read_lock(), srcu_read_unlock() and
- call_srcu(), along with expedited and
- synchronous variants.
-
- "sched": preempt_disable(), preempt_enable(), and
- call_rcu_sched(), along with expedited,
- synchronous, and polling variants.
-
- "tasks": voluntary context switch and call_rcu_tasks(),
- along with expedited and synchronous variants.
-
- Defaults to "rcu".
-
-verbose Enable debug printk()s. Default is disabled.
-
+Module parameters are prefixed by "rcutorture." in
+Documentation/admin-guide/kernel-parameters.txt.
OUTPUT
diff --git a/Documentation/RCU/whatisRCU.txt b/Documentation/RCU/whatisRCU.txt
index c2a7fac..7e1a872 100644
--- a/Documentation/RCU/whatisRCU.txt
+++ b/Documentation/RCU/whatisRCU.txt
@@ -212,7 +212,7 @@
rcu_assign_pointer()
- typeof(p) rcu_assign_pointer(p, typeof(p) v);
+ void rcu_assign_pointer(p, typeof(p) v);
Yes, rcu_assign_pointer() -is- implemented as a macro, though it
would be cool to be able to declare a function in this manner.
@@ -220,9 +220,9 @@
The updater uses this function to assign a new value to an
RCU-protected pointer, in order to safely communicate the change
- in value from the updater to the reader. This function returns
- the new value, and also executes any memory-barrier instructions
- required for a given CPU architecture.
+ in value from the updater to the reader. This macro does not
+ evaluate to an rvalue, but it does execute any memory-barrier
+ instructions required for a given CPU architecture.
Perhaps just as important, it serves to document (1) which
pointers are protected by RCU and (2) the point at which a
@@ -266,7 +266,7 @@
unnecessary overhead on Alpha CPUs.
Note that the value returned by rcu_dereference() is valid
- only within the enclosing RCU read-side critical section.
+ only within the enclosing RCU read-side critical section [1].
For example, the following is -not- legal:
rcu_read_lock();
@@ -292,12 +292,25 @@
typically used indirectly, via the _rcu list-manipulation
primitives, such as list_for_each_entry_rcu().
+ [1] The variant rcu_dereference_protected() can be used outside
+ of an RCU read-side critical section as long as the usage is
+ protected by locks acquired by the update-side code. This variant
+ avoids the lockdep warning that would happen when using (for
+ example) rcu_dereference() without rcu_read_lock() protection.
+ Using rcu_dereference_protected() also has the advantage
+ of permitting compiler optimizations that rcu_dereference()
+ must prohibit. The rcu_dereference_protected() variant takes
+ a lockdep expression to indicate which locks must be acquired
+ by the caller. If the indicated protection is not provided,
+ a lockdep splat is emitted. See RCU/Design/Requirements/Requirements.html
+ and the API's code comments for more details and example usage.
+
The following diagram shows how each API communicates among the
reader, updater, and reclaimer.
rcu_assign_pointer()
- +--------+
+ +--------+
+---------------------->| reader |---------+
| +--------+ |
| | |
@@ -305,12 +318,12 @@
| | | rcu_read_lock()
| | | rcu_read_unlock()
| rcu_dereference() | |
- +---------+ | |
- | updater |<---------------------+ |
- +---------+ V
+ +---------+ | |
+ | updater |<----------------+ |
+ +---------+ V
| +-----------+
+----------------------------------->| reclaimer |
- +-----------+
+ +-----------+
Defer:
synchronize_rcu() & call_rcu()
@@ -322,28 +335,27 @@
implementations of the RCU infrastructure make heavy use of batching in
order to amortize their overhead over many uses of the corresponding APIs.
-There are no fewer than three RCU mechanisms in the Linux kernel; the
-diagram above shows the first one, which is by far the most commonly used.
-The rcu_dereference() and rcu_assign_pointer() primitives are used for
-all three mechanisms, but different defer and protect primitives are
-used as follows:
+There are at least three flavors of RCU usage in the Linux kernel. The diagram
+above shows the most common one. On the updater side, the rcu_assign_pointer(),
+sychronize_rcu() and call_rcu() primitives used are the same for all three
+flavors. However for protection (on the reader side), the primitives used vary
+depending on the flavor:
- Defer Protect
+a. rcu_read_lock() / rcu_read_unlock()
+ rcu_dereference()
-a. synchronize_rcu() rcu_read_lock() / rcu_read_unlock()
- call_rcu() rcu_dereference()
+b. rcu_read_lock_bh() / rcu_read_unlock_bh()
+ local_bh_disable() / local_bh_enable()
+ rcu_dereference_bh()
-b. synchronize_rcu_bh() rcu_read_lock_bh() / rcu_read_unlock_bh()
- call_rcu_bh() rcu_dereference_bh()
+c. rcu_read_lock_sched() / rcu_read_unlock_sched()
+ preempt_disable() / preempt_enable()
+ local_irq_save() / local_irq_restore()
+ hardirq enter / hardirq exit
+ NMI enter / NMI exit
+ rcu_dereference_sched()
-c. synchronize_sched() rcu_read_lock_sched() / rcu_read_unlock_sched()
- call_rcu_sched() preempt_disable() / preempt_enable()
- local_irq_save() / local_irq_restore()
- hardirq enter / hardirq exit
- NMI enter / NMI exit
- rcu_dereference_sched()
-
-These three mechanisms are used as follows:
+These three flavors are used as follows:
a. RCU applied to normal data structures.
@@ -548,7 +560,7 @@
in terms of familiar locking primitives, and another that more closely
resembles "classic" RCU. Both are way too simple for real-world use,
lacking both functionality and performance. However, they are useful
-in getting a feel for how RCU works. See kernel/rcupdate.c for a
+in getting a feel for how RCU works. See kernel/rcu/update.c for a
production-quality implementation, and see:
http://www.rdrop.com/users/paulmck/RCU
@@ -867,18 +879,20 @@
bh: Critical sections Grace period Barrier
- rcu_read_lock_bh call_rcu_bh rcu_barrier_bh
- rcu_read_unlock_bh synchronize_rcu_bh
- rcu_dereference_bh synchronize_rcu_bh_expedited
+ rcu_read_lock_bh call_rcu rcu_barrier
+ rcu_read_unlock_bh synchronize_rcu
+ [local_bh_disable] synchronize_rcu_expedited
+ [and friends]
+ rcu_dereference_bh
rcu_dereference_bh_check
rcu_dereference_bh_protected
rcu_read_lock_bh_held
sched: Critical sections Grace period Barrier
- rcu_read_lock_sched synchronize_sched rcu_barrier_sched
- rcu_read_unlock_sched call_rcu_sched
- [preempt_disable] synchronize_sched_expedited
+ rcu_read_lock_sched call_rcu rcu_barrier
+ rcu_read_unlock_sched synchronize_rcu
+ [preempt_disable] synchronize_rcu_expedited
[and friends]
rcu_read_lock_sched_notrace
rcu_read_unlock_sched_notrace
@@ -890,8 +904,8 @@
SRCU: Critical sections Grace period Barrier
- srcu_read_lock synchronize_srcu srcu_barrier
- srcu_read_unlock call_srcu
+ srcu_read_lock call_srcu srcu_barrier
+ srcu_read_unlock synchronize_srcu
srcu_dereference synchronize_srcu_expedited
srcu_dereference_check
srcu_read_lock_held
@@ -934,7 +948,8 @@
d. Do you need RCU grace periods to complete even in the face
of softirq monopolization of one or more of the CPUs? For
example, is your code subject to network-based denial-of-service
- attacks? If so, you need RCU-bh.
+ attacks? If so, you should disable softirq across your readers,
+ for example, by using rcu_read_lock_bh().
e. Is your workload too update-intensive for normal use of
RCU, but inappropriate for other synchronization mechanisms?
@@ -1033,7 +1048,7 @@
spinlocks blocking while in RCU read-side critical
sections.
- Why the apparent inconsistency? Because it is it
+ Why the apparent inconsistency? Because it is
possible to use priority boosting to keep the RCU
grace periods short if need be (for example, if running
short of memory). In contrast, if blocking waiting
