user
76 lines
16 KiB
XML
76 lines
16 KiB
XML
<?xml version="1.0" encoding="UTF-8" standalone="no"?><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" contentScriptType="application/ecmascript" contentStyleType="text/css" height="620.2694px" preserveAspectRatio="none" style="width:312px;height:620px;" version="1.1" viewBox="0 0 312 620" width="312.6158px" zoomAndPan="magnify"><defs/><g><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="211.9549" x="52.4571" y="7.5779">A2 STRUCTURE — RV32 header, split and two-sided coalescing</text><!--MD5=[9827fb78ff6e3f59cfadf959dc26af7c]
|
||
class HEADER--><rect fill="#EDF6FA" height="69.8104" id="HEADER" style="stroke: #2C7794; stroke-width: 1.0633189422886131;" width="107.7497" x="16.3042" y="15.1133"/><ellipse cx="40.1935" cy="25.0376" fill="#ADD1B2" rx="6.3799" ry="6.3799" style="stroke: #2C7794; stroke-width: 0.7088792948590754;"/><path d="M41.1017,27.3747 Q40.858,27.4965 40.5922,27.5519 Q40.3264,27.6184 40.0273,27.6184 Q38.9861,27.6184 38.4323,26.9316 Q37.8896,26.2449 37.8896,24.9379 Q37.8896,23.6309 38.4323,22.9442 Q38.9861,22.2575 40.0273,22.2575 Q40.3264,22.2575 40.5922,22.3239 Q40.8691,22.3793 41.1017,22.5011 L41.1017,23.642 Q40.8359,23.3983 40.5811,23.2876 Q40.3374,23.1768 40.0827,23.1768 Q39.5178,23.1768 39.2298,23.6198 Q38.9418,24.0629 38.9418,24.9379 Q38.9418,25.8129 39.2298,26.256 Q39.5178,26.699 40.0827,26.699 Q40.3374,26.699 40.5811,26.5883 Q40.8359,26.4775 41.1017,26.2338 L41.1017,27.3747 Z "/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="55.2926" x="51.9609" y="27.7881">01 Block header</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="17.0131" x2="123.345" y1="34.9619" y2="34.9619"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="63.0903" x="20.5575" y="45.3753">next : BlockLink_t*</text><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="38.9884" x="20.5575" y="55.0303">size : size_t</text><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="97.8253" x="20.5575" y="64.6852">raw sizeof = 8 bytes on RV32</text><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="99.2431" x="20.5575" y="74.3401">aligned xHeapStructSize = 16</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="17.0131" x2="123.345" y1="79.2527" y2="79.2527"/><!--MD5=[40d637119be40bcfdc4ce848efbdda9e]
|
||
class ALLOC--><rect fill="#EDF6FA" height="60.1555" id="ALLOC" style="stroke: #2C7794; stroke-width: 1.0633189422886131;" width="114.1296" x="13.1143" y="138.0897"/><ellipse cx="41.6467" cy="148.014" fill="#ADD1B2" rx="6.3799" ry="6.3799" style="stroke: #2C7794; stroke-width: 0.7088792948590754;"/><path d="M42.5549,150.3511 Q42.3112,150.4729 42.0454,150.5283 Q41.7796,150.5948 41.4805,150.5948 Q40.4393,150.5948 39.8855,149.908 Q39.3428,149.2213 39.3428,147.9143 Q39.3428,146.6073 39.8855,145.9206 Q40.4393,145.2339 41.4805,145.2339 Q41.7796,145.2339 42.0454,145.3003 Q42.3223,145.3557 42.5549,145.4775 L42.5549,146.6184 Q42.2891,146.3747 42.0343,146.2639 Q41.7906,146.1532 41.5359,146.1532 Q40.971,146.1532 40.683,146.5962 Q40.395,147.0393 40.395,147.9143 Q40.395,148.7893 40.683,149.2324 Q40.971,149.6754 41.5359,149.6754 Q41.7906,149.6754 42.0343,149.5647 Q42.2891,149.4539 42.5549,149.2102 L42.5549,150.3511 Z "/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="51.7482" x="54.052" y="150.7644">Allocated block</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="13.8231" x2="126.535" y1="157.9383" y2="157.9383"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="105.623" x="17.3675" y="168.3517">02 A: header + 24 byte request</text><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="81.5211" x="17.3675" y="178.0067">aligned total = 48 bytes</text><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="96.4076" x="17.3675" y="187.6616">payload begins after header</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="13.8231" x2="126.535" y1="192.5741" y2="192.5741"/><!--MD5=[71c2adef9be32489055f250a531e7c6f]
|
||
class REM--><rect fill="#EDF6FA" height="50.5005" id="REM" style="stroke: #2C7794; stroke-width: 1.0633189422886131;" width="92.8632" x="23.7475" y="251.4111"/><ellipse cx="37.4288" cy="261.3354" fill="#ADD1B2" rx="6.3799" ry="6.3799" style="stroke: #2C7794; stroke-width: 0.7088792948590754;"/><path d="M38.3371,263.6725 Q38.0934,263.7944 37.8276,263.8497 Q37.5617,263.9162 37.2627,263.9162 Q36.2215,263.9162 35.6677,263.2295 Q35.125,262.5427 35.125,261.2357 Q35.125,259.9287 35.6677,259.242 Q36.2215,258.5553 37.2627,258.5553 Q37.5617,258.5553 37.8276,258.6218 Q38.1045,258.6771 38.3371,258.799 L38.3371,259.9398 Q38.0712,259.6961 37.8165,259.5854 Q37.5728,259.4746 37.3181,259.4746 Q36.7532,259.4746 36.4652,259.9177 Q36.1772,260.3607 36.1772,261.2357 Q36.1772,262.1108 36.4652,262.5538 Q36.7532,262.9969 37.3181,262.9969 Q37.5728,262.9969 37.8165,262.8861 Q38.0712,262.7753 38.3371,262.5317 L38.3371,263.6725 Z "/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="63.0903" x="46.9278" y="264.0859">03 Free remainder</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="24.4563" x2="115.9018" y1="271.2597" y2="271.2597"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="40.4061" x="28.0007" y="281.6732">own header</text><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="84.3566" x="28.0007" y="291.3281">free = 4032 bytes after A</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="24.4563" x2="115.9018" y1="296.2406" y2="296.2406"/><!--MD5=[b0a0edd67d9eafaaa5639bbe6382adce]
|
||
class LIST--><rect fill="#EDF6FA" height="50.5005" id="LIST" style="stroke: #2C7794; stroke-width: 1.0633189422886131;" width="114.8384" x="12.7598" y="355.0776"/><ellipse cx="21.9753" cy="365.0019" fill="#ADD1B2" rx="6.3799" ry="6.3799" style="stroke: #2C7794; stroke-width: 0.7088792948590754;"/><path d="M22.8835,367.339 Q22.6398,367.4609 22.374,367.5162 Q22.1082,367.5827 21.8091,367.5827 Q20.7679,367.5827 20.2141,366.896 Q19.6714,366.2093 19.6714,364.9023 Q19.6714,363.5953 20.2141,362.9085 Q20.7679,362.2218 21.8091,362.2218 Q22.1082,362.2218 22.374,362.2883 Q22.6509,362.3436 22.8835,362.4655 L22.8835,363.6063 Q22.6177,363.3627 22.3629,363.2519 Q22.1192,363.1411 21.8645,363.1411 Q21.2996,363.1411 21.0116,363.5842 Q20.7236,364.0272 20.7236,364.9023 Q20.7236,365.7773 21.0116,366.2203 Q21.2996,366.6634 21.8645,366.6634 Q22.1192,366.6634 22.3629,366.5526 Q22.6177,366.4419 22.8835,366.1982 L22.8835,367.339 Z "/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="94.9898" x="30.4818" y="367.7524">04 Address-ordered free list</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="13.4687" x2="126.8894" y1="374.9263" y2="374.9263"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="99.2431" x="17.0131" y="385.3397">previous < inserted < current</text><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="46.0772" x="17.0131" y="394.9946">A < B < C+tail</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="13.4687" x2="126.8894" y1="399.9071" y2="399.9071"/><!--MD5=[007d3a1820cefd008c8dbdad7e6fdec6]
|
||
class LEFT--><rect fill="#EDF6FA" height="50.5005" id="LEFT" style="stroke: #2C7794; stroke-width: 1.0633189422886131;" width="131.8515" x="4.2533" y="458.7441"/><ellipse cx="21.1246" cy="468.6684" fill="#ADD1B2" rx="6.3799" ry="6.3799" style="stroke: #2C7794; stroke-width: 0.7088792948590754;"/><path d="M22.0329,471.0055 Q21.7892,471.1274 21.5233,471.1828 Q21.2575,471.2492 20.9585,471.2492 Q19.9173,471.2492 19.3635,470.5625 Q18.8207,469.8758 18.8207,468.5688 Q18.8207,467.2618 19.3635,466.575 Q19.9173,465.8883 20.9585,465.8883 Q21.2575,465.8883 21.5233,465.9548 Q21.8003,466.0102 22.0329,466.132 L22.0329,467.2728 Q21.767,467.0292 21.5123,466.9184 Q21.2686,466.8076 21.0138,466.8076 Q20.449,466.8076 20.161,467.2507 Q19.873,467.6937 19.873,468.5688 Q19.873,469.4438 20.161,469.8868 Q20.449,470.3299 21.0138,470.3299 Q21.2686,470.3299 21.5123,470.2191 Q21.767,470.1084 22.0329,469.8647 L22.0329,471.0055 Z "/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="94.9898" x="31.3325" y="471.4189">05 Previous / left neighbour</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="4.9622" x2="135.3959" y1="478.5928" y2="478.5928"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="123.345" x="8.5066" y="489.0062">previous + previous.size == inserted</text><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="68.7613" x="8.5066" y="498.6611">merge previous first</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="4.9622" x2="135.3959" y1="503.5736" y2="503.5736"/><!--MD5=[490fcd32b6546c9bc615869efabd094a]
|
||
class RIGHT--><rect fill="#EDF6FA" height="50.5005" id="RIGHT" style="stroke: #2C7794; stroke-width: 1.0633189422886131;" width="122.6361" x="8.861" y="562.4106"/><ellipse cx="25.0943" cy="572.335" fill="#ADD1B2" rx="6.3799" ry="6.3799" style="stroke: #2C7794; stroke-width: 0.7088792948590754;"/><path d="M26.0026,574.672 Q25.7589,574.7939 25.4931,574.8493 Q25.2272,574.9157 24.9282,574.9157 Q23.887,574.9157 23.3332,574.229 Q22.7905,573.5423 22.7905,572.2353 Q22.7905,570.9283 23.3332,570.2415 Q23.887,569.5548 24.9282,569.5548 Q25.2272,569.5548 25.4931,569.6213 Q25.77,569.6767 26.0026,569.7985 L26.0026,570.9394 Q25.7367,570.6957 25.482,570.5849 Q25.2383,570.4741 24.9836,570.4741 Q24.4187,570.4741 24.1307,570.9172 Q23.8427,571.3602 23.8427,572.2353 Q23.8427,573.1103 24.1307,573.5533 Q24.4187,573.9964 24.9836,573.9964 Q25.2383,573.9964 25.482,573.8856 Q25.7367,573.7749 26.0026,573.5312 L26.0026,574.672 Z "/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="87.1922" x="35.1604" y="575.0854">06 Next / right neighbour</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="9.5699" x2="130.7882" y1="582.2593" y2="582.2593"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="114.1296" x="13.1143" y="592.6727">merged + merged.size == current</text><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="65.2169" x="13.1143" y="602.3276">merge next second</text><line style="stroke: #2C7794; stroke-width: 1.0633189422886131;" x1="9.5699" x2="130.7882" y1="607.2402" y2="607.2402"/><path d="M152.409,367.1286 L152.409,377.4924 L127.9173,380.3279 L152.409,383.1634 L152.409,393.5272 A0,0 0 0 0 152.409,393.5272 L304.1092,393.5272 A0,0 0 0 0 304.1092,393.5272 L304.1092,374.2174 L297.0204,367.1286 L152.409,367.1286 A0,0 0 0 0 152.409,367.1286 " fill="#FBFB77" style="stroke: #A80036; stroke-width: 0.7088792948590754;"/><path d="M297.0204,367.1286 L297.0204,374.2174 L304.1092,374.2174 L297.0204,367.1286 " fill="#FBFB77" style="stroke: #A80036; stroke-width: 0.7088792948590754;"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="124.7628" x="156.6623" y="378.2509">Address order exposes both physical</text><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="136.8137" x="156.6623" y="387.9058">neighbours without scanning the arena.</text><!--MD5=[fc2657b7de304bb41a5d36ac60748945]
|
||
reverse link HEADER to ALLOC--><path d="M70.1791,95.245 C70.1791,109.5006 70.1791,124.9329 70.1791,137.8557 " fill="none" id="HEADER<-ALLOC" style="stroke: #8095A1; stroke-width: 0.7088792948590754;"/><polygon fill="#8095A1" points="70.1791,86.1926,67.3435,90.4459,70.1791,94.6992,73.0146,90.4459,70.1791,86.1926" style="stroke: #8095A1; stroke-width: 0.7088792948590754;"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="60.2547" x="70.8879" y="114.4769">precedes payload</text><!--MD5=[bb73b5a7e21afff1a1d0c43dcbd5d11a]
|
||
link ALLOC to REM--><path d="M70.1791,198.4224 C70.1791,213.4506 70.1791,231.6688 70.1791,246.6687 " fill="none" id="ALLOC->REM" style="stroke: #8095A1; stroke-width: 0.7088792948590754;"/><polygon fill="#8095A1" points="70.1791,250.1422,73.0146,243.7623,70.1791,246.5978,67.3435,243.7623,70.1791,250.1422" style="stroke: #8095A1; stroke-width: 0.7088792948590754;"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="46.0772" x="70.8879" y="227.7983">first-fit + split</text><!--MD5=[32aec76f28e14f88b0d74d9f592c80fb]
|
||
link REM to LIST--><path d="M70.1791,302.1243 C70.1791,316.5855 70.1791,334.9242 70.1791,350.1297 " fill="none" id="REM->LIST" style="stroke: #8095A1; stroke-width: 0.7088792948590754;"/><polygon fill="#8095A1" points="70.1791,353.667,73.0146,347.287,70.1791,350.1226,67.3435,347.287,70.1791,353.667" style="stroke: #8095A1; stroke-width: 0.7088792948590754;"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="58.837" x="70.8879" y="331.4649">insert by address</text><!--MD5=[cc3605e5f4ba919f564e1d79e1300518]
|
||
link LIST to LEFT--><path d="M70.1791,405.7909 C70.1791,420.252 70.1791,438.5907 70.1791,453.7962 " fill="none" id="LIST->LEFT" style="stroke: #8095A1; stroke-width: 0.7088792948590754;"/><polygon fill="#8095A1" points="70.1791,457.3335,73.0146,450.9536,70.1791,453.7891,67.3435,450.9536,70.1791,457.3335" style="stroke: #8095A1; stroke-width: 0.7088792948590754;"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="58.837" x="70.8879" y="435.1314">heap_4 tests first</text><!--MD5=[e8df39c6ef374d140d6cfa6fe0b5ac87]
|
||
link LEFT to RIGHT--><path d="M70.1791,509.4574 C70.1791,523.9185 70.1791,542.2572 70.1791,557.4627 " fill="none" id="LEFT->RIGHT" style="stroke: #8095A1; stroke-width: 0.7088792948590754;"/><polygon fill="#8095A1" points="70.1791,561,73.0146,554.6201,70.1791,557.4556,67.3435,554.6201,70.1791,561" style="stroke: #8095A1; stroke-width: 0.7088792948590754;"/><text fill="#000000" font-family="Monospace" font-size="7.0888" lengthAdjust="spacingAndGlyphs" textLength="51.7482" x="70.8879" y="538.7979">then tests next</text><!--MD5=[d8b34fb36bd2f73cd895320cbfc22e63]
|
||
@startuml
|
||
scale 620 height
|
||
top to bottom direction
|
||
skinparam backgroundColor transparent
|
||
skinparam shadowing false
|
||
skinparam defaultFontName Monospace
|
||
skinparam defaultFontSize 10
|
||
skinparam classBorderColor #2c7794
|
||
skinparam classBackgroundColor #edf6fa
|
||
skinparam ArrowColor #8095a1
|
||
title A2 STRUCTURE — RV32 header, split and two-sided coalescing
|
||
|
||
class "01 Block header" as HEADER {
|
||
next : BlockLink_t*
|
||
size : size_t
|
||
raw sizeof = 8 bytes on RV32
|
||
aligned xHeapStructSize = 16
|
||
}
|
||
class "Allocated block" as ALLOC {
|
||
02 A: header + 24 byte request
|
||
aligned total = 48 bytes
|
||
payload begins after header
|
||
}
|
||
class "03 Free remainder" as REM {
|
||
own header
|
||
free = 4032 bytes after A
|
||
}
|
||
|
||
HEADER *- - ALLOC : precedes payload
|
||
ALLOC -down-> REM : first-fit + split
|
||
|
||
class "04 Address-ordered free list" as LIST {
|
||
previous < inserted < current
|
||
A < B < C+tail
|
||
}
|
||
class "05 Previous / left neighbour" as LEFT {
|
||
previous + previous.size == inserted
|
||
merge previous first
|
||
}
|
||
class "06 Next / right neighbour" as RIGHT {
|
||
merged + merged.size == current
|
||
merge next second
|
||
}
|
||
|
||
REM -down-> LIST : insert by address
|
||
LIST -down-> LEFT : heap_4 tests first
|
||
LEFT -down-> RIGHT : then tests next
|
||
|
||
note right of LIST
|
||
Address order exposes both physical
|
||
neighbours without scanning the arena.
|
||
end note
|
||
@enduml
|
||
|
||
PlantUML version 1.2020.02(Sun Mar 01 11:22:07 CET 2020)
|
||
(GPL source distribution)
|
||
Java Runtime: OpenJDK Runtime Environment
|
||
JVM: OpenJDK 64-Bit Server VM
|
||
Java Version: 25.0.4-ea+4-1-Debian
|
||
Operating System: Linux
|
||
Default Encoding: UTF-8
|
||
Language: en
|
||
Country: null
|
||
--></g></svg> |
