Article 3996 of fj.unix: Path: news2.sra.co.jp!katsu From: katsu@sra.co.jp (WATANABE Katsuhiro) Newsgroups: fj.comp.oops,fj.comp.lang.implementation,fj.unix Subject: Re: garbage collection Date: 7 Oct 1998 07:34:54 GMT Organization: Software Research Associates, Inc., Japan Lines: 129 Message-ID: <6vf5iu$mhu$1@sranhh.sra.co.jp> References: NNTP-Posting-Host: sras49.sra.co.jp In-reply-to: MAEDA Atssi's message of 27 Jul 1998 04:14:40 GMT Originator: katsu@sras49 Xref: news2.sra.co.jp fj.comp.oops:1722 fj.comp.lang.implementation:27 fj.unix:3996 あまりのフォローの遅さが議論の妨げになっていたらごめんなさい。 GC や記憶管理一般でなく、malloc(3) の BSD における変遷のみに 焦点を当てて議論してみます。 記事 で MAEDA Atusi さんいはく > サイズ別のフリーリストを作る方式(segregated free lists schme)のすべて > がbuddy block systemではありませんが、昔4.X BSDについてきたいわゆるbsd > mallocは確かにbuddy systemを使っていました。bsd mallocは割り付けが大変 > 高速なことで知られていますが、空き領域をまとめるということを決してしな > いので、フラグメンテーションがひどいことでも知られています。 色々な論文(前田さんがご紹介の、IWMM'95 [1] や Grunwald の論文 [2]) には、確かに (4.2)BSD は buddy block system と書かれていますが、 これは「4.X BSD」一般ではなく、4.2BSD に限ったことでしょう。 4.2BSD から 4.3BSD の間に、malloc(3) は大きく書き換えられました。 正確な資料は捜し出せませんでしたが、私の知識では 4.3BSD malloc は (a) segregated free lists scheme である。2 の冪乗のブロックサイズ を基本に据えた strict segregated fit に類似。 (b) ある程度大きな(1/2 page を越える)領域を確保するときは、 (2 の冪乗 + 1) * pagesize の block を確保する。 (c) coalescing しない。 でした。(b) の意味を例示すると、pagesize(1) が 4096 を仮定すれば、 malloc(2048 ぐらい) 1+1 pages = 8192 bytes の block を確保 malloc(8192 ぐらいより大) 2+1 pages = 12288 bytes の block malloc(12288 ぐらいより大) 4+1 pages = 20480 bytes の block malloc(20480 ぐらいより大) 8+1 pages = 36864 bytes の block という感じになります。（「ぐらい」は header 分を意味。） 性質 (b) のように 1 page の張り出しがあるため、大きいブロックは 単純に split することが能わず、buddy block system にはなり得ません。 （大きくない block も split しません。）この 1 page 分の張り出しは 何かというと、2 の冪乗の大きさのブロックが malloc される確率は 高いと考えて、internal fragmentation （すなわち、 block_size - header_size - (malloc の引数)）を小さくしようとした 最適化と思われます。"Bug Fixes and Changes in 4.3BSD" [3] には SMM> malloc Malloc underwent a major rework. Memory SMM> requests of page size or larger are always SMM> page aligned, and are now optimized for sizes SMM> that are a power of two. The debugging code SMM> has been improved. という記述があります。２の冪乗サイズの最適化については man 3 malloc でも言及してます。4.3BSD を元にした ASCII UX/4.3BSD(pagesize 1024), NEWS-OS 3.X,4.X (pagesize 4096) の malloc の振舞いは、(b) を 持ち出すとうまく説明できたものでした。例えば、malloc(3) の振舞い をメモした記事 [4] は、私が NEWS-OS 4.0C を使っていた頃に書いた ものです。 4.4BSD 系の malloc は 4.3BSD と同じだと思います。NetBSD, OpenBSD 等はこれを引き継いでいることでしょう。 SunOS, Solaris には bsdmalloc(3X) ライブラリが存在して、標準の malloc(3) の代わりに 4.3BSD の malloc が利用できます。もちろん、 上述の２の冪乗サイズの最適化等の振舞いを観察することができます。 （Solaris の man 3 malloc は、BSD malloc と標準のものを比べて、 "better performance" だが "space inefficient" と評しています。） 4.4BSD (Lite-2) の子孫のうち、FreeBSD では、RELEASE-2.2 以降から phkmalloc というのが採用されたそうです。これは、最近の仮想記憶 システムの事情を考えて、paging をなるべく抑える戦略のようです。 逆に、mmap(2) が必要なため、古いＯＳには移植できないそうです。 phkmalloc は、page 単位の割り当てと page 未満の割り当て戦術が 別になってます。前者は、address-ordered first fit で、split や coalescing あり。後者は、2 の冪乗サイズのブロックで、segregated free list と bitmapped fits を併用しており、coalescing しません。 その他、page directory というので page 群を管理してて header は データブロックに隣接してないとか、適当な chache 分を残して 空きブロックを sbrk() でＯＳに返すとかの特徴があります。 詳しくは、論文 "Malloc(3) revisited" [5] を参照してください。 記事 で suzuki@otsl.co.jp (SUZUKI Hisao) さんいはく > >mallocは確かにbuddy systemを使っていました。bsd mallocは割り付けが大変 > >高速なことで知られていますが、空き領域をまとめるということを決してしな > >いので、フラグメンテーションがひどいことでも知られています。 > > ここにちょっと疑問があります。「空き領域をまとめるということを決 > してしない」というのは，ただ compaction をしない，ということでは > なく，buddy system での coalescing も全然しない，ということなの > でしょうか ?_? まず、GC や記憶域管理一般ではなく malloc(3) に限った話をしますと、 compaction（使用中の領域を移動して詰めて大きな空き領域を作ること） をするような実装は、malloc ではありえません。 次に、coalescing（隣接する空き領域の融合）については、4.[234]BSD の malloc では全く行ないません。malloc 内で brk() が失敗した時ぐらい、 時間をかけて coalescing やってもいいんじゃないかと私は感じましたが、 実際はそのまま malloc をあきらめていました。 参考文献： [1] Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles, "Dynamic Storage Allocation: A Survey and Critical Review", Proc. 1995 Intl. Workshop on Memory Management (IWMM'95), LNCS 986, (ftp://ftp.cs.utexas.edu/pub/garbage/allocsurv.ps) [2] Dirk Grunwald, Benjamin Zorn, and R. Henderson, "Improving the Cache Locality of Memory Allocation", SIGPLAN '93, Conference on PLDI, June 1993, (ftp://ftp.cs.colorado.edu/pub/techreports/grunwald/PLDI-93-locality.ps.Z) [3] "Bug Fixes and Changes in 4.3BSD"; Marshall Kirk McKusick, James M. Bloom, Michael J. Karels; 4.3BSD UNIX System Manager's Manual(SMM); April 15, 1986; 4.3BSD 由来のシステムならば、/usr/doc/smm に roff 原稿がある。 [4] Subject: Re: BSD malloc(3) and Swap Space; Message-ID: (SRA 社内のみ流通); 渡邊克宏; http://www.sra.co.jp/people/katsu/article/104.txt [5] "Malloc(3) revisited"; Paul-Henning Kamp; (http://www.freebsd.org/~phk/malloc/malloc.ps.gz および、 このページ近辺の若干の情報) -- 渡邊克宏＠ＳＲＡ