realloc（および遅延）のストーリー

単純なマクロ

すべては単純なマクロで始まりました：（近似コード）

#define ADD_BYTE(C) do { \ if (offset == capa) { \ if (capa < 16) { \ capa = 16; \ } else { \ capa <<= 1; \ } \ buffer = realloc(buffer, capa); \ assert(buffer != NULL); \ } \ buffer[offset++] = (C); \ } while(0)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Cプログラミング言語に精通していない人のために、この単純なマクロは、バイト（C）を動的に割り当てられたバッファー（バッファー）に追加します。 記録の次の位置は、offsetパラメーターを使用して決定されます。 バッファーがいっぱいになるたびに、ボリュームが2倍になります（最小サイズの16バイトから開始）。



動的バッファにバイトを追加します-これは、ほとんどすべてのプログラムで最も一般的な操作の1つです（文字列、配列などを操作するため）。



しかし、再配布戦略がいかに効果的であるかをどのように理解するのでしょうか？ この問題を複雑さの観点から見て、realloc（）の複雑さをO（N）にすると、1バイトを追加すると平均 O（1）の複雑さがすぐにわかります。これは非常に良いことです。



しかし、最悪の場合の複雑さは何ですか？バッファへのメモリの再割り当てが必要な場合はどうでしょうか？

匿名 ：これは良い戦略ですか？ 大きなアレイ（1ギガバイトなど）のサイズを増やし始めると、深刻なパフォーマンスの問題が発生します。 特に、バッファをスワップファイルから移動する必要がある場合は、結果を想像してください。



私 ：うーん...正直なところ、私はそれについて考えたことはありません...しかし、私はすべてがそれほど怖くないと確信しています。 システムはこのタスクに正常に対処する必要があります。



匿名 ：そして、同じ指数戦略であっても、接続された構造がより良い選択肢であるように思えます。



私 ：いいえ、時間の無駄です。



匿名 ：証拠？

ああ、そうですか？！

さて、あなたは自分の立場を正当化する必要があります。 すべてのプログラマと同様に、私はとても怠け者です。 より正確には：「 プログラマーにふさわしいので 、私はとても怠け者です。」 怠azineは、よりスマートで効率的になるための大きなインセンティブです。 繰り返しのタスクや日常的なタスクを解決するのが面倒です。 もっとインテリジェントなもの 、できるだけ速い ものが必要です 。 はい、それは時々 怠 sometimesと呼ばれるものです。 しかし、私の意見では、これは効率に他なりません。



バッファを保存するためのブロックのリンクリストは、やや面倒な解決策です。 これが不可能だと言っているのではありません 。 「 インポッシブルはフランス語ではない 」ナポレオンはかつて言った（彼はひどく終わったが）。 解決策は可能ですが、面倒です。 サブアレイをコピーしたり、ディスクに保存したりするには多少の手間がかかります。 おそらく、各配列の先頭へのポインタのインデックスを維持する必要があります。ブロックの先頭のアドレスと多くの退屈なものを取得するために、2を底とする対数を取得します。



私の怠lazはここで最も歓迎されることを何かが教えてくれます。 結局のところ、小さなブロックについてはまったく心配する必要はありません。システムの仮想メモリが大きなブロックを処理します。



それを理解しましょう。

ところで、realloc（）とは何ですか？

これは、Cライブラリに実装されている一般的なPOSIX準拠の機能です。 Linuxの場合、これはlibc.soライブラリであり、mallocおよびfree関連の関数reallocも含まれています。

 nm -D /lib/x86_64-linux-gnu/libc.so.6 | grep -E "T (malloc|realloc|free)$" 000000000007e450 T free 000000000007e030 T malloc 000000000007e4e0 T realloc
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

本当に興味がある人のために：「T」は「テキストシンボル」を意味し、大文字はこのシンボルが公開されて見えることを示すために使用されます。 プログラムテキストセグメントはcode 、 データセグメントは初期化データ（変数）、 bssセグメントは初期化されていないデータ（変数）、またはデータ（変数）であり、初期値としてゼロを受け取りました）。



メモリアロケータは、メモリの割り当て、再割り当て、および解放に使用されます（ありがとう、Captain Obvious！）。 そのようなディストリビューターは数多くあります（最も有名なのはバディアロケーターです ）。



素晴らしくひどいsbrk呼び出しを使用して、独自の最も単純なアロケーターを実装できます。これは、データセグメントの最後に空のスペースを追加するだけです。

 #include <sys/types.h> #include <unistd.h> #include <string.h> void *malloc(size_t size) { return sbrk(size); } void free(void *ptr) { /*   ? */ } /* :    (,  ) */ void *realloc(void *ptr, size_t size) { void *nptr = malloc(size); if (nptr == NULL) { return NULL; } // «old_size»    :) // (,      ) memcpy(nptr, ptr, old_size); free(ptr); return nptr; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

[注。 Hacker Newsの読者の一人が正しく述べたように、ここでは、たとえばブロックが選択された後にブロックの先頭に書き込むことができるold_size値が必要です。 しかし、いいえ、reallocでエラーが発生した場合にソースブロックを解放すべきではありませんでした:)]



もちろん、このディスペンサーはもう少し複雑になり、memcpy呼び出しの数を制限するために複雑なデータ構造が必要になります。



大きなブロックで何が起こるかを理解するには、Linux上のGlibcをより詳しく知る必要があります。

Glibcの紹介

最新のglibcをダウンロードして 、ソースツリーを調べるだけです。

興味深いmallocディレクトリが1つあります。 その中のmalloc.cファイルを見つけて、エディターで開きます。

 /*   : *        (>= 512 ),      FIFO (. .    ). *    (<= 64   )   ,      . *    ,        ,          ,   . *     (>= 128   )     ,   .  ,    ,    : http://gee.cs.oswego.edu/dl/html/malloc.html */
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この部分に最も関心があります：「 非常に大きなリクエスト（デフォルトでは128 Kb以上）の場合、サポートされている場合、システムはメモリマッチングを使用します 。」



128 Kbのしきい値はmallopt（）関数によって設定されます。

 M_MMAP_THRESHOLD    ,   ,     ( ),   M_MMAP_THRESHOLD,     mmap(2),          sbrk(2).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そのため、私が言ったように、システム自体の仮想メモリサービスが大きなブロックを処理します。



本質的に、これは次のことを意味します。

• mallocはmmapを使用して実装されます。
• freeはmunmapを使用して実装されます。
• reallocはmremapを使用して実装されます（何？！POSIXにはまだありませんか？真剣に？）

さて、mremapの知識を少し広げてみましょう。



それで、私たちはman mremapについて何を知っていますか：

 mremap()      Linux. mremap()       .  ,     realloc(3).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ええ、 非常に効果的なreallocです。 どのくらい効果的ですか？



最初に、mmap、munmap、mremapがglibcライブラリに記述されています。 実際、エントリポイントのみ：

 nm -D /lib/x86_64-linux-gnu/libc.so.6 | grep -E "(mmap|munmap|mremap)$" 00000000000e4350 W mmap 00000000000e9080 W mremap 00000000000e4380 W munmap
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この場合、デフォルトのエントリポイントは「弱い」文字であることに注意してください。 つまり、動的リンク中に他の誰かによって上書きされる可能性があります。 例：

 ldd /tmp/sample linux-vdso.so.1 (0x00007584a8aaa000) libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007584a86e6000) /lib64/ld-linux-x86-64.so.2 (0x00007584a8aac000
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

...文字はlinux-vdso.so.1ライブラリでオーバーライドできます-これはすべてのLinuxプログラムに表示される魔法のライブラリで、 システムコールを含む一部のコールを高速化できます。

いずれにせよ、glibcライブラリのキャラクターは、システムカーネル（syscall）を呼び出すためのチャネルであり、glibcまたはvdsoになります（デフォルトの実装を参照してください：sysdeps / unix / sysv / linux / mmap64.c）。 例：

 void * __mmap64 (void *addr, size_t len, int prot, int flags, int fd, off64_t offset) { //    void *result; result = (void *) INLINE_SYSCALL (mmap2, 6, addr, len, prot, flags, fd, (off_t) (offset >> page_shift)); return result; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、最初の質問はglibcではなく、Linuxカーネルに関連しています。

コアを知る

最新のカーネルバージョンをダウンロードし、 mremapの仕組みを簡単に見てみましょう。



マニュアル（ The Linux Kernel Howto ）を見ると、非常に興味深いディレクトリが見つかります：

mmディレクトリには、メモリを操作するために必要なすべてのコードが含まれています。 アーキテクチャ固有のメモリ管理コードは、arch / * / mm /という形式のディレクトリに配置されます（例：arch / i386 / mm / fault.c）。

素晴らしい。 それらが必要です！

ここに興味深いファイルがあります：mm / mremap.c。 その中に、mremap関数へのシステムコールのエントリポイントがあります。 ここに：

 /* *  ( )  , ,    * (    MREMAP_MAYMOVE    VM) * *  MREMAP_FIXED  5  1999 .   (Benjamin LaHaise) *     MREMAP_MAYMOVE. */ SYSCALL_DEFINE5(mremap, unsigned long, addr, unsigned long, old_len, unsigned long, new_len, unsigned long, flags, unsigned long, new_addr) {
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

（glibcまたは対応するvdsoチャネルを介して）ユーザーコードで対応するシステムコールを行うときに 、カーネルに入ります。



この関数のコードを学習すると、さまざまな引数のチェックと些細なケースの処理がわかります（たとえば、メモリブロックの削減 -ブロックの最後でページを解放するだけです）。



次に、カーネルは表示領域を拡大して拡大しようとします（sbrkを使用したCライブラリ内のアロケーターも同様です）。 拡張が成功した場合、関数は結果を返します。



これらの些細なケースはすべてO（1）の複雑さで実装されています（カーネルに入るコストを考慮しても、割り込みは使用されなくなりますが、それでも使用されます）。



そして、 最悪のシナリオは何ですか？

  /* *         *       . */ ret = -ENOMEM; if (flags & MREMAP_MAYMOVE) { unsigned long map_flags = 0; if (vma->vm_flags & VM_MAYSHARE) map_flags |= MAP_SHARED; new_addr = get_unmapped_area(vma->vm_file, 0, new_len, vma->vm_pgoff + ((addr - vma->vm_start) >> PAGE_SHIFT), map_flags); if (new_addr & ~PAGE_MASK) { ret = new_addr; goto out; } map_flags = vma->vm_flags; ret = move_vma(vma, addr, old_len, new_len, new_addr); if (!(ret & ~PAGE_MASK)) { track_exec_limit(current->mm, addr, addr + old_len, 0UL); track_exec_limit(current->mm, new_addr, new_addr + new_len, map_flags); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一見すると、カーネルは単純なアロケーターと同じことを行います。

• 新しい領域を強調表示します。
• 元の領域を新しい領域にコピーしてから解放します（つまり、移動操作が実行されます）。

しかし、詳しく見てみましょう。



move_vmaの呼び出しは次のとおりです。

 static unsigned long move_vma(struct vm_area_struct *vma, unsigned long old_addr, unsigned long old_len, unsigned long new_len, unsigned long new_addr) { ... new_pgoff = vma->vm_pgoff + ((old_addr - vma->vm_start) >> PAGE_SHIFT); new_vma = copy_vma(&vma, new_addr, new_len, new_pgoff, &need_rmap_locks); if (!new_vma) return -ENOMEM; moved_len = move_page_tables(vma, old_addr, new_vma, new_addr, old_len, need_rmap_locks);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここには2つの興味深い課題があります。

• copy_vma;
• move_page_tables。

copy_vma関数は、mm / mmap.cファイルに記述されています。 タイプvm_area_structの構造を移動します-これは、メモリのブロックを記述するカーネルの内部構造です。



定義はここにあります：include / linux / mm_types.h。 この小さな構造には、領域に関するすべての情報が含まれます：開始アドレスと終了アドレス、ディスク上のファイル（ファイルを表示するためにメモリ領域が使用される場合）など。



したがって、この移動操作は非常に簡単です-O（1）。



move_page_tables関数は何をしますか？



最も興味深いのはこのループにあるようです：

 ... for (; old_addr < old_end; old_addr += extent, new_addr += extent) { ... move_ptes(vma, old_pmd, old_addr, old_addr + extent, new_vma, new_pmd, new_addr, need_rmap_locks); ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードは少し複雑です（さらに、コメントはありません）が、基本的にこれらは基本的な算術演算と計算です。



move_ptes関数には、最低レベルの内部ループが含まれます。

 ... for (; old_addr < old_end; old_pte++, old_addr += PAGE_SIZE, new_pte++, new_addr += PAGE_SIZE) { if (pte_none(*old_pte)) continue; pte = ptep_get_and_clear(mm, old_addr, old_pte); pte = move_pte(pte, new_vma->vm_page_prot, old_addr, new_addr); ... set_pte_at(mm, new_addr, new_pte, pte); } ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それでは、このサイクルで何が起こるのでしょうか？！ メモリ領域に対応するページテーブルの行（ PTE 、 ページテーブルエントリ ）を別の場所に移動するだけです。 本質的に、これらは各ページに割り当てられた整数です。



それで、私たちには何がありますか。実際、カーネルはマップされたブロックのデータに触れませんでした 。 エリア全体を移動するには、数ビットを交換するだけで十分でした。

正式には、複雑さはまだ O（N）ですが、

• 4 KB（または非常に大きなページの場合は2 MB）のページ全体をコピーする代わりに、カーネル構造内で整数を交換します。
• 「コールド」メモリに触れることなく「ホット」カーネルメモリを操作します。ページファイルにプッシュされるデータははるかに少なくなります。

したがって、O（N）を使用しますが、大きな違いがあります。



ああ、ところで、O（N）が多くの場合紛らわしいことを知っていますか？



この場合、Nの最大値は2 ⁴⁸ （仮想空間の最大サイズ）です。 ほとんどのコンピューターはわずか数ギガバイトのメモリで動作します-ほとんどのアーキテクチャでは64 GBを超えません（つまり、2 ³⁶バイト）。 ビッグページは2 ²¹バイトで、move_ptesの操作の最大数は2 ¹⁵です（はい、これは 32,768操作のみです）。



したがって、最悪の場合、コストは常に極めて低く、何らかの理由で最初からそれを疑いませんでした。



また、読むことをお勧めします：Mel GormanによるLinux Virtual Memory Managerの本を理解する 。



ナイアシリル・ムノガブカフ？ 心配しないで。 怠azineとreallocがすべてです。