A few notes about memcpy vs memmove and some related items as well.

ちょっと memcpy 対 memmove とか関連事項のメモ。

memcpy

The C standard specifies two functions for copying memory regions, memcpy and memmove. The important difference is that it is undefined behavior to call memcpy with overlapping regions. One must use memmove for that. As the names imply, memcpy copies data from one region to another, while memmove moves data within a region. (It’s also perfectly acceptable to memmove between different regions.)

C 規格はメモリ範囲コピーのための関数を二つ規定している。memcpy と memmove だ。重要な違いは、重複範囲で memcpy を呼ぶと未定義動作になるという点だ。そういうときは memmove を使わなければいけない。名前のとおり、memcpy はデータをある範囲から別の範囲にコピーするもので、一方 memmove は、範囲内でデータを移動するものだ。(memmove で別の範囲に移動してもまったく問題はない。)

This subtle but important distinction allows memcpy to be optimized more aggressively. In the case of memmove between overlapping regions, care must be taken not to destroy the contents of the source before they are done copying. This is easiest to see with a naive implementation of a copy loop.

この小さな、しかし重要な区別があるおかげで memcpy のほうがアグレッシブに最適化できる。重複範囲の memmove は、元の内容をコピーする前に破壊してしまわないような注意が必要なのだ。この失敗はナイーブなコピーループで簡単に見ることができる。

In order to operate as desired, the second loop must be changed to for (int i = 3; i >= 0; i--). memmove must implement both loops and decide between them at runtime.

期待どおりに動作するためには、二番目のループを for (int i = 3; i >= 0; i--) にする必要がある。memmove は、両方のループを実装しておいて、ランタイムでどちらを使うか決定しなければいけない。

bcopy

BSD systems also have another copying function, bcopy. It has the same semantics as memmove, but the source and destination arguments are reversed. It also has one other property: the compiler doesn’t know about it. The compiler can optimize and inline calls to standard C functions, but can’t do so when they are misspelled.

BSD には別のコピー関数もある。bcopy だ。意味は memmove と同じだが、コピー元とコピー先の引数が逆だ。そしてもう一つ特徴がある: コンパイラに知られていないということだ。標準的な C 関数へのコールはコンパイラが最適化してインライン化できるが、つづりが違えば、それが不可能になる。

Some time ago, dlg@ noticed that a couple of the bcopy calls in the network stack were impacting packet forwarding performance. Copying an ethernet header is only six bytes. The compiler could easily inline such a copy, but instead the source code required a call to the bcopy function, which would then perform various overlaps tests, etc. Replacing the bcopy calls with calls to memcpy sped things up considerably.

いくらか前に dlg@ が気づいたのだが、ネットワークスタック内に数回ある bcopy コールがパケットフォワードの性能に影響を与えていた。イーサネットヘッダのコピーなんて 6 バイトに過ぎない。コンパイラがそういうコピーをインライン化するのは簡単なはずだが、そのソースコードは bcopy 関数へのコールを要求し、それは種々の重複テストやら何やらを実行することになっていた。その bcopy コールを書き換えて memcpy へのコールにすると、大幅にスピードアップできた。

And so began a slow conversion of the many bcopy calls in the kernel to memcpy. This requires inspecting the function arguments to make sure they don’t overlap. If they do, then memmove must be used instead. Before this operation started, there was not a single memmove in the kernel, as evidenced by the fact that several architectures lacked implementations.

それで、カーネル内にある大量の bcopy コールを少しずつ memcpy に変換することが始まった。これには引数の中身が重複していないか調査する必要がある。重複していれば memmove を使わなければならない。この作戦が開始する前まで、カーネル内に memmove は一つもなかった。その証拠に、実装のないアーキテクチャも複数あった。

libkern

Two things to note about the kernel implementation of these functions. First, they are almost always implemented in assembly for performance. Sometimes, though, that results in some superultraoptimized code, such as the miracle of modern engineering that is arm memcpy.S. Wowzers. For large copies, finding an optimized path is worth it. But all that code burns icache and causes branch mispredictions. No wonder then that having the compiler inline calls works better than dropping into this behemoth. (For the bold, you may also gaze into the abyss that is sparc64/locore.s for another take on these functions.)

これらの関数のカーネル実装について、留意すべき点が二つある。一つは、性能上の理由から、それらがほぼ必ずアセンブリで実装されるということ。時にそれは何らかの超絶すごい最適化コードになり、たとえば arm の memcpy.S のような現代エンジニアリングの奇跡を産み出す。どひゃー、だ。巨大な範囲のコピーなら最適経路を探す価値もあろうが、このコードは命令キャッシュを使い尽くして分岐予測の失敗を招く。コンパイラにインライン化させるほうが、こんな怪物ベヒーモスになるよりもうまくいくのは当然だ。(勇者たちよ、sparc64/locore.s という深淵を覗き込むなら、これらの関数のまた別の面を知ることになろう。)

Second, on many architectures, the functions share code and overlap. The amd64 memmove.S is easier to read. Long ago, all three functions (memcpy, memmove, bcopy) were the same. And frequently implemented in terms of bcopy. This meant that every call to memcpy or memmove had to reverse the arguments. In accordance with our preference for new code to use the standard functions, this was changed to have bcopy reverse the arguments and fall into memmove. More recently, we’ve also changed the memcpy entry point to occur after the overlap check (but not yet everywhere, as the arm example shows).

次に、多くのアーキテクチャでこれらの関数がコードを共有しているということだ。amd64 の memmove.S は、さっきのよりも読みやすい。昔は memcpy, memmove, bcopy の三つが一緒だった。そして bcopy の別名として実装されることが多かった。つまり memcpy や memmove へのコールは毎回、引数を引っくり返す必要があったというわけだ。しかし、新しいコードを書くときは標準関数を使うという我々の好みに則り、bcopy が引数を引っくり返して memmove に落ちていくように変更された。もっと近くでは、memcpy のエントリポイントを重複チェックの後に置くようにも変更してある (arm の例のとおり、まだすべてのアーキテクチャというわけではないが)。

memmove

As mentioned, we’re changing bcopy to memcpy and the occasional memmove. Sometimes that goes wrong, and a memcpy is introduced where memmove is needed. That happened in the PPPOE code as seen here. A MAC address of all ‘A’ or ‘F’? Almost as if memcpy copied two overlapping addresses as seen in the example above. Sure enough, reverting to bcopy solves the problem. Or switching to memmove. In this case, it seemed like the bcopy to memcpy conversion was safe because the destination was freshly allocated by M_PREPEND, and therefore the pointers would be unique. But it turns out the source was actually part of the mbuf to start, and had been chopped off with m_adj earlier in the function. Very sneaky.

前述のとおり、我々は bcopy を memcpy に、あるいは必要に応じて memmove に換えている。この際に間違えて、memmove すべきところで memcpy を使ってしまうことがある。実際に PPPOE のコードでこのように起こってしまった。MAC アドレスすべてが A や F になる……だと……? まるで上の例のように、重複アドレスを memcpy したかのようだ……! アッハイ、bcopy に戻したら直ります。あるいは memmove に切り換えても。さて今回のケース、コピー先は M_PREPEND で新規に割り当てられているのでポインタはユニークであり、bcopy を memcpy に換えても安全なように見えた。しかし実際にはコピー元が mbuf の一部から始まって関数の前のほうで m_adj によって切られていたのだ。なんとも小賢しい。

nop

Not long ago, reyk@ noticed that while we use asm versions of these functions in the kernel, libc is built with the stock C versions. Switching to the asm versions gives a nice performance boost. But then something very strange happened. mlarkin@ had an amd64 ramdisk kernel crashing at boot. In bcopy. A poorly assembled version of bcopy.

比較的最近になって reyk@ が気づいたのだが、カーネル内ではこれらの関数の asm バージョンを使っているのに、libc には出来合いの C バージョンが入っている。asm バージョンに切り換えたところ、良い感じの性能改善が見られている。しかしここで、とても奇妙なことが起きた。mlarkin@ の amd64 ramdisk カーネルが起動時にクラッシュしたのだ。bcopy で。拙いアセンブリバージョンの bcopy で。

Normally, bcopy is supposed to look something like this:

通常、bcopy はこのような感じになっているはずだ:

xchg the source and destination registers, and then “nop sled” into memmove. But Mike had a special edition bcopy:

コピー元とコピー先のレジスタを xchg してから nop のソリに乗ってシャンシャンと memmove まで連れていってもらうのだが、Mike は特別エディションの bcopy を使っていた:

Well, that’s certainly different. Perhaps most awesome is that the last callq in bcopy is actually also the first few instructions of memmove, but that’s just coincidence. But how is this possible? The kernel is built from entirely separate sources, unshared with libc. A switch to asm memcpy/memmove in libc can’t possibly affect the same functions in the kernel. Can it?

うん、たしかに違うね。おそらく一番すごいのは bcopy の最後の callq が memmove の最初の二、三個の命令と同じだということだが、これは単なる偶然だ。しかしどうしてこんなことが起こり得るのか? カーネルはまったく別のソースからビルドされており、libc と共有されていない。libc で asm の memcpy/memmove に切り換えたからといって、カーネルの同名関数に影響するはずがない。そうでしょ?

gas

Reverting to a previous build of libc and recompiling the kernel corrected the problem. The problem was actually in userland. millert@ quickly found and backported two memcpy fixes for gas. Surely, that’ll fix it. But no. The problem is in the libc asm commit, but not in memcpy or memmove.

libc を前回のビルドに戻してカーネルをコンパイルし直したところ、問題は収まった。本当に原因はユーザランドにあったのだ。すぐ millert@ が、gas にあった二つの memcpy の訂正をバックポートしてくれた。よし、これでオッケー。……じゃなかった。問題は libc の asm 化コミットにあり、memcpy でも memmove でもなかったのだ。

memset

After deraadt@ deduced through some trial and error that memset was the buggy function, naddy@ noticed that the FreeBSD version of this function had one tiny difference. Another diff for the one liner hall of fame.

試行錯誤しながら deraadt@ は memset にバグがあると推理し、naddy@ は FreeBSD 版の memset に小さな違いがあることを発見した。またしてもワンライナーの殿堂入り間違いなしの diff だ。

The second argument to memset is of type int, but is expected to be interpreted as an unsigned char. By default, however, the register it’s passed in will be sign extended. 0x90 turns into 0xffffff90 and everything goes sideways. How could a bug like this live in the kernel for so long? The kernel only ever calls memset with three arguments: 0, ' ', 0xff. The first two are positive values, and the last sign extends into itself.

memset の第二引数は int だが、unsigned char として解釈するよう期待されている。しかし既定では、それを入れて渡されるレジスタは符号拡張される。0x90 は 0xffffff90 に、といった具合にすべてズレていくのだ。一体どうすれば、こんなバグがカーネル内で、これほど長く生き残っていられたのだろう? 実は、カーネルはこれまで三種類の引数でしか memset をコールしていない: 0, ' ', 0xff だ。最初の二つは正の値だし、最後のは符号拡張しても変わらない。

cld

Related fun fact: the x86 architectures have a direction flag that can be set to cause the processor to run backwards. This is how the backwards copying overlapping memmove is implemented. It’s important for the operating system to keep this flag set to the correct value. If userland sets the flag and then traps into the kernel, it would not be good for the kernel to run in reverse. 900 years ago, bugs of this nature could be exploited for some hilarity. The asm versions of memcpy were until very recently somewhat paranoid about always clearing the direction flag in case it had somehow been forgotten. But guenther@ did an audit and fixed up all the remaining entry points where it was possible it wasn’t set, and then the unnecessary instruction could be removed.

関連して、面白い事実がある: x86 アーキテクチャには方向フラグがあり、セットするとプロセッサが逆に進む。これを使って逆向きの重複 memmove が実装されている。OS にとって、このフラグを正しい値にしておくのは重要である。ユーザランドがフラグをセットしたままカーネルトラップに入り、カーネルが逆に進んでしまうのは良くない。900 年前にはこの種のバグが跳梁跋扈していた。asm バージョンの memcpy は、つい最近まで少しパラノイド気味に、「もしかして忘れているんじゃないか」と、いつも方向フラグをクリアしていた。しかし guenther@ が監査を実施して、セットされていない可能性のあるエントリポイントをすべて修正し、しかるのちに不要な命令を削除することができた。

libc

After the initial libc asm commit was reverted, deraadt@ spent some time polishing and improving it. Mostly untangling the complicated libc build infrastructure. The Makefiles are designed to support asm or C versions of each function, but sometimes they have to be implemented in pairs or with dummy stub files or else too many functions get compiled. And the dependencies were generally wrong. Part of the great restructuring involved temporarily changing all architectures to a special memcpy implementation. It checks for overlap like memmove would, but instead of processing the data, it logs a message and aborts. All within C spec. This will help us verify that programs are using memcpy correctly and memmove where they must. Similar changes should be coming to the kernel. So far a few problems have been identified. Also a bug involving overlapping snprintf buffers.

最初の libc asm コミットが撤回されてから、deraadt@ は時間をかけてそれを磨き直し、改良した。おもに、複雑な libc ビルドのインフラを解きほぐすことに時間を費した。Makefile は、それぞれの関数の asm バージョンにも C バージョンにも対応するように設計されているが、時には両方の組み合わせや、ダミーのスタブファイルを含めたりして実装される必要がある (さもなくば、必要以上に多くの関数がコンパイルされてしまう)。そして、その依存関係がだいたいおかしかった。大規模構造改革の一環として、すべてのアーキテクチャが一時的に特別な memcpy 実装に変更された。これは memmove のように重複をチェックするが、重複データは処理せずログを残して abort する。すべて C 規格の範囲内だ。これにより、プログラムが memcpy を正しく使っていること、そして必要なところでは memmove を使っていることを検証するのに役立つ。同様の変更はカーネルにも来ることになるはずだ。今のところ少数の問題が特定されている。加えて、重複バッファの snprintf に関連するバグが一つ。