-
Notifications
You must be signed in to change notification settings - Fork 0
/
Tiny Buddy Book.html
69 lines (50 loc) · 32 KB
/
Tiny Buddy Book.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
<!DOCTYPE html><html><head><title>Tiny Buddy Book</title><meta charset='utf-8'><link href='https://dn-maxiang.qbox.me/res-min/themes/marxico.css' rel='stylesheet'><style>
.note-content {font-family: 'Helvetica Neue', Arial, 'Hiragino Sans GB', STHeiti, 'Microsoft YaHei', 'WenQuanYi Micro Hei', SimSun, Song, sans-serif;}
</style></head><body><div id='preview-contents' class='note-content'>
<div id="wmd-preview" class="preview-content"></div>
<div id="wmd-preview-section-48433" class="wmd-preview-section preview-content">
</div><div id="wmd-preview-section-48434" class="wmd-preview-section preview-content">
<h1 id="tiny-buddy-book">Tiny Buddy Book</h1>
</div><div id="wmd-preview-section-48435" class="wmd-preview-section preview-content">
<h3 id="a-simple-implementation-of-buddy-memory-allocation">A simple implementation of Buddy memory allocation</h3>
<p></p>
</div><div id="wmd-preview-section-48436" class="wmd-preview-section preview-content">
<h3 id="the-physical-memory-abstracion"><strong>The physical memory abstracion</strong></h3>
<p>We divided whole memory space into many chunks with the same size, and define each chunk as 4KB in conventional ,which is the size of a page in x86-32 platform. Then in uCore we defien data type <code>struct Page</code>and use an array of <code>pages</code>to represent entire physical memory, our physical memory manager(<strong>pmm</strong>) is built based on this array.Another thing we should notice is that the usable physical memory is not the continuous address space in ideal, for example ,some memory is reserved for kernel,or perhaps memory chipset on motherboard lacks some chips, which lead to “memory hole” . we flag these unallocatable pages so that they will be never touched by any processes. The pages that are not flaged make up the free area.The responsibility of <strong>pmm</strong> is allocate allocatable pages from free area to process and reclaim freed memory to free area.</p>
</div><div id="wmd-preview-section-48437" class="wmd-preview-section preview-content">
<h3 id="buddy-system-as-a-pmm-for-ucore"><strong>Buddy system as a pmm for uCore</strong></h3>
<p>Based on the page structure we have described above, we use a powerful tool to manage physical memory. <br>
The traditional pmm just like <strong>first-fit</strong>,<strong>best-fit</strong>, etc. neraly all use doublely linked list to manage free pages,this cause the allocation or free algorithm is <span class="" rel="1f08ccc9cd7309ba1e756c3d9345ad9f"><span class="MathJax_SVG" id="MathJax-Element-12-Frame" role="textbox" aria-readonly="true" style="font-size: 100%; display: inline-block;"><span><img type="image/png" width="37" height="18" longdesc="__SVG__undefined" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAEoAAAAkCAYAAAAuLqxbAAAH30lEQVRoQ+WaZYwmRRCGn8MhuLu7u4Tg7m5Bg0uwBAgEd3e34O7uDsFdL9gBh3sODYfk2XRfenu/menZ+35sQiUbyHzV3TXVVW+9VXOD+P/KIODf0tdXeWRkamASYBxgTuA94Bfgc+CnkdkYmBbYDTga+GMk98qXjwqcBJwNDCnZuz+O0imrAxsCSwCzZgcNA94BbgcuB74qMSTT2QA4HPgaWBv4qx971C0ZA7gRmA84Eriyaf+2jloP2AdYPmz8FvAk8HEIY522FLBA+P11YCtAvVI5BtgTuC5EVHF6lB6Q6F0IbA4cGyKscotSR40PHA9sCUwAfACcB1wB/JDtPg1wdeLMj4BVgQ8LXuT0cBF3AOsX6HdD5QJgF+AE4KCqDUscNXm43RXDJq+GjV+ssVK8MiIWDDp3A5sCv9esOStE0qMh3ep0u+GguId45cWsBewKGGV9pMlRkwHXAiuHlUaFqfRcgaWnAfsmepsAN1es2xG4OOCZkfR8wf7dVFkUuCsUpS2Ae/PN6xw1UQDkZcOiL4F1gZcKLfRAnRzlpoAH/2TrNfJOYCrgjMy5hUd1RU1QPywEgQXk+3TXKkel4Rj1jwMObmHSYsALif6boVp+kTwbPeCZaWl1tIp+2uKMbqrODDwDTBnA/ZASRx0AnJgo+sJrdADuOkMXAl7JFOYF3k6eiXu3ARYLC8DW3XzzfuwlTdAGL21pwELUI50iag7gsZAKUc+UM4fbiFzrvmyBURZT16g1NY0mRe4k9yoRYcG/mYBFgF8Bq9ffYbGV2Uq7XCDA1wOvFWwcsVLVXjDQyVEaK1+K8kSoCBrTRvYDTs4WLJkA9eyAexvqsnmxanDNAWMBewDLAFbiGZPLTGHBM3xJ0ziK+4u1Vuw6mSvAxbjBznWAb12QO0oj7gHGS3arLJkNhx4FHJrppBG1c1KK3wBMw14Amq01Pc8EfAmdYYsTxTQ3YlYBrgLsDt4PcBF1zgn0o85sW7L7A2NXbyVAutLHUbYc2yY7maOG79A2oQR4+2KP6ZdKilH+HkmlKbpRA89K9zk/cB6fiZ+eMzdwQ4CN/YFRQurPHxZKjrdreI+xQ6CsEPS8GDuRXo6aLhwyS7KZ4JY6rtRfpsXDQLqXVU/cECiNDklebIX8fzGqpF0ZLdAJi4tihyBJvBV4KLQ9Pjc6zI5IeoWCUxtewL2lMfECHwjkd3iaeja5t2QbmR4SwbZiCjyYLdKAzYIzvBS5U3wJiaiEtERmAB5JLkFG7ZTBCUO6xzxZj2lkeVlNYrMc97FX9XK/SR0lHZAWRBEAFwfebdq5w++xHUl/Sp1u82y6xcmD0WDqlYiGe9OK0GA1tnPwL51UbA9cGvRk+pLI7woOMFgMGkVHGV1DoqMs1fZm6Y3ofcH954LNUxVB9vEs7WyifZFPgqLVxVFMFLHFLr5EzgV2D4oCraMS7baCpiIvs4lX2nC01FGutW8dHB1lJfFmImao4AL7urZDMztxOU0qDsj2Sh54eBqpnrVxgZdybHNedQnQi0UH+iDuWR2VnYJewRE9BSFyuz6OmjDMlbydKP0ZdTjUM6Vif+heRpOl/7Nkb9sFnRMxqjT1Up7jdka9FSqnFWlXYDpqj3ShRNKI0vbVTPEYUZZF+UeKE7JZG9s24vp8QiDbjVgR97Ii2aHHAZ9An95i1Zl5tFZNJA4M8zP3cbAofSgd22hLjG65maRzaArmqYIHyHMiqJU4y+5fkE2jsoq7jBnalcizPMuK2DTyTXFHkiru9TDnRCzx0gJBX6kdyGVr9Ye2xM5ErLV9G5Y6SpLmwD2KDFWlJuOjfk5WnwphW3WTkrmIW1YlWXBdmzRF4EnxIqpGMjl9MO3tXZWmLy9mlqkXOdqIIpA6arZQOYwMxfy06pV8HLBiSfoEW8WbkEsNrwnFlLcZHZbvFMfypQsDLycP7RhMq1x0uGRXcdDoOzhLcyqgTbZkv1XYNXGwPV7GiCKQ93r2QzaeUWTlTV8oNMB10Ulij46z36oTZ+u+qMCuNBFCPzrEeVgdL0r1xEuxzwbZSYUR7Fi6StJGvdeoJXeUXbnRYHVRjCq5SDqAi4dMCgjUAqdjDQmq6XBEMu5o8FWPg+PF+F/bkU7i5yWZvBVIkdDu3UHR97EIxcLgJesg9e0wTmkwSGyKo55e3UKnMYs3rVLkIH7UlFv47E/A8BSE/VPHyLHH0ohnmzyT/W4ja5qY7tIKK0ycKaWqee9oVcrbLfV9H+2MRUiy7DOdZK/XJLHZ9tLXBMTZHqkaBesMI0NQyz9wxrXiihTf0v90iyjKjb0sdPU63G+C6QQ06sqDLgqY92NoK6pGMjpf8mxKmxHXhHdpcpJzMQuYlKUPAW76CjM9YN46RbTNUWTqgqoELp1/NxlS9Xs6tahKKUcmprdigWjCPyefYqYRVfTJPPS59rsWAGlHr3VNjurvy7ddt034dwDaY/XrVM3a7tlGXyYvvEhB/Erdp4ANFEf5UhYCAVqcM+XbNuNtHJPqmilirK2Q/yDET1Z9ZCA5SuMiCXWWpbPyb4D9dUbdOrFPvmTaWcE7ykBzlEbGWZYv4DilUxXshsPEPauc/axzuHzi0euMgegoDdwh3K7AKreRlnRT5GVWRptzSawcrVYGqqM02nm7EWUP2u0U9OOHMyyHgLY3jTKQHaXxTU1s4wt2S+E/VyCoNGZKbK0AAAAASUVORK5CYII=" style="margin-top:0;margin-bottom:0;"></span></span></span> in complexity at worst,if the page number is very large ,this seems too slow. <br>
Buddy memory allocation describe a series exquisite algorithms that can finish allocation and free work at worst <span class="" rel="4840badd5478c5e2fa10e45907a181df"><span class="MathJax_SVG" id="MathJax-Element-13-Frame" role="textbox" aria-readonly="true" style="font-size: 100%; display: inline-block;"><span><img type="image/png" width="62" height="18" longdesc="__SVG__undefined" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAHwAAAAkCAYAAABLw14kAAAMqklEQVR4XuXbY7BlSRYF4NVj27Zt2zZjbNu2bdu2bdu2bU98L3J35DtzdF9XdFfX7D9V79701tor8+6VPUcOluRISX6452xpcScHSfL3xVZdg702aTzS9uBJjpPkcEnO3r7/UZKvJfHvr/bB+IdKcvckH07yxpFxTpTkiEnOleS4SU7Y1vLAJC/bB/PuX7oeMMmTkzwnyUfXLnqnCj9GkqsnuVSSkyTxdy+/T/LFJK9J8pQkf1q7oNbuDEnun+T4SS6c5MeD/kdJ8u4kjIKyS/6Y5MxJvrrhfPvX5o9Oco0kj0jyqDWb2FThB05y6yTXSnLaJA74rc3CPpHkP01Bl05yuraAdya5bJI/r1lQMyKL/1aSmyb5/kQ/3i2kPSDJDVqbjye5SJLfrZxrT2h2+yT3TvLCJLdc2tAmCj92kqcnuVgblIfdN8kHRibh9U9oh+/r9ya55Aqla/OSJD9vfb+9tIEkr0hypdZOiLvFij57WhNGf88kj09ym7nNrVX4mZK8OMmJ22CvSnK9JH+YGVwo1u7QrY3ceq+Z9udO8qY2pojwyRVaOXqLMKdpba/SDGBF1z2uybObTh7UlD+6wTUKl0ff1in7/UkumuSvC0cm/FO48E5+muRsSb430q+f445r81GS87boUeMzmm/ucapct6FjNYeBaa6b5LVj3ZYUznNe3RCw/p9LcqEkv1y3hjw1yU26tjdM8qxB3wMleXmSyzcgJjz/ZuX4osY9Wtu1aWPl0PvLZndI8sgkn29Oycm2yZzCD5vklU3B1enK7bO1p3GnJA/vGr8gybUHnY1J4QQglPvXiAjy+g5T6Kf//7McraU4gPpxSW67icIfkuSuXQch4goNia89VEACoChRT8uzf2kfHKaFnvO3kH+OJN9ZObj6H3BUfxOYQUWwiYguSru/dWvapH+1VS0cIsk/WwmqWtlUYJ0xTGR9HHMOL/VzPb9VUT9Jcp5hipvycGTGmzvApbOa+9Mb7kKEuGLXR20uz/62fQacVa4B2OT7tYd1wU7BSjh/j+GD4ZIZ2emb8Z6gcQjmtDaI3zrWiLNjoJdofIEyVCpyVsZ5+0xqUlIePsnx2lrO2EpM6e8XbXJVkZLr1O3vjzUwtnQ+UqM0TB6b5Hb9ZsYUzuoRJhRcQikG2kQO0MJ/309u4c2/bgOVNfrzoUnutsEEfQTCBTCeJZpRG2WbaAB8vq6VgDzhRm1upY1QOHewx2yHCbxqB9QqT50dpZ00yYfa+LyfQb60jY9QksYYXk9Y2QODFyUYwDOaMfRHIlqquefk5EnwESIDBs6Ye2OuMYVDvnKjBZVQ2ijqm5mZBYsSkHkJYGUBCBslle+LoIEsn7dS4SjdtzSUrstsKZKE8T2moVcKcugAZU8GSTd4AHKf1mZsOdb9vla1YBTRv0/qGlK4sXuhzIu3D3ju+RojeKuu0c1aP2nTOZjjU0mu1thMTVHGSK9/zJxTn8c1M5extmRM4bhZh1/yrubda3NI9TtFEmGIpZUI8XK4QxeqeHzJWZJg69aIUMyDbI6IGoxpTCj7DS30+v5+jTAatpV6rI98o0WBYYoAZJ0HDyQP7qqEGo8Bf6b9AY/wVPsa4otTtjSiKQewf3cSjAPBBT/9qynZmZH+/KbOyRqlE+MRBikabslQ4azvPR0Q0uaJSXpLnJpo+LkQaeG99J6IuEEWlDCQr6wcvFeOcCkquawZiv0x4Ou0L+TWOrxhWyWosrNEmB+yiDdO8rTWQMnjwui7g4HOmeSD3WenSvKlkbWhjd0zEMYqMohaMERVG4dskVUpTNaE9IMmeVGHnbal46HCL9fyd78+h1sgYKU+tpoV89P36Q/xLi1v1/dyz9pLD0ZYFOpc9XDnJA/rFCSdTDF4PEJEKkFRyuclrl+F1Mu0D5xJD0irXT+nz8b25dz1d96EBwKSPF1+L+GAIkoxnNvC84wyerpZHne/sBWhhwrviQzfs+JNSqV+ocNI4TDx8IXQESbmKwF0vj6zifpK+QJsCeOE4fS1frVzSIBZhX03S4iJKZHGRIMSh/SO7m937Q6/aFwcA5JjKPJvcQ3SjpzsbqAXoE9erZLS2uAk1VF/M9gzidKf81MFLAnQXcb0hVbBbKH/ocKXyqilier7PlzVZ8MDEt7llxKbX3NZwjCEwFKknNmH4hoPo3f99gfDdXhzBiUf91XCMBQPc6NyR9nTi7QkVwN2BDgEAIfCWHEIxJpED6ANiO2lr0Q2qZR6D/9sA6NbhtQr3P817MMULvyajZhYq2wgDUgSfkrGrHPo4SdrDyeW5kHPAkKE9cpvQw/CzXs4UUbBkPtQOZxD6SRq1E2gaKS+rvKx2vepZOwyqE9jFM+7x8Bub1wqBRdTVRbWXPK3yqHOkRMVflg6o6GHi1ZbNOvQw1mRWrVkE6uqPsLSEOyMceguSVzcl6xVeF+725hDHQrP7jl7gGgIIPs+WDtKLgOZomldUIguohGDUjL9IAnlAFryN6QtlThkDN5QMHKAWSmSIjzaGD7N6lOS3H7WJF9e0nT7vtcjQslcW6+PhgrHafeewMPrrnnNXDaLhKiSQB9R46ojREaPtLWbCs39vEdoYc/myZTVC7V1L1wlz1wF0KcgORIwmwJ3ykkeCoBSkpBsXUVjPrOBvaKPh+fmaRaHKOPCD2DUhuLMiqzZ5GEHnQKXpUfR1lhb6xkqfHjZMVfGjBmAHOgwSqZCru97RsjfCJoeJY+Nr3aFOqUNitRnrOTpLVw6EZ7HyjZzyJ887gJtwiXGTykGZPFUUUR/onZnJDx+TnpF2oO3Bt4ADqWPZJs87BBtOK49EyByb15lqHBARaiqRwtDKnRuIxYuDxZdCIAJJVMHgE/G6KkCCDrTDc+c9CxWn2e9cQOQoHA50YYrMm0LaSOD97W1vUtpU9e/QBmkzjvNRfGbSq9IIA06H1LCWEr5u87GmpyVG0LomyNOiWijQqpqYls6HSrcS0iDFf+NOmQpyos5wXzJpzWJRwhCds+kjfVHSd68feH/S2+yvNsCIgnvshmAS9iCeqvm7hG6KANX2MtQGKfySJhF4FjzGOLXz2G73uWhBEmCQuXVw0eWU2fFyCmy6GahXEgfiujHoDmeswRMsX5AIWOYu9eALxA/jPJ/qpMxatVi5O7y1CWEK3ehKwuEoAYpYiqE9pvr60wHAYBN8cRDy627c4Zik7ygQJJx7IEItdY2VIqD00aJRNm4bm2nxMWINbow6UUfypFGALq5p9nyvyhSKWkKiPWgE9rndEo0QHCsKunX04NmEcS5uJDZkqnrUZaOhKjQ/tzGP7MYClGTUgCPRFUyDpaobMBOLd1a1fw9Yh29v+12AiHz5LpsEf7197dLj7pWrC5Ik6IkhXsPLusGjEcDVwxO9EIdF/89o/OtEMsBqs4etqVM/MKwnq52PQsn7AKH8vhQ6uWKz+V3Bol/UBUsvfXrSz5prQx/VuG+tBiLl9cJhZjMWzaUn7dTNi5ss2zIeO3jhX6DvTeOkRnVFkfMi6pW9rl86ony2D14PZ1yT+7mTwh2nw/44bs9ZRb61fRrfjBBCUpJXo4WtQ64pfJsrVPdraYe/hjCJQ5DqAgxB8QAQ9VOOZxKQARaIqZEDmdkz3TiinvbbwKW3rShEyleSGRhDt1BQsY8ipV+ZIMcNuY9PW6YIjz6iABF2xhvYr1L79+EOJ4OcMnDShycvX/XpB1zI1xcS7qL7oHlkduDDj8GcMdeV8pjCnLWIovoSPnOcO4HGsYTPa0Vrpp6n9+faZW6jI6y8QHbZEnhfWPWRuHygZpujFSYC4dz3/mlCc8RMXaKfnc691I/KUrIn7os0Z8CKyIyLLLTS6el9Ux9rxyT72GwsWvbxZC+04l32s8VJoZLThO+ptDyTsffST8/qJDGGLsoIYXMSc8ezqWnnaxlqU/lbnfhzu/fYx028fClCXfF9wVqHCzAUTdru2LsnYyB8hT6yZqrSe/1KoyO3afvZA1r+sAxOAEYBbaYjL67m8Jtjpf4hQrPcn+99jdpaw5m0zb965U1qUY1YO0qBNTmvvEbN5WSixwgzZxzz58my7JND2ZXt3ef7OBw1VDt2jJvV6/D3QDWDoBSdiI8MHdD4ThyOGLmZ61e3knFsun61etCuUpj7mdce4+7O3p4LQ57J0zhgrF4+5UoP9GaWEQhU2UiTyJy8OhKPPW8HO/RofuIpVp5V+wFrmBgSkv8xCrZnRVuA9DvKPhYtbtd1whNidLFeB21rUvJ6r5caYW+VWWonTd97LlPVlmM3eoxdneFr97IvtSQR6ujMXzOTqpRVezX4HL19v8LY77OQ/1R68oAAAAASUVORK5CYII=" style="margin-top:0;margin-bottom:0;"></span></span></span> <br>
Now let’us treat the memory as a complete binary tree(CBT). Sounds a little stranger,right ? First, walk into the bottom of this CBT,we can see many tree node stand in a line,define every node as a page and are continuous in address. So these page make up entire memory space, and then go up stairs, every higher level nodes can be treated as a root of subtree, this subtree owns some pages in his bottom, and this is a subset of memory space,the higher level it is, the more pages it owns, the root of CBT owns whole memory space.Thus we treat each node as a memory block and each block is exactly power of 2 pages in size.The reason why we use CBT to represent memory map is that we can use binary search in allocation algorithm, it’ll bring <span class="" rel="4840badd5478c5e2fa10e45907a181df"><span class="MathJax_SVG" id="MathJax-Element-14-Frame" role="textbox" aria-readonly="true" style="font-size: 100%; display: inline-block;"><span><img type="image/png" width="62" height="18" longdesc="__SVG__undefined" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAHwAAAAkCAYAAABLw14kAAAMqklEQVR4XuXbY7BlSRYF4NVj27Zt2zZjbNu2bdu2bdu2bU98L3J35DtzdF9XdFfX7D9V79701tor8+6VPUcOluRISX6452xpcScHSfL3xVZdg702aTzS9uBJjpPkcEnO3r7/UZKvJfHvr/bB+IdKcvckH07yxpFxTpTkiEnOleS4SU7Y1vLAJC/bB/PuX7oeMMmTkzwnyUfXLnqnCj9GkqsnuVSSkyTxdy+/T/LFJK9J8pQkf1q7oNbuDEnun+T4SS6c5MeD/kdJ8u4kjIKyS/6Y5MxJvrrhfPvX5o9Oco0kj0jyqDWb2FThB05y6yTXSnLaJA74rc3CPpHkP01Bl05yuraAdya5bJI/r1lQMyKL/1aSmyb5/kQ/3i2kPSDJDVqbjye5SJLfrZxrT2h2+yT3TvLCJLdc2tAmCj92kqcnuVgblIfdN8kHRibh9U9oh+/r9ya55Aqla/OSJD9vfb+9tIEkr0hypdZOiLvFij57WhNGf88kj09ym7nNrVX4mZK8OMmJ22CvSnK9JH+YGVwo1u7QrY3ceq+Z9udO8qY2pojwyRVaOXqLMKdpba/SDGBF1z2uybObTh7UlD+6wTUKl0ff1in7/UkumuSvC0cm/FO48E5+muRsSb430q+f445r81GS87boUeMzmm/ucapct6FjNYeBaa6b5LVj3ZYUznNe3RCw/p9LcqEkv1y3hjw1yU26tjdM8qxB3wMleXmSyzcgJjz/ZuX4osY9Wtu1aWPl0PvLZndI8sgkn29Oycm2yZzCD5vklU3B1enK7bO1p3GnJA/vGr8gybUHnY1J4QQglPvXiAjy+g5T6Kf//7McraU4gPpxSW67icIfkuSuXQch4goNia89VEACoChRT8uzf2kfHKaFnvO3kH+OJN9ZObj6H3BUfxOYQUWwiYguSru/dWvapH+1VS0cIsk/WwmqWtlUYJ0xTGR9HHMOL/VzPb9VUT9Jcp5hipvycGTGmzvApbOa+9Mb7kKEuGLXR20uz/62fQacVa4B2OT7tYd1wU7BSjh/j+GD4ZIZ2emb8Z6gcQjmtDaI3zrWiLNjoJdofIEyVCpyVsZ5+0xqUlIePsnx2lrO2EpM6e8XbXJVkZLr1O3vjzUwtnQ+UqM0TB6b5Hb9ZsYUzuoRJhRcQikG2kQO0MJ/309u4c2/bgOVNfrzoUnutsEEfQTCBTCeJZpRG2WbaAB8vq6VgDzhRm1upY1QOHewx2yHCbxqB9QqT50dpZ00yYfa+LyfQb60jY9QksYYXk9Y2QODFyUYwDOaMfRHIlqquefk5EnwESIDBs6Ye2OuMYVDvnKjBZVQ2ijqm5mZBYsSkHkJYGUBCBslle+LoIEsn7dS4SjdtzSUrstsKZKE8T2moVcKcugAZU8GSTd4AHKf1mZsOdb9vla1YBTRv0/qGlK4sXuhzIu3D3ju+RojeKuu0c1aP2nTOZjjU0mu1thMTVHGSK9/zJxTn8c1M5extmRM4bhZh1/yrubda3NI9TtFEmGIpZUI8XK4QxeqeHzJWZJg69aIUMyDbI6IGoxpTCj7DS30+v5+jTAatpV6rI98o0WBYYoAZJ0HDyQP7qqEGo8Bf6b9AY/wVPsa4otTtjSiKQewf3cSjAPBBT/9qynZmZH+/KbOyRqlE+MRBikabslQ4azvPR0Q0uaJSXpLnJpo+LkQaeG99J6IuEEWlDCQr6wcvFeOcCkquawZiv0x4Ou0L+TWOrxhWyWosrNEmB+yiDdO8rTWQMnjwui7g4HOmeSD3WenSvKlkbWhjd0zEMYqMohaMERVG4dskVUpTNaE9IMmeVGHnbal46HCL9fyd78+h1sgYKU+tpoV89P36Q/xLi1v1/dyz9pLD0ZYFOpc9XDnJA/rFCSdTDF4PEJEKkFRyuclrl+F1Mu0D5xJD0irXT+nz8b25dz1d96EBwKSPF1+L+GAIkoxnNvC84wyerpZHne/sBWhhwrviQzfs+JNSqV+ocNI4TDx8IXQESbmKwF0vj6zifpK+QJsCeOE4fS1frVzSIBZhX03S4iJKZHGRIMSh/SO7m937Q6/aFwcA5JjKPJvcQ3SjpzsbqAXoE9erZLS2uAk1VF/M9gzidKf81MFLAnQXcb0hVbBbKH/ocKXyqilier7PlzVZ8MDEt7llxKbX3NZwjCEwFKknNmH4hoPo3f99gfDdXhzBiUf91XCMBQPc6NyR9nTi7QkVwN2BDgEAIfCWHEIxJpED6ANiO2lr0Q2qZR6D/9sA6NbhtQr3P817MMULvyajZhYq2wgDUgSfkrGrHPo4SdrDyeW5kHPAkKE9cpvQw/CzXs4UUbBkPtQOZxD6SRq1E2gaKS+rvKx2vepZOwyqE9jFM+7x8Bub1wqBRdTVRbWXPK3yqHOkRMVflg6o6GHi1ZbNOvQw1mRWrVkE6uqPsLSEOyMceguSVzcl6xVeF+725hDHQrP7jl7gGgIIPs+WDtKLgOZomldUIguohGDUjL9IAnlAFryN6QtlThkDN5QMHKAWSmSIjzaGD7N6lOS3H7WJF9e0nT7vtcjQslcW6+PhgrHafeewMPrrnnNXDaLhKiSQB9R46ojREaPtLWbCs39vEdoYc/myZTVC7V1L1wlz1wF0KcgORIwmwJ3ykkeCoBSkpBsXUVjPrOBvaKPh+fmaRaHKOPCD2DUhuLMiqzZ5GEHnQKXpUfR1lhb6xkqfHjZMVfGjBmAHOgwSqZCru97RsjfCJoeJY+Nr3aFOqUNitRnrOTpLVw6EZ7HyjZzyJ887gJtwiXGTykGZPFUUUR/onZnJDx+TnpF2oO3Bt4ADqWPZJs87BBtOK49EyByb15lqHBARaiqRwtDKnRuIxYuDxZdCIAJJVMHgE/G6KkCCDrTDc+c9CxWn2e9cQOQoHA50YYrMm0LaSOD97W1vUtpU9e/QBmkzjvNRfGbSq9IIA06H1LCWEr5u87GmpyVG0LomyNOiWijQqpqYls6HSrcS0iDFf+NOmQpyos5wXzJpzWJRwhCds+kjfVHSd68feH/S2+yvNsCIgnvshmAS9iCeqvm7hG6KANX2MtQGKfySJhF4FjzGOLXz2G73uWhBEmCQuXVw0eWU2fFyCmy6GahXEgfiujHoDmeswRMsX5AIWOYu9eALxA/jPJ/qpMxatVi5O7y1CWEK3ehKwuEoAYpYiqE9pvr60wHAYBN8cRDy627c4Zik7ygQJJx7IEItdY2VIqD00aJRNm4bm2nxMWINbow6UUfypFGALq5p9nyvyhSKWkKiPWgE9rndEo0QHCsKunX04NmEcS5uJDZkqnrUZaOhKjQ/tzGP7MYClGTUgCPRFUyDpaobMBOLd1a1fw9Yh29v+12AiHz5LpsEf7197dLj7pWrC5Ik6IkhXsPLusGjEcDVwxO9EIdF/89o/OtEMsBqs4etqVM/MKwnq52PQsn7AKH8vhQ6uWKz+V3Bol/UBUsvfXrSz5prQx/VuG+tBiLl9cJhZjMWzaUn7dTNi5ss2zIeO3jhX6DvTeOkRnVFkfMi6pW9rl86ony2D14PZ1yT+7mTwh2nw/44bs9ZRb61fRrfjBBCUpJXo4WtQ64pfJsrVPdraYe/hjCJQ5DqAgxB8QAQ9VOOZxKQARaIqZEDmdkz3TiinvbbwKW3rShEyleSGRhDt1BQsY8ipV+ZIMcNuY9PW6YIjz6iABF2xhvYr1L79+EOJ4OcMnDShycvX/XpB1zI1xcS7qL7oHlkduDDj8GcMdeV8pjCnLWIovoSPnOcO4HGsYTPa0Vrpp6n9+faZW6jI6y8QHbZEnhfWPWRuHygZpujFSYC4dz3/mlCc8RMXaKfnc691I/KUrIn7os0Z8CKyIyLLLTS6el9Ux9rxyT72GwsWvbxZC+04l32s8VJoZLThO+ptDyTsffST8/qJDGGLsoIYXMSc8ezqWnnaxlqU/lbnfhzu/fYx028fClCXfF9wVqHCzAUTdru2LsnYyB8hT6yZqrSe/1KoyO3afvZA1r+sAxOAEYBbaYjL67m8Jtjpf4hQrPcn+99jdpaw5m0zb965U1qUY1YO0qBNTmvvEbN5WSixwgzZxzz58my7JND2ZXt3ef7OBw1VDt2jJvV6/D3QDWDoBSdiI8MHdD4ThyOGLmZ61e3knFsun61etCuUpj7mdce4+7O3p4LQ57J0zhgrF4+5UoP9GaWEQhU2UiTyJy8OhKPPW8HO/RofuIpVp5V+wFrmBgSkv8xCrZnRVuA9DvKPhYtbtd1whNidLFeB21rUvJ6r5caYW+VWWonTd97LlPVlmM3eoxdneFr97IvtSQR6ujMXzOTqpRVezX4HL19v8LY77OQ/1R68oAAAAASUVORK5CYII=" style="margin-top:0;margin-bottom:0;"></span></span></span> in complexity. </p>
<ul><li><p><strong>Buddy Data Structure</strong> <br>
It is time to define the datastrcture of this CBT，before to do this , we need to make clear how to measure size of memory. Block size are be measured using term <code>order</code>, a block with order <code>o</code> means this block have <span class="" rel="c4ac6abb3be2ee9441487b37b7baf1c7"><span class="MathJax_SVG" id="MathJax-Element-15-Frame" role="textbox" aria-readonly="true" style="font-size: 100%; display: inline-block;"><span><img type="image/png" width="35" height="18" longdesc="__SVG__undefined" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAEYAAAAkCAYAAAA0EkzVAAAE3klEQVRoQ+WadahlVRSHv7EbFWMMVAzELkZB7MDATlAUxQIDRVQYExM7EEFsQcXuRgwM7MbAxMBmbBQsPllb9px34p4z3vveu7P+edxzdq3fXuu34rwJDL/MDswJ+PcX4Afgzya1JzQNGOfv9wZ2BTYE5gbeBZ4ELgDeqtNtmIE5GTixQvkfgR2Ax6rAGVZgVPoO4HrgauDDsJp9gQ0CjBeAzQBBGiHDCMwcwP3Aq8ARBY0XAm7JwNkpAJwugFkSeA5YFfi6xBgE47Z4fhBw2ViwGC10VuC3PpL6+sAKVQoDSwEfxf4HApePJjCLANsCmwOzAFOAe4Dbgb/7AJIXULXussB7sefGwONdgJkRmB+YDfgD+An4uaUihsvzAcnOSPEdcAogEZ4OHN9yvWkdnohZQLysUn2qyHeBCGe7AN62CdEMwLfAM8A1wfRNh1TxY4FrgX2ywYsBnwHfA/p8Zdhs2qDle/WVfHeO/ObWNuF6JeA6YPWaTb8AjgRurBlzaljDi4Amm9/MgsC9wNrAMcA5LRXsOlzdng7y3b/OjYsWsyJwN7BMDzsb/w+OXKE4fJPYfN6wCHOKXBYHPo0HpwEnRNquq2mtbUWXF2AvrEpmjgtfOFxIWqiUHBiV0MxMep4NVn8ZcIyArQPoWotmq3mQdYGPs2eS653AVsATFYdYE3gp5nhzVwITw4rWaotK3LzW8HaDBct32wDvN+2RA2MyZA0hOPLBryWT9U1dxHCYRCI9KfutC74Sv48CzitZRzf0ubemQlqPYdyDz9V06JL3WswNEe3KpnvuM4I368D7b24CxupTn58P2AL4quZwmuxZ2Xtdbzfg98wCUm6gZSSQ0hQVdy8Lu5uBPXqpdjuAlabsGOcVnDdK1ikN7QkYLeD5IMuLGg5hZvkIYD6gvA5slN2WnHFcvJNLPi+sJxE/GjXKehWHnQYcppq6HXApYIZr3lQUywd58uLsYv8dk4DxxieHtZSl0fmC5jWGa3MAxVC7fbiFv48Gzg5/1yq+ySYnyxTIA4Ar/i8EStaxJDCB1NUfKLz/K1xXI3gnyH+qIQmYmSKRawLFyY61ahVMRaI1F0mZpkrfBcwDrAK8GePkgQuBvYBzAS2rXyJvyZW67ZcVmywfhpE4rhSYNgfUYow2K8ckybjY9zDsSuZPRY5iCLYukcPOzIq4Nvv2OlZFLRJVvElMIyT8ER29Lm0Hw7Vl/WpxG/Y3Uu2RH0TL2RRYOpK7h4NbrJP6KeZg8lhTDaYFy5X2akZIF2Dysl1zTS7VT2UHvnYXYCwX9gQ+AMxwPxn4qQewYVtgJgXZ6k77AVcN4IyjskUbYEz1jTZbApcAh47KiQe0aRtgLBNsLD8EbA2YCwyt9AqM7cL7opcq+dZWpsOAVi/ArAHcFJ03U+w8kx0GDEp1aALGzw0mQamH0VNlOgxo1QFjhmueskS0Ai0WpxupAsYaw2rU3qxtAduTdWKlbQ1kzyO1H8Y1iGXA2DAyfV8uOnY2v+vELwiOfw04bFyjkR2+CIy/LdVtb9rhNzRXiYWXH68Oj6a2rc/a/yAYT6AVgUlNnbY6PBj9Gb89DYXkwJjN2s3qIrtHm7LL3DE5JwFzSLT3msJ3mRKG8GKnbkwq2+ZQCQj/DcsI1EX8vtRL56/L2qM25x8WNuMlwSXZKAAAAABJRU5ErkJggg==" style="margin-top:0;margin-bottom:0;"></span></span></span> continuous pages, the start address of this block is start address of first block. Every node we called it a buddy, a buddy is just a unsigned short which separate into three field as follows.</p>
<table>
<thead>
<tr>
<th align="left">order</th>
<th align="right">left</th>
<th align="center">right</th>
</tr>
</thead>
</table>
<ul>
<li>order : The order of this block.</li>
<li>left : The allocable memory of left tree, measure in order</li>
<li>right : The allocable memory of right tree, measure in order</li></ul>
<p>Each field is 5 bit width, the most significant bit is not used at present. We can extract this info through bit-wise operation, and are defined as macros in <code>tiny_buddy.h</code>. <br>
The CBT is an array of buddys, which is defined as <code>Buddy *mem</code> in uCore .We need a continuous memory reserved for Buddy system.</p></li>
<li><strong>The allocation algorithm</strong> <br>
The algorithm is just like binary search. Given the number of pages need to allocated , calculate the minimum order that can satisfy requirement.Then start from root,if the left allocable satisfy request then go left,else if the right allocable satisfy request then go right, if neither left nor right could satisfy request, then the allocation failed and return <code>NULL</code>,otherwise it will finally stop at a buddy. and this buddy’s order must equal allocation order, it is what we want. Attention! Don’t forget flag this buddy as unallocatable and update its ancestor’s allocable status.<code>struct Page* buddy_alloc_pages(size_t n)</code>do this work in uCore, return value is the head page of a memory block, and the page’s property flag should be set, the property should be assigned to n, which means the next following continous pages are allocated.</li>
<li><strong>The free algorithm</strong> <br>
Given an allocated block,first we should translate physical address to buddy index,then modify buddy’s field. Next flag this buddy as allocatable and update ancestors’ allocatable status. Because of using of CBT,free block merge has finished implicitly.<code>void buddy_free_pages(struct Page* page)</code> do this work in uCore, the argument page is the header page of memory block need to be freed, the page’s property flag should be clean and property should be assigned to zero. </li>
<li><p><strong>The initialization algorithm</strong> <br>
Initialization is divided into 2 steps.</p>
<ul>
<li>Flag all pages as unallocable </li>
<li>Flag usable page as allocable one by one <br>
Bootloader will provide usable continous pages to pmm, once we flag one page as allocable, update his ancestor’s allocable status immediately. Each page will cost <span class="" rel="4840badd5478c5e2fa10e45907a181df"><span class="MathJax_SVG" id="MathJax-Element-16-Frame" role="textbox" aria-readonly="true" style="font-size: 100%; display: inline-block;"><span><img type="image/png" width="62" height="18" longdesc="__SVG__undefined" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAHwAAAAkCAYAAABLw14kAAAMqklEQVR4XuXbY7BlSRYF4NVj27Zt2zZjbNu2bdu2bdu2bU98L3J35DtzdF9XdFfX7D9V79701tor8+6VPUcOluRISX6452xpcScHSfL3xVZdg702aTzS9uBJjpPkcEnO3r7/UZKvJfHvr/bB+IdKcvckH07yxpFxTpTkiEnOleS4SU7Y1vLAJC/bB/PuX7oeMMmTkzwnyUfXLnqnCj9GkqsnuVSSkyTxdy+/T/LFJK9J8pQkf1q7oNbuDEnun+T4SS6c5MeD/kdJ8u4kjIKyS/6Y5MxJvrrhfPvX5o9Oco0kj0jyqDWb2FThB05y6yTXSnLaJA74rc3CPpHkP01Bl05yuraAdya5bJI/r1lQMyKL/1aSmyb5/kQ/3i2kPSDJDVqbjye5SJLfrZxrT2h2+yT3TvLCJLdc2tAmCj92kqcnuVgblIfdN8kHRibh9U9oh+/r9ya55Aqla/OSJD9vfb+9tIEkr0hypdZOiLvFij57WhNGf88kj09ym7nNrVX4mZK8OMmJ22CvSnK9JH+YGVwo1u7QrY3ceq+Z9udO8qY2pojwyRVaOXqLMKdpba/SDGBF1z2uybObTh7UlD+6wTUKl0ff1in7/UkumuSvC0cm/FO48E5+muRsSb430q+f445r81GS87boUeMzmm/ucapct6FjNYeBaa6b5LVj3ZYUznNe3RCw/p9LcqEkv1y3hjw1yU26tjdM8qxB3wMleXmSyzcgJjz/ZuX4osY9Wtu1aWPl0PvLZndI8sgkn29Oycm2yZzCD5vklU3B1enK7bO1p3GnJA/vGr8gybUHnY1J4QQglPvXiAjy+g5T6Kf//7McraU4gPpxSW67icIfkuSuXQch4goNia89VEACoChRT8uzf2kfHKaFnvO3kH+OJN9ZObj6H3BUfxOYQUWwiYguSru/dWvapH+1VS0cIsk/WwmqWtlUYJ0xTGR9HHMOL/VzPb9VUT9Jcp5hipvycGTGmzvApbOa+9Mb7kKEuGLXR20uz/62fQacVa4B2OT7tYd1wU7BSjh/j+GD4ZIZ2emb8Z6gcQjmtDaI3zrWiLNjoJdofIEyVCpyVsZ5+0xqUlIePsnx2lrO2EpM6e8XbXJVkZLr1O3vjzUwtnQ+UqM0TB6b5Hb9ZsYUzuoRJhRcQikG2kQO0MJ/309u4c2/bgOVNfrzoUnutsEEfQTCBTCeJZpRG2WbaAB8vq6VgDzhRm1upY1QOHewx2yHCbxqB9QqT50dpZ00yYfa+LyfQb60jY9QksYYXk9Y2QODFyUYwDOaMfRHIlqquefk5EnwESIDBs6Ye2OuMYVDvnKjBZVQ2ijqm5mZBYsSkHkJYGUBCBslle+LoIEsn7dS4SjdtzSUrstsKZKE8T2moVcKcugAZU8GSTd4AHKf1mZsOdb9vla1YBTRv0/qGlK4sXuhzIu3D3ju+RojeKuu0c1aP2nTOZjjU0mu1thMTVHGSK9/zJxTn8c1M5extmRM4bhZh1/yrubda3NI9TtFEmGIpZUI8XK4QxeqeHzJWZJg69aIUMyDbI6IGoxpTCj7DS30+v5+jTAatpV6rI98o0WBYYoAZJ0HDyQP7qqEGo8Bf6b9AY/wVPsa4otTtjSiKQewf3cSjAPBBT/9qynZmZH+/KbOyRqlE+MRBikabslQ4azvPR0Q0uaJSXpLnJpo+LkQaeG99J6IuEEWlDCQr6wcvFeOcCkquawZiv0x4Ou0L+TWOrxhWyWosrNEmB+yiDdO8rTWQMnjwui7g4HOmeSD3WenSvKlkbWhjd0zEMYqMohaMERVG4dskVUpTNaE9IMmeVGHnbal46HCL9fyd78+h1sgYKU+tpoV89P36Q/xLi1v1/dyz9pLD0ZYFOpc9XDnJA/rFCSdTDF4PEJEKkFRyuclrl+F1Mu0D5xJD0irXT+nz8b25dz1d96EBwKSPF1+L+GAIkoxnNvC84wyerpZHne/sBWhhwrviQzfs+JNSqV+ocNI4TDx8IXQESbmKwF0vj6zifpK+QJsCeOE4fS1frVzSIBZhX03S4iJKZHGRIMSh/SO7m937Q6/aFwcA5JjKPJvcQ3SjpzsbqAXoE9erZLS2uAk1VF/M9gzidKf81MFLAnQXcb0hVbBbKH/ocKXyqilier7PlzVZ8MDEt7llxKbX3NZwjCEwFKknNmH4hoPo3f99gfDdXhzBiUf91XCMBQPc6NyR9nTi7QkVwN2BDgEAIfCWHEIxJpED6ANiO2lr0Q2qZR6D/9sA6NbhtQr3P817MMULvyajZhYq2wgDUgSfkrGrHPo4SdrDyeW5kHPAkKE9cpvQw/CzXs4UUbBkPtQOZxD6SRq1E2gaKS+rvKx2vepZOwyqE9jFM+7x8Bub1wqBRdTVRbWXPK3yqHOkRMVflg6o6GHi1ZbNOvQw1mRWrVkE6uqPsLSEOyMceguSVzcl6xVeF+725hDHQrP7jl7gGgIIPs+WDtKLgOZomldUIguohGDUjL9IAnlAFryN6QtlThkDN5QMHKAWSmSIjzaGD7N6lOS3H7WJF9e0nT7vtcjQslcW6+PhgrHafeewMPrrnnNXDaLhKiSQB9R46ojREaPtLWbCs39vEdoYc/myZTVC7V1L1wlz1wF0KcgORIwmwJ3ykkeCoBSkpBsXUVjPrOBvaKPh+fmaRaHKOPCD2DUhuLMiqzZ5GEHnQKXpUfR1lhb6xkqfHjZMVfGjBmAHOgwSqZCru97RsjfCJoeJY+Nr3aFOqUNitRnrOTpLVw6EZ7HyjZzyJ887gJtwiXGTykGZPFUUUR/onZnJDx+TnpF2oO3Bt4ADqWPZJs87BBtOK49EyByb15lqHBARaiqRwtDKnRuIxYuDxZdCIAJJVMHgE/G6KkCCDrTDc+c9CxWn2e9cQOQoHA50YYrMm0LaSOD97W1vUtpU9e/QBmkzjvNRfGbSq9IIA06H1LCWEr5u87GmpyVG0LomyNOiWijQqpqYls6HSrcS0iDFf+NOmQpyos5wXzJpzWJRwhCds+kjfVHSd68feH/S2+yvNsCIgnvshmAS9iCeqvm7hG6KANX2MtQGKfySJhF4FjzGOLXz2G73uWhBEmCQuXVw0eWU2fFyCmy6GahXEgfiujHoDmeswRMsX5AIWOYu9eALxA/jPJ/qpMxatVi5O7y1CWEK3ehKwuEoAYpYiqE9pvr60wHAYBN8cRDy627c4Zik7ygQJJx7IEItdY2VIqD00aJRNm4bm2nxMWINbow6UUfypFGALq5p9nyvyhSKWkKiPWgE9rndEo0QHCsKunX04NmEcS5uJDZkqnrUZaOhKjQ/tzGP7MYClGTUgCPRFUyDpaobMBOLd1a1fw9Yh29v+12AiHz5LpsEf7197dLj7pWrC5Ik6IkhXsPLusGjEcDVwxO9EIdF/89o/OtEMsBqs4etqVM/MKwnq52PQsn7AKH8vhQ6uWKz+V3Bol/UBUsvfXrSz5prQx/VuG+tBiLl9cJhZjMWzaUn7dTNi5ss2zIeO3jhX6DvTeOkRnVFkfMi6pW9rl86ony2D14PZ1yT+7mTwh2nw/44bs9ZRb61fRrfjBBCUpJXo4WtQ64pfJsrVPdraYe/hjCJQ5DqAgxB8QAQ9VOOZxKQARaIqZEDmdkz3TiinvbbwKW3rShEyleSGRhDt1BQsY8ipV+ZIMcNuY9PW6YIjz6iABF2xhvYr1L79+EOJ4OcMnDShycvX/XpB1zI1xcS7qL7oHlkduDDj8GcMdeV8pjCnLWIovoSPnOcO4HGsYTPa0Vrpp6n9+faZW6jI6y8QHbZEnhfWPWRuHygZpujFSYC4dz3/mlCc8RMXaKfnc691I/KUrIn7os0Z8CKyIyLLLTS6el9Ux9rxyT72GwsWvbxZC+04l32s8VJoZLThO+ptDyTsffST8/qJDGGLsoIYXMSc8ezqWnnaxlqU/lbnfhzu/fYx028fClCXfF9wVqHCzAUTdru2LsnYyB8hT6yZqrSe/1KoyO3afvZA1r+sAxOAEYBbaYjL67m8Jtjpf4hQrPcn+99jdpaw5m0zb965U1qUY1YO0qBNTmvvEbN5WSixwgzZxzz58my7JND2ZXt3ef7OBw1VDt2jJvV6/D3QDWDoBSdiI8MHdD4ThyOGLmZ61e3knFsun61etCuUpj7mdce4+7O3p4LQ57J0zhgrF4+5UoP9GaWEQhU2UiTyJy8OhKPPW8HO/RofuIpVp5V+wFrmBgSkv8xCrZnRVuA9DvKPhYtbtd1whNidLFeB21rUvJ6r5caYW+VWWonTd97LlPVlmM3eoxdneFr97IvtSQR6ujMXzOTqpRVezX4HL19v8LY77OQ/1R68oAAAAASUVORK5CYII=" style="margin-top:0;margin-bottom:0;"></span></span></span> to do update, The complexity of this algorithm is finally <span class="" rel="743c00b1fa7d59c887892656948b54b8"><span class="MathJax_SVG" id="MathJax-Element-17-Frame" role="textbox" aria-readonly="true" style="font-size: 100%; display: inline-block;"><span><img type="image/png" width="71" height="18" longdesc="__SVG__undefined" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAI4AAAAkCAYAAABfegKAAAAOSklEQVR4Xt3bA5CkyRYF4LPPtm3btm3btm3btm3bthnPtv3i68jsyMn5VdM1Pb17Izp2tiqdF+eem7VfdrYcPMk/9sESj5DkcEl+uA/m3l9Mud8WV3nsJEdLcpIk/v2/JB9L8os1HPr5klwpyR22uMa57odKctLyd7wk505yrCS/SXK9JL+dG+AA8P25klwtyQOS/H7JfvZEcQ6W5FJJrpzknElOPDDRd5J8JMkjknxzyUKaNgcpG7hJkjsmefmK/Vdtfrskt0ly+GIEtf8biuIyhgO6HDOJ/drrrZN8dm7DqyoOa3SZlIZ8Jclrknw1CWWhuecv2uv7nyS56wqXf+gyHoW8b5Inz21gDd8zhCMWpbGXk5Ux757kUWsYf/8yxFGTvCzJcZPcNMmHpxa+iuLcLcm9S+z/c/n3S4tLb+fgMe6T5P7lwz8luXyS98+coJDx1iRnKsr2rG0+ceH2c0kOW+Y9Q5IvbvMa9vV0lOcVSc6W5CJJPjm2oCWKow3L58LI15Nw7++Z2CVw+eIklyltPp/k0kl+NtLnkEneXrzV45PcaR+coND47DLvl8vB/XIfrGNfT3maJK8ri7hGMabd1jSnOL7/QBJAlfA0V5xRmjrJDZI8v5mRx3r0yKlop/0nklwsCS+13fKiJNctk/Kk19nuBeyg+W6W5JlJPprkckMJwpziPD3JLZoNyTJ4kiVyliSfbhq+t4Ssv3SdKcwTSwiURb1+yeBrbnPkEibPXsa9eZLtDpVr3tKWhhOu35jkgiXBuWc/2pTiCBePbTq40Ksm+c/CJcEMH0oCsZOfF/D8/aa/VP5dSU6f5H1JLpnknwvHX2cz7vnjSQ5TvCoF+to6J9gfjnWjJM9N8sckFy/RYHMbY4rj4MQ5fAaBTQDc1oPMncUpBw6/B5x3acLXnmYxQPVfBxZziCSwE15iLqXmVXlXAhBS4N/NbbD53jm28/13hb59U/sxFliwJ0Z04CQSlJ44tUbY829J/r5gfSdI8u7C0XEaosGk4lg0pXF4VXgel7yKyI56PuAcDVKXAsuipN4wzVkXcD64Fv2ElvMmOVUSG+QdUQOE1xCj0QJHSfLtEm6nDsvBXKH0h3Wuv3CjUtdLlD/rOnqSHxWDgefGkoF+eNkMHAlPGMO43yrYgtUjVYcEs26P5j5zITGdCe6sDS/OAiQ4YyFmH1OiwdQ2KeCbCmfnfjgTidGGDHkcmvXaZkQhxsQ2sorgevAirVy0AdbGBLyJLMZ3GOcxuWyShyZhkS3p+N2yPpwRxXph8Y7tODI2oH6ofOGiWNZpSwfZlcuakiMVZb16Sd+RlF9K4nMKeJ4k30ty2yRvmxlLe9QFb2wvMOSvilHIZF3am4syHjTJM0rY5z1eUDzCqbs5QIp69k9IcsOCIWszCg2/zJGzD09yj9LJ2aNZBhWHtVrkBZqFYBQd+qryoELitf0A5uqFpN21nPDKJNeewU8AG+uGR8Tf45SBawYEU8FLFB1e4fHqPr5QrJk36MWFoQvIEiM5XZKnldIEb3bNzrPaozM8RlEEFzQ0r/n0FSIp/DsL5UF5CGKSwl+oWbCQyzNh5Q9UvK71SJuRr0R/fdTZnlK8J49qb8jYKjwQI5uSGyd5TmkAg4IrQuhuHqf1AnVAXIyQsopwc/oAVVXacORQoHaKQHaLoROTCVMyNICa8BAuitL8tFzGH4pSUk6CyJPmD/EyaIJHlnY8oHAxRgdglXkQHg9T7mAlAK3AFxhYVk+eV9r1W+JBKT2D4AHM+5mu0auacVycffKG/frwT86BOAfnytPYM6+l74mKUtUpEHzOcUoQgZUEtEb6wVh2U5ynJrlVMxL3C+u4kFVEwfODXUjB0VBCxUPhwQZZC5GOLy1m6lMZXVbEAimIC6CoFcs4uNuX8Vmui+ozQlbLpVePav/qVkMCQ7jok5eLk7KP1dGwr8IYoQzWCJRWsVbGcuHygfCE6mjF2kCGir1eneRaSf7dtWtTZ18B+vYJ4xgTF0Naz0oJrInyT0l71tptQo0W44jPbylgtQ62p4U+Mb6vdSD5hBjCYt9R4rP/FzvF0CXSeghjKBOwVu4ZNiA8GoWgLOQhA2HT572Cw2WVNW3XAk8IJSyQ8Jb1QofWbIyqjMIk1rw1PnjKhdbyhrbOup/TOEIdoUS8WJ8hnqKUc4RGhoTV50GdKc9XhWFWD8yzOpuNsDMhXg202PbOSR6nfas43DAvYQFV9jRF7j2X8drDsdlNhJ7kXkkAsTnpQyCgCMw70DZkyEq4YRsnsgkX2AsMVGtoQzxTbc96H1b+h7XynBR2SABYnqgtBHPx7fOMNgFxecIuMN1Kz4ONlWIUJCtZCfswmk8VYN6O14Y92AdwnxM60QJotcqNc2gVhyvuY6wUzCJWEZfmMtrMR13L5da3HrKAmj4bG2iTIs6J9zLitbEd+A+KZ/GOpBVKWj3HVN2Jl6O0RDhzoX3afvxCflWDmksWkJr2W7M0IQbw/1ezwBY7AOZAZw+geYwHlz68FSXfwBedCHO1PCKEyxzhlxYHWTtoUNe0BN+YBi7i1asBwlcbWKpVnPaw69pYApyzioj9PEErsgdxv0rvcTY1eWYiG5Y6E6UL7C6c0INFRdmKVV7S1KDa4XEgcEblq3i8qkRtuzY0+lxYBFLHxOXgXWSoZChMtspo7Yy2VQqGQZHrhXnKArP10ivpr8v6ZJWttJyarGsq02v7mZ9nrXvx1MV+dlEcRFxLNLFoG1qFv8HUOtQK+swhu+K2Ww7lhMUCuGOyNFS1CqHfUMbXg0WuvKaU7aEgDnmG6hmtmTdrhdvnYapyOXSW/+MJxXHJGzhgpnyBUOVVpOI8JlzCK2HrWTYgiu53UWPFYSG4DZmbHqFbnzEYJ4HVYK4lpSOJwDeasTbvqfU4/SIojLSurS1NnNfGV711jpUqsJ0uqbpOfAJeYUp6hRAOra+n5W1WyGUlU7xM62HHrBBXhD11NmQsO6vr7nkw4fIqEyWP+soRSAcJeFEGLOu0PwooYRkToayScjwXDqk39J76WAW39hhnkxxtFae3QIvVcSiuDm2EWwNQKxawEelw+7Si9utTzTncoB+FkA3U8ccY3vZdjfa8Ul+RN17rvcRxWYZU10FXZWyVUJ+pdN33XkjieTx0ZzQyrymM+MBSHqGQwLvwaQ2MigK0KXx/5r1C2IMnvX3W1dacjFHhh0Rjzuv0ZaPNJKNVHIuWwtbHVyYZShOHlIYiYH9ZV5Wp9zfaOLT7lcasCnieqie12QP+Qfo9xMhy1zXtZ7FSSAJAwlkuxhNVc1ZmucUhtyxEofR31FUPHEJ9wVjH5A3q/obODHcldQZo7WXVR/G9oSMjkY29AN411QdFGIi5eDb/nSo7WFclCTkQ4XzjzPtalYuXBVSZs7DarrVenobS9AC531ALIgFw1qLeNCZt9mCNXuX3glUWWir9buNcPkVSCAWuhS/YCs9UvVe1Qv0onnPwjtr3+BbZBYFL2qcm7fz1GYLPxgB5ba9s4hIrj2NOWaXsCa5ZIm1Kb08KyLLMXtrSTsVAiD0cj9KJvzER1vzggGgvO9yQXnFwELTTJRIboaFjnIWYbsMyKUIrWdqSx14ODQZwmcRhuqwhkT1YFyshY4DXUw4UubGthfVjk22e5WGviRBSH4wJEfYL2CP2ZC+1yMmdO7CqpEC2uXuRadmzEDWHg/QFAdTsarbiMwZnfZ6u8IxohCnBxdTnvGOA156MZX1EpmmPMCVPN/dEVxSpe28Lp4PVcZsRYz1zIFwZlyrF8+7FswuuXkoHw7hMVqKP8DNEtI0dQBt+xthdfVvgzrow07UY2I7d0urqVbgLuENGoZJcxbpremt/CDQHw7v0z0fEedjNnhmSSrNxibqU0gLFrJV5Yy95j1ND1dDZOE+GgqQb8kDmoviVVVZm8NSzF9UA91Lrerwv5Vazq85h7G5aY6XEvLd0f0PGHnKZUKiRtbBei+cNpKEyIiQfd89KpLQuRYhYVbxD0Z/rtEHebehRFq9WsYr22g3hIakskFizNesDlrGmrXizwrprqLA/IH6sXkZRVbF5RfhKaKVELoRiGetJC89ABiV8MEyMNCXgDSl9fS1Z1+qihaT+R3IIVKC7PmKTTbVMfLvX1jP53FnUOtrUfXnvVNn4zVLDnOJUpWKtJkFY4V5YEkBF84QEHA2LXWJhY4tscdXYm2MK4Y+iU96pB1J4GS6ZMshwxn7ioXIMUPJclK2vcvfrVa+SLPCw/o2X4l15H2MMKXw/BuabMuBrYKLKmwmJvjO+R2S1+Kv/EM6UUdU2Mq+xEK+/sUGJmvXWH95NKU2b9TpD4WqXzHTusXodXKz0RxzYUHq7qrdplZcVUCCXDPPMFd/2dK592Y/xUTJeZep3ZgC+h121luRMEHZeFWyXCGOwHWMYpBSWKs7eXrDwh3GWGSytW+3tNa17/Eo/qNF50jD1prll4IFYijOVca5zrbCNso4IQ3kHH3vtFMWxcZmGjIQSCTVLMrN1HtjeHqtWp+Eh5YQ5r1ozGjwKq59rv471C4GURjIyhA0359hJitMqj7iNC5p7r7uOw9quMZBzMrJdiLSRydu3UVLm+o5mb64VAYx/Ql9IEobIxB2rOBYGA0iPZQpY3P6B0948vL05Ni7FxcjkZKwUYqikwON67uGXGpIP/baSfCzZE/6OZ5PhIf0kC5Oy0zxOXSztx4dIf/snlXN72snfuxScEuWRxQlHCrJoAwVV73Q8PAekZVOq0XO/CVvHfr1ekDnxNIt+0rNTFaceBtJtnRncOg55q2OgOOAHdTBknEo4ikPBEWDGz2Cop1Lsra5hy/13uuJseYM7eABhgecBSIUiNAeib6oivmO283+Q1UBSkQ6/9gAAAABJRU5ErkJggg==" style="margin-top:0;margin-bottom:0;"></span></span></span></li></ul>
<p><code>static void buddy_init_memmap(struct Page* page, size_t n)</code> do this work in uCore. If <code>mem_init</code> equals false, which means <code>Buddy* mem</code> has not been initialized, let <code>mem</code> point to a continous memory block with size of CBT in the front of detected memory, so these memory are be reserved for buddy system. then call <code>buddy_fill(0)</code> to flag all pages as unallocable. </p></li>
<li><strong>The update algorithm</strong> <br>
We have mentiond update many times. Now let’s see this important algorithm who guarantee a buddy’s allocable info is always right.Each buddy has its left tree and right tree, we can set buddy’s left/right field as allocable(left tree/right tree). what is allocable size of a buddy? If this block is totally free, which means no pages is allocated in this block, the allocable size is just the size of this buddy. else the allocable size is maximum of allocable(left tree ) and allocable(right tree) . When an allocation or a free happend in a buddy, the allocable size of his ancestor might be changed, update ancestor’s left and right field iteratively until reach root. <code>static void update(int i)</code>do this work in uCore.</li>
</ul></div><div id="wmd-preview-section-footnotes" class="preview-content"></div></div></body></html>