Heap入門/mallocとfreeの構造,処理,仕組み
[+]Heapの構造について
allocate_chunk{prev_size, size, data}
free_chunk{prev_size, size, fd, bk, free_space}
①allocate_chunk{prev_size, size, data}をfreeすると、dataの先頭4バイトがfd、次の4バイトがbkになり、残ったdataがfree_spaceになる。
②各チャンクにおいて、直上チャンクがallocateチャンクの場合、prev_sizeが直上チャンクにuser使用域として奪われる。(ヒープ領域としては自身のモノのまま)
つまり、①と②を考慮すると、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においてもそれは同様である。
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 コマンド一覧
- #実行
- r2 -d a.out
- r2 -d a.out 100 hoge fugafuga
- #解析
- aaa
- #進数変換/計算
- ? [expr]
- #関数列挙
- afl
- #imports
- iiq
- #Exports
- iEq
- #symbols
- isq
- #sections
- iSq
- #reloc
- irq
- #strings
- izq
- #xref
- ax [addr] (このアドレスを指すポインタ検索)
- axt [addr] (addrを参照するデータの検索)
- axf [addr] (addrから参照されるデータの検索)
- (ex)
- axf [.text_addr] (.text_addrを使うaddrの検索)
- axf sym.imp.printf (printfが参照されてるaddrの検索)
- axt sym.imp.printf (printfを参照してるaddrの検索)
- axf str.Enter_the_password (
- axt str.Enter_the_password (str.Enter_the_passwordを参照するaddrの検索)
- #メモリ上書き
- #シークしてるところで(下)
- wa jmp eax (機械語生成)
- w 'hello' (文字列生成)
- wx 90 90 90 90 (バイト生成)
- wf tmp.bin (ファイルからインポート)
- #registers
- dr
- #memory map/vmmap
- dm,dmq
- #シンボル
- dmi
- #現在のシンボル
- dmi.
- #ヒープ情報
- dmh
- #バックトレース
- dbt
- #p system
- dmi* libc system
- #レジスタ
- dr / dr [register]
- #前のレジスタ
- dro
- #レジスタ書き換え
- dr eax=0xhoge
- #seek(見たいアドレス位置の変更)
- s [addr]
- #seekをひとつ進める
- s++
- #seekをひとつ戻す
- s--
- #seekを進める(?)
- s >> (?)
- #seekされている位置からの逆アセンブル
- pd [num]
- #関数の逆アセンブル
- pdf @関数名
- #checksec
- iI
- #break point
- db [addr]
- #step into
- ds
- ds [num]
- #step over
- dso
- dso [num]
- #back
- dsb
- #フレームの終わりまでステップ
- dsf
- #snapshot系(?)
- dms(?)
- #step until addr
- dcu [addr] / dsu [addr]
- #callまでステップ
- dsui call / dcui call(?)未確認
- #visual mode
- V
- #graphic mode
- VV
- #mode change (visual/graphic)
- p
- #step into (visual/graphic)
- s
- #step over (visual/graphic)
- S
- #functions menu (visual/graphic)
- v
- (Usage command)
- m: function name edit
- x: xref(crr_seekのみ)
- #メモリ解析
- #基本
- pf [解析数][option] [addr]
- (Usage Options)
- i: int
- b: 1byte
- c: char
- w: 2byte
- x: 4byte
- q: 8byte
- p: pointer
- s: 4byte strings
- S: 8byte strings
- z: nullまで(4byte_addr)
- Z: nullまで(8byte_addr)
- D: disass
- (ex) pf x 0xaaaabbbb
- (ex) pf 3x @0xaaaabbbb
- (ex) pf 10s @esp <- 神
- (ex) pf 10xs @esp
- #バイナリ表示
- px[option] [addr]
- (Usage Options)
- default: hexdump
- w: 4byteのpx
- q: 8byteのpx
- #文字列表示
- ps[option] [addr]
- (Usage Options)
- default: 機械語で表示)
- b: めちゃ有能
- i: 文字化けで表示
- x: ストリームで表示
- u: psxのutf16.ver
- z: nullまで
- #検索系
- /: 検索
- /c: asm検索 (jmp eax)?
- /a: asm検索 (jmp eax)?
- /A: asm検索(jmp)
- ieq: エントリーポイント
- #r2 -w: よくわからん
- #r2 -n
- p=e よくわからんけど色のゲージ
- #rabin2(未整形)
- -qe エントリーポイント?
- -qs [file] シンボル?
- -qi
- -qR
- #その他
- s eip (現在の位置)
- ood (-dで開き直す)
- ood AAAAAAAAAAAAAAAAA....
- pm マジック
- pc (byte)
- pcp (pcのつよいばん?)
- pB バイナリ
- R 色変え
- 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) /* ############################# */