Heap入門/mallocとfreeの構造,処理,仕組み

[+]Heapの構造について

allocate_chunk{prev_size, size, data}

free_chunk{prev_size, size, fd, bk, free_space}

f:id:ta1se1_sec:20170703183333p:plain

①allocate_chunk{prev_size, size, data}をfreeすると、dataの先頭4バイトがfd、次の4バイトがbkになり、残ったdataがfree_spaceになる。

②各チャンクにおいて、直上チャンクがallocateチャンクの場合、prev_sizeが直上チャンクにuser使用域として奪われる。(ヒープ領域としては自身のモノのまま)

f:id:ta1se1_sec:20170703183445p:plain

つまり、①と②を考慮すると、freeするのに必要な最小構成は

allocate_chunk{prev_size, size, data(fd,bk)}

の4*4バイトとなる。

dataが最小8バイトで、freeするとそれがfd+bkに分解される。

 

[+]freeについて

allocateチャンクがfreeされると、binsのインデックス0とインデックス1に存在するunsorted binにまずは繋がれる。

そして、そのチャンクのsizeごとに振り分けられたbinsに繋がっていく。

具体的な種類としては「small bins」「fast bins」「large bins」などがある。

small binsは8バイトごとにサイズ分けされているため、チャンクをsmall binsに繋ぐ際には、そのチャンクのsizeを8で割った値をインデックスにすれば対応しているbinsのインデックスを特定することができる。

先程述べたように、ひとつのチャンクの最小サイズは16なので、最小サイズのチャンクを格納するsmall binsのインデックスは16÷8で2となり、small binsのインデックス0と1はsmall binsとして使用されない。

ここは時系列順で繋がるunsorted binとして使用されている。

large binsにおいてもそれは同様である。

f:id:ta1se1_sec:20170703183509p:plain

freeチャンクはそれぞれfdとbkという二つの要素を持っており、fdには先頭チャンクのアドレスが、bkには最後尾チャンクのアドレスが格納されている。

先頭チャンクのbkと最後尾チャンクのfdは自身のサイズの管理を担当しているインデックス-1をインデックスとするbinsのアドレスが格納されている。

fast binsにもfd/bkメンバは存在しているのだが、 fast binsはbkメンバを用いない、単方向リストとなっている。

 

[+]Unlinkについて

・XチャンクとPチャンクが隣り合っている場合

・X->sizeのPREV_INUSEが1か(Xの直上チャンクがallocateチャンクか)確認

・(P+P->size)->sizeのPREV_INUSEが0か(Xの直下チャンクがfreeチャンクか)確認

・P->sizeのPREV_INUSEが1か(X自身がallocateチャンクか)確認

・P->fd->bk = P->bk(つまりP->fd+8 = P->bk)

・P->bk->fd = P->fd(つまりP->bk+4 = p->fd)

 

参考/画像提供 : http://www.valinux.co.jp/technologylibrary/document/linux/malloc0001/

英語の技術文献を読んでいて遭遇した難しい英単語/英熟語備忘録

What’s this?

私が英語の技術文献を読んでいる時に遭遇した、その場で意味がわからずに調べた英単語/英熟語の意味をメモしていくページです。
個人的にわからなかったものをまとめていくので、簡単なものも多く含まれていると思われますが、ご了承ください。

List

英単語 和訳
retrieve 検索する
incompatible 非対応な
implict 暗黙
identical to A Aと同じ
except that A A以外
A call コール/呼び出し
A call to flock() flock()のコール
英文 和訳
the buffer pointed to by buf bufに指されているbuffer
No permissions are required on the file itself, ファイルそれ自体には権限は必要とされていない
fstatat() are described below. fstatat()については後述します。
it returns information about the link itself, not the file that it refers to 参照しているファイルではなくリンク自体の情報を返す。
the file about which information is to be retrieved is specified by the file descriptor fd. どの情報が検索されるかについてのファイルはファイルディスクリプタfdに指定されています。

radare2 コマンド一覧

  1. #実行  
  2. r2 -d a.out  
  3. r2 -d a.out 100 hoge fugafuga  
  4.   
  5. #解析  
  6. aaa  
  7.   
  8. #進数変換/計算  
  9. ? [expr]  
  10.   
  11. #関数列挙  
  12. afl  
  13.   
  14. #imports  
  15. iiq  
  16.   
  17. #Exports  
  18. iEq  
  19.   
  20. #symbols  
  21. isq  
  22.   
  23. #sections  
  24. iSq  
  25.   
  26. #reloc  
  27. irq  
  28.   
  29. #strings  
  30. izq  
  31.   
  32. #xref  
  33. ax [addr] (このアドレスを指すポインタ検索)  
  34. axt [addr] (addrを参照するデータの検索)  
  35. axf [addr] (addrから参照されるデータの検索)  
  36. (ex)  
  37. axf [.text_addr] (.text_addrを使うaddrの検索)  
  38. axf sym.imp.printf (printfが参照されてるaddrの検索)  
  39. axt sym.imp.printf (printfを参照してるaddrの検索)  
  40. axf str.Enter_the_password (  
  41. axt str.Enter_the_password (str.Enter_the_passwordを参照するaddrの検索)  
  42.   
  43. #メモリ上書き  
  44. #シークしてるところで(下)  
  45. wa jmp eax (機械語生成)  
  46. 'hello'  (文字列生成)  
  47. wx 90 90 90 90 (バイト生成)  
  48. wf tmp.bin (ファイルからインポート)  
  49.   
  50. #registers  
  51. dr  
  52.   
  53. #memory map/vmmap  
  54. dm,dmq  
  55.   
  56. #シンボル  
  57. dmi  
  58.   
  59. #現在のシンボル  
  60. dmi.  
  61.   
  62. #ヒープ情報  
  63. dmh  
  64.   
  65. #バックトレース  
  66. dbt  
  67.   
  68. #p system  
  69. dmi* libc system  
  70.   
  71. #レジスタ  
  72. dr / dr [register]  
  73.   
  74. #前のレジスタ  
  75. dro  
  76.   
  77. #レジスタ書き換え  
  78. dr eax=0xhoge  
  79.   
  80. #seek(見たいアドレス位置の変更)  
  81. s [addr]  
  82.   
  83. #seekをひとつ進める  
  84. s++  
  85.   
  86. #seekをひとつ戻す  
  87. s--  
  88.   
  89. #seekを進める(?)  
  90. s >> (?)  
  91.   
  92. #seekされている位置からの逆アセンブル  
  93. pd [num]  
  94.   
  95. #関数の逆アセンブル  
  96. pdf  
  97. pdf @関数名  
  98.   
  99. #checksec  
  100. iI  
  101.   
  102.   
  103. #break point  
  104. db [addr]  
  105.   
  106. #step into  
  107. ds  
  108. ds [num]  
  109.   
  110. #step over  
  111. dso  
  112. dso [num]  
  113.   
  114. #back  
  115. dsb  
  116.   
  117. #フレームの終わりまでステップ  
  118. dsf  
  119.   
  120. #snapshot系(?)  
  121. dms(?)  
  122.   
  123. #step until addr  
  124. dcu [addr] / dsu [addr]  
  125.   
  126. #callまでステップ  
  127. dsui call / dcui call(?)未確認  
  128.   
  129. #visual mode  
  130. V  
  131.   
  132. #graphic mode  
  133. VV  
  134.   
  135. #mode change (visual/graphic)  
  136. p  
  137.   
  138. #step into (visual/graphic)  
  139. s  
  140.   
  141. #step over (visual/graphic)  
  142. S  
  143.   
  144. #functions menu (visual/graphic)  
  145. v  
  146. (Usage command)  
  147. m: function name edit  
  148. x: xref(crr_seekのみ)  
  149.   
  150. #メモリ解析  
  151. #基本  
  152. pf [解析数][option] [addr]  
  153. (Usage Options)  
  154. i: int  
  155. b: 1byte  
  156. c: char  
  157. w: 2byte  
  158. x: 4byte  
  159. q: 8byte  
  160. p: pointer  
  161. s: 4byte strings  
  162. S: 8byte strings  
  163. z: nullまで(4byte_addr)  
  164. Z: nullまで(8byte_addr)  
  165. D: disass  
  166. (ex) pf x 0xaaaabbbb  
  167. (ex) pf 3x @0xaaaabbbb  
  168. (ex) pf 10s @esp <- 神  
  169. (ex) pf 10xs @esp  
  170.   
  171. #バイナリ表示  
  172. px[option] [addr]  
  173. (Usage Options)  
  174. default: hexdump  
  175. w: 4byteのpx  
  176. q: 8byteのpx  
  177.   
  178. #文字列表示  
  179. ps[option] [addr]  
  180. (Usage Options)  
  181. default: 機械語で表示)  
  182. b: めちゃ有能  
  183. i: 文字化けで表示  
  184. x: ストリームで表示  
  185. u: psxのutf16.ver  
  186. z: nullまで  
  187.   
  188. #検索系  
  189. /: 検索  
  190. /c: asm検索 (jmp eax)?  
  191. /a: asm検索 (jmp eax)?  
  192. /A: asm検索(jmp)  
  193.   
  194. ieq: エントリーポイント  
  195.   
  196. #r2 -w: よくわからん  
  197.   
  198. #r2 -n  
  199. p=e よくわからんけど色のゲージ  
  200.   
  201. #rabin2(未整形)  
  202. -qe エントリーポイント?  
  203. -qs [file] シンボル?  
  204. -qi   
  205. -qR  
  206.   
  207. #その他  
  208. s eip (現在の位置)  
  209. ood (-dで開き直す)  
  210. ood AAAAAAAAAAAAAAAAA....  
  211. pm マジック  
  212. pc (byte)  
  213. pcp (pcのつよいばん?)  
  214. pB バイナリ  
  215. R 色変え  
  216.   
  217. narnia2(ウェブ)  

C言語のリファレンスの読み方

C言語は、ポインタ周りを深く理解していないと、リファレンスを読むことすらできません。
今回は、その解説を行っていきたいと思います。
問題のページは、こちら
この中から

int execvp(const char *file, char *const argv[]);  

について解説して行きたいと思います。

  • 定石その1 : constは無視
    constというのは、そのまま「静的な」という意味なのですが、これは、定数宣言の時にも用いられ、ここでは、「関数内で書き換えられることはありませんよ」ということを僕らに教えてくれてるだけなのです。なので、このconstについては意識しなくても、リファレンスの理解は十分可能です。
    すると、こうなります。
int execvp(char *file, char * argv[]);
  • 定石その2 : あすたりすくの位置
    ポインタを表す「*」という記号ですが、これは、変数から離しましょう。
    すると、こうなります。
int execvp(char* file, char* argv[]);
  • 定石その3 : そのまま変数に定義されている型のデータを入れる
    char*型とは、1byteの部屋をもったポインタ型のことです。
    つまり、file変数にはアドレス1(以降p0)があり、そのp0は1byte分の広さがあるということで、
    argv[]配列の中には、それぞれアドレス1,アドレス2,アドレス3,,,(以降p0,p1,p2)があり、それぞれ1byte分の広さがあるということです。

以上の定石3つを適応させると、こうなります。

char *args = {"sh", NULL};
execvp(args[0], args);

char *argsでargsという1byte分の部屋を持つアドレス専用の変数を用意します。
その変数を配列として、{“sh”, NULL}を入れます。
こうすることで、args[0]->p0->“sh”, args[1]->p1->NULLとなります。
これがすんなりわからない方は、普通のポインタ型宣言を思い出すと良いでしょう。
char *pHoge = “hogehoge”;
これは、pHogeという1byteの部屋をもつポインタ変数を用意します。
そのあと、そこに"hogehoge"というデータをもつ先頭番地をpHogeに格納します。(ポインタ型変数宣言時に代入する場合はアドレスでなければならないので、本来はキャストが必要。しかし、警告がでるだけで自動キャストが行われる。)
すると、pHogeにはアドレスが格納され、*pHogeはそのアドレスの中身が格納されます。
この時の"hogehoge"を{“hoge”,“fuga”}という配列の形にすることで、pHogeにはその配列の先頭番地が格納され、*pHogeの中にはその配列の先頭要素が格納されることになります。
つまり、結果的にchar *args = {“sh”, NULL};でargs[0]には"sh"が格納されたアドレス、args[1]にはNULLが格納されたアドレス、argsには配列の先頭番地が格納されることになります。
そのあとにexecvp(args[0], args);でexecvp(“sh"が格納されたアドレス, {"sh"が格納されたアドレスが格納されたアドレス,NULL}); となり、定石3の形と同じにすることができました。
これを実際のメモリ的に考えると、

...  
p0 --> 0x12345678 --> "sh"  
...  
p1+0 --> 0x78  
p1+1 --> 0x56  
p1+2 --> 0x34  
p1+3 --> 0x12  
p1+4 --> 0x00  
p1+5 --> 0x00  
p1+6 --> 0x00  
p1+7 --> 0x00  
...  

この時、
execvp(p0,p1+0)である。

メモリについて

メモリについてのメモ。

メモリは1番地ごとに1byteの空間をもっている。
0x12345678 -> 0xaa
0x12345679 -> 0xaa
0x1234567a -> 0xaa
0x1234567b -> 0xaa
4byte単位で区切った際のひとつひとつを「1語」「1ワード」と言ったりする。
0x12345678 -> 0xaabbccdd
0x1234567c -> 0xaabbccdd
0x12345680 -> 0xaabbccdd
0x12345684 -> 0xaabbccdd
0x12345688 -> 0xaabbccdd
0x1234568c -> 0xaabbccdd
0x12345690 -> 0xaabbccdd

型について

  • char -> BYTE型:1byte
  • short -> WORD型:2byte
  • int -> DWORD型:4byte

配列について

char array[] = {‘a’, ‘b’, ‘c’, 0};
0x12345678 -> 'a'
0x12345679 -> 'b'
0x1234567a -> 'c'
0x1234567b -> 0x00
  • array = 0x12345678
  • array[0] = *(array + 1*0) = *(0x12345678 + 0) = “a”
  • array[1] = *(array + 1*1) = *(0x12345678 + 1) = “b”
  • array[3] = *(array + 1*3) = *(0x12345678 + 3) = 0x00
int array[] = {8, 255, 1024};
0x12345678 -> 0x00000008
0x1234567c -> 0x000000ff
0x12345680 -> 0x00000400
  • array = 0x12345678
  • array[0] = *(array + 4*0) = *(0x12345678 + 0) = 0x00000008
  • array[1] = *(array + 4*1) = *(0x12345678 + 4) = 0x000000ff
  • array[2] = *(array + 4*2) = *(0x12345678 + 8) = 0x00000400

連続宣言時の挙動

  • char arrayA [ ] = {‘a’, ‘b’, ‘c’};
  • char arrayB [ ] = {’d', ‘e’, ‘f’};
  • arrayA[0]: *0x12345678 = ‘a’
  • arrayA[1]: *0x12345679 = ‘b’
  • arrayA[2]: *0x1234567a = ‘c’
  • arrayB[0]: *0x1234567b = ’d'
  • arrayB[1]: *0x1234567c = ‘e’
  • arrayB[2]: *0x1234567d = ‘f’
実はこんなこともできる
arrayA: 0x12345678
arrayB: 0x1234567b
arrayB[0]: *(arrayB + 1*0) = *(0x1234567b + 0) = *0x1234567b = 'd'
arrayA[3]: *(arrayA + 1*3) = *(0x12345678 + 3)   = *0x1234567b = 'd'
arrayA[4]: *0x1234567c = 'e'
arrayA[5]: *0x1234567d = 'f'

実際に配列宣言時のメモリの中身を覗くプログラムをC言語で書いてみた

// memory.c

#include <stdio.h>
int main(void){
    int hoge[] = {111,222,333,444};
    int fuga[] = {555,666,777,888};
    printf("[+] int hoge[] = {111,222,333,444};\n");
    printf("[+] int fuga[] = {555,666,777,888};\n\n");
    printf("hoge   : %p\n", hoge);
    printf("fuga   : %p\n", fuga);
    printf("hoge[0]: %d\n", hoge[0]);
    printf("hoge[1]: %d\n", hoge[1]);
    printf("hoge[2]: %d\n", hoge[2]);
    printf("hoge[3]: %d\n", hoge[3]);
    printf("fuga[0]: %d\n", fuga[0]);
    printf("fuga[1]: %d\n", fuga[1]);
    printf("fuga[2]: %d\n", fuga[2]);
    printf("fuga[3]: %d\n\n", fuga[3]);
    printf("hoge    : %p -> %d\n", hoge, hoge[0]);
    printf("&hoge[0]: %p -> %d\n", &hoge[0], hoge[0]);
    printf("fuga    : %p -> %d\n", fuga, fuga[0]);
    printf("&fuga[0]: %p -> %d\n\n", &fuga[0], fuga[0]);
    printf("&hoge[0]: %p -> %d  (0x%08x)\n", &hoge[0], hoge[0], hoge[0]);
    printf("&hoge[1]: %p -> %d  (0x%08x)\n", &hoge[1], hoge[1], hoge[1]);
    printf("&hoge[2]: %p -> %d  (0x%08x)\n", &hoge[2], hoge[2], hoge[2]);
    printf("&hoge[3]: %p -> %d  (0x%08x)\n\n", &hoge[3], hoge[3], hoge[3]);
    printf("&hoge[4]: %p -> %d  (0x%08x)\n", &hoge[4], hoge[4], hoge[4]);
    printf("&hoge[5]: %p -> %d  (0x%08x)\n", &hoge[5], hoge[5], hoge[5]);
    printf("&hoge[6]: %p -> %d  (0x%08x)\n\n", &hoge[6], hoge[6], hoge[6]);
    printf("&fuga[0]: %p -> %d  (0x%08x)\n", &fuga[0], fuga[0], fuga[0]);
    printf("&fuga[1]: %p -> %d  (0x%08x)\n", &fuga[1], fuga[1], fuga[1]);
    printf("&fuga[2]: %p -> %d  (0x%08x)\n", &fuga[2], fuga[2], fuga[2]);
    return 0;
}
$ gcc -o memory memory.c
$ ./memory

/* ######### 出力結果 ########## */

[+] int hoge[] = {111,222,333,444};
[+] int fuga[] = {555,666,777,888};

hoge   : 0x7fff2df76c10
fuga   : 0x7fff2df76c20
hoge[0]: 111
hoge[1]: 222
hoge[2]: 333
hoge[3]: 444
fuga[0]: 555
fuga[1]: 666
fuga[2]: 777
fuga[3]: 888

hoge    : 0x7fff2df76c10 -> 111
&hoge[0]: 0x7fff2df76c10 -> 111
fuga    : 0x7fff2df76c20 -> 555
&fuga[0]: 0x7fff2df76c20 -> 555

&hoge[0]: 0x7fff2df76c10 -> 111  (0x0000006f)
&hoge[1]: 0x7fff2df76c14 -> 222  (0x000000de)
&hoge[2]: 0x7fff2df76c18 -> 333  (0x0000014d)
&hoge[3]: 0x7fff2df76c1c -> 444  (0x000001bc)

&hoge[4]: 0x7fff2df76c20 -> 555  (0x0000022b)
&hoge[5]: 0x7fff2df76c24 -> 666  (0x0000029a)
&hoge[6]: 0x7fff2df76c28 -> 777  (0x00000309)

&fuga[0]: 0x7fff2df76c20 -> 555  (0x0000022b)
&fuga[1]: 0x7fff2df76c24 -> 666  (0x0000029a)
&fuga[2]: 0x7fff2df76c28 -> 777  (0x00000309)

/* ############################# */