# HG changeset patch
# User Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
# Date 1403600826 -32400
# Node ID 105ba499ae4012a320307865a336c36cc62818c2
# Parent  3488934d6d2312e1a702d5185183c21f7d3e1f34
commit

diff -r 3488934d6d23 -r 105ba499ae40 s6/.DS_Store
Binary file s6/.DS_Store has changed
diff -r 3488934d6d23 -r 105ba499ae40 s6/blank.css.less
--- a/s6/blank.css.less	Fri May 09 11:17:10 2014 +0900
+++ b/s6/blank.css.less	Tue Jun 24 18:07:06 2014 +0900
@@ -71,7 +71,7 @@
 
 
 p, li, dt, dd, td{ font-size: @font-size-text; }
-th { font-size: @font-small-size;}
+th { font-size: @font-small-size; font-weight:normal; align:left}
 
 
 pre {font-size: @font-size-code; }
diff -r 3488934d6d23 -r 105ba499ae40 s6/blank.html
--- a/s6/blank.html	Fri May 09 11:17:10 2014 +0900
+++ b/s6/blank.html	Tue Jun 24 18:07:06 2014 +0900
@@ -137,7 +137,7 @@
       <div class='slide'>
         <h2>進捗</h2>
         <dl>
-          <dt>s6 Slide整えて遊んでた</dt>
+          <dt>Scalaで遊んでた</dt>
           <dt>mallocのお勉強</dt>
           <dd>kernel reading party(小崎さん)</dd>
           <dd><a href="http://shelby.tv/video/youtube/0-vWT-t0UHg/the-67th-yokohama-kernel-reading-party">動画</a></dd>
@@ -146,9 +146,9 @@
       
       <div class='slide'>
         <h2>mallocってなんだっけ……？</h2>
-        <img src="images/malloc.png" width="500">
         <pre class="code">
           void *malloc(size_t size);</pre>
+        <img src="images/malloc.png" width="500">
         <ul>
           <li>mallocはsizeバイト分のメモリを割り当て、ポインタを返す</li>
           <li>返ってくるのはvoidのポインタなので、戻り値を型でキャストする必要がある</li>
@@ -160,7 +160,7 @@
       </div>
 
       <div class='slide'>
-        <h2>古典的malloc</h2>
+        <h2>古典的malloc(K&R malloc)</h2>
         <img src="images/heap.png" width="700">
         <ul>
           <li>使用可能なブロックを繋げたリスト構造、free list (freeされているブロックのlist?)
@@ -228,7 +228,7 @@
       
       <div class='slide'>
         <h2>free</h2>
-        <img src="images/free3.png" width="700">
+        <img src="images/free_after.png" width="700">
         <p>チェックに引っかかったところをマージする。</p>
       </div>
       
@@ -236,12 +236,12 @@
         <h2>古典的malloc & freeまとめ</h2>
         <p>フラグメンテーションが頻発する。</p>
         <ul>
-          <li><p>このmallocが主流だった時は「メモリはプログラムの最初に一気に確保するもの」だった</p></li>
-          <li><p>メモリが充分に空いている状態で、
-              必要なメモリを一気に確保するならフラグメンテーションは起きにくい</p></li>
-          <li><p>今はJava・C++のようなオブジェクト指向言語、
-              Rubyのようなスクリプト言語等、小さいmallocが頻発する</p></li>
-          <li><p>それをfirst fitでやるのはよくない</p></li>
+          <li>このmallocが主流だった時は「メモリはプログラムの最初に一気に確保するもの」だった</li>
+          <li>メモリが充分に空いている状態で、
+              必要なメモリを一気に確保するならフラグメンテーションは起きにくい</li>
+          <li>今はJava・C++のようなオブジェクト指向言語、
+              Rubyのようなスクリプト言語等、小さいmallocが頻発するものが多い</li>
+          <li>それをfirst fitでやるのはよくない</li>
         </ul>
         
       </div>
@@ -250,8 +250,100 @@
       <div class='slide'>
         <h2>mallocの改良</h2>
         <p>そもそも、一つのfree listで管理することが無理がある</p>
-        <p>サイズ16用のリスト、サイズ24用のリスト……というようにリストを複数作ってやる</p>
-      </div>      
+        <p>サイズ16Byte用のリスト、サイズ24Byte用のリスト……というようにリストを複数作ってやる</p>
+        <table border="0">
+          <tr>
+            <th>
+              <img src="images/free_list_list.png" width="400">
+            </th>
+            <th valign="top" align="left">
+              <ul>
+                <li>mallocで要求されたsizeを8で割れば自分が使用するindexとなる</li>
+                <li>無限にリストを増やすわけにはいかないので、このリストを使うのは512バイト以下の場合のみ</li>
+                <li>512バイト以上の大きいデータの場合は、特殊な管理を行う</li>
+                <li>大きいデータと小さいデータを一緒に管理するからフラグメンテーションが進むんだ<br>
+                  →大きいデータ用の領域がもう一個欲しい<br>→そうだ、mmapを使おう</li>
+            </th>
+          </tr>
+        </table>
+      </div>
+
+
+      <div class='slide'>
+        <h2>mmapってなんだっけ……？</h2>
+        <ul>
+          <li>ファイル(fdで指定したもの)をメモリにマップする</li>
+          <li>fdで&quot;/dev/zero&quot;を指定することでmmapをメモリ確保APIとして使用</li>
+          <li>このAPIを使ってHuge Blockはmmapで直接kernelから取得する</li>
+        </ul>
+        <pre class="code">
+          void *alloc_mmap(size_t size) {
+              int fd    = open("/dev/zero", O_RDONLY);
+              void *ret = mmap(addr, length, prot, flags, fd, offset); 
+              return ret;
+          }</pre>
+        <table border="1" >
+          <tr bgcolor="dbffa3">
+            <th align="left" style="margin:10px 10px 10px;">addr</th><th align="left">mapするメモリアドレス。NULLを渡せばkernelがアドレスを選択する。</th>
+          </tr>
+
+          <tr bgcolor="palegreen">
+            <th align="left">length</th><th align="left">addrから何バイトマッピングするか。</th>
+          </tr>
+
+          <tr bgcolor="dbffa3">
+            <th align="left" >prot</th><th align="left">マッピングのメモリ保護の指定。Read Write Exec None等がある。</th>
+          </tr>
+          <tr bgcolor="palegreen">
+            <th align="left">flags</th><th align="left">マップを要求された時、共有するかコピーを渡すか。</th>
+          </tr>
+          <tr bgcolor="dbffa3">
+            <th align="left">offset</th><th align="left">ファイルの何バイト目からをメモリにマップするか。</th>
+          </tr>
+        </table>
+      </div>
+
+      <div class='slide'>
+        <h2>Huge Block</h2>
+        <p>mmapで確保するので、free listからは独立している。
+        <table>
+          <tr>
+            <th>
+              <img src="images/huge_block.png" width="500">
+            </th>
+            <th valign="top" align="left">
+              <p>
+                listを使って管理しているわけではないので、listをたどったりしなくて良い。</p>
+              <p>
+                ほしかったらmmapして、いらなくなったらmunmapすればよい。
+              </p>
+            </th>
+          </tr>
+        </table>
+        <ul>
+          <li>free list上でフラグメンテーションが起きにくくなった(当たり前)</li>
+          <li>メモリの無駄が少ない<br>
+            大きなメモリは同じサイズでもう一度mallocされる可能性は低いので、
+          使わなくなったらすぐOSに返却するのは正しい</li>
+        </ul>
+      </div>
+
+      <div class='slide'>
+        <h2>まとめ</h2>
+        <ul>
+          <li>一見危なそうに見える処理が……</li>
+          <li>HugeBlockをmmapで管理すれば確かに手っ取り早いではあるが、何バイトからをHugeBlockとするかをちゃんと考えないとだめ</li>
+        </ul>
+        <h2>次やること？</h2>
+        <ul>
+          <li>AVLTree</li>
+          <li>2-2n allocator</li>
+          <li>mallocのソースを読む</li>
+        </ul>
+      </div>
+
+
+
     </div> <!-- presentation -->
   </body>
 </html>