同時にwrite(2)すると混ざるかどうか

Linux のシステムコールである write(2) の ドキュメントを読むと

Atomic/non-atomic: A write is atomic if the whole amount written in one operation is not interleaved with data from any other process. This is useful when there are multiple writers sending data to a single reader. Applications need to know how large a write request can be expected to be performed atomically. This maximum is called {PIPE_BUF}. This volume of IEEE Std 1003.1-2001 does not say whether write requests for more than {PIPE_BUF} bytes are atomic, but requires that writes of {PIPE_BUF} or fewer bytes shall be atomic.

との記載があり、PIPE_BUF(Linux では 4KB)のサイズより小さい場合は atomic なのでログが混ざることはないが、それより大きい場合は混ざることがある、というように読めます。

RubyのLoggerはスレッドセーフ(＆プロセスセーフ)かどうか調べてみた - sonots:blog

この件、引用されたこともあって確認した。古い linux kernel (2.6.35.13) だけど。

まず、vfs レイヤの動作として、 vfs_write -> do_sync_write -> f_op->aio_write の順で呼び出される。

そして、各fs実装 (f_op) の呼び出しが以下のようになる。

ext2/ext3の場合、aio_write は generic_file_aio_write なので、以下のように追記モード云々に関係なく、常にロックをとる*1。

/**
 * generic_file_aio_write - write data to a file
 * @iocb:       IO state structure
 * @iov:        vector with data to write
 * @nr_segs:    number of segments in the vector
 * @pos:        position in file where to write
 *
 * This is a wrapper around __generic_file_aio_write() to be used by most
 * filesystems. It takes care of syncing the file in case of O_SYNC file
 * and acquires i_mutex as needed.
 */
ssize_t generic_file_aio_write(struct kiocb *iocb, const struct iovec *iov,
                unsigned long nr_segs, loff_t pos)
{
        struct file *file = iocb->ki_filp;
        struct inode *inode = file->f_mapping->host;
        ssize_t ret;

        BUG_ON(iocb->ki_pos != pos);

        mutex_lock(&inode->i_mutex);
        ret = __generic_file_aio_write(iocb, iov, nr_segs, &iocb->ki_pos);
        mutex_unlock(&inode->i_mutex);

        if (ret > 0 || ret == -EIOCBQUEUED) {
                ssize_t err;

                err = generic_write_sync(file, pos, ret);
                if (err < 0 && ret > 0)
                        ret = err;
        }
        return ret;
}
EXPORT_SYMBOL(generic_file_aio_write);

xfsの場合はxfs_file_aio_writeの中でdirect I/Oでなければブロックする。

PS. POSIX的にはOSの自由だろとか、nfsだったらどうだろという議論はあると思うので用法用量を守ってお使いください。

*1:そして、だから MySQL で ext2/ext3 は遅いとか言われるんですねー

サービスごとに異なるパスワードを使い分ける方法

最近、パスワードの使い回しをしているユーザーに対する攻撃が出回るようになってきています (参照: パスワード攻撃に対抗するWebサイト側セキュリティ強化策 | 徳丸浩の日記) が、マスタパスワードからサービスごとに異なるパスワードを自動生成するのが簡単な対策ですよね。

プログラマなら（もしくはコマンドライン操作に慣れているのなら）、こんな感じでできるかなーと思います。

$ perl -MDigest::HMAC_SHA1 -wle 'print Digest::HMAC_SHA1->new($ARGV[0])->add($ARGV[1])->b64digest' "my-master-password" example.com
Mau83v+ml6dRViOZhcRdHM0NXzY
$

HMAC 関数にマスターパスワードとサービスのドメイン名を食わせて、その出力をサービス専用のパスワードにするだけ。忘れても再計算すれば同じ値が出る。もちろん、先頭10文字とかにしてもいい。

巨大な bookmarklet を信頼できる形で配布する方法

Twitter で聞いてみたところ @hasegawayosuke さんいわく、Bookmarklet の文字数制限は最短だと約2,000文字らしいです。

でも、その長さで bookmarklet を書くのって難しいですよね。かといって、別のサーバから JavaScript をダウンロードして実行するとなると、そのダウンロードされたスクリプトが安全か、という問題が出てきます。

ならば、暗号学的ハッシュ関数を2,000文字以下で実装し、ダウンロードしたスクリプトの改ざん検証を行った上で実行すればいいのではないか。そうすれば、文字数の制限に悩むことなく Bookmarklet の開発に勤しめるのではないでしょうか。

ジャジャーン！というわけで、とても短い SHA-1 の JavaScript 実装を作りました*1。

GitHub - kazuho/sha1.min.js: SHA-1 implementation in JavaScript (1480 bytes; intended for bookmarklets, etc.)

現在 1,480 文字。これを使ってダウンロードしたスクリプトの SHA-1 を検証した後に eval すれば、サーバに bookmarklet の実装をおいても問題なくなりますね*2。たとえば、http://example.com/bookmarklet.js をダウンロードして、その SHA-1 ハッシュ値が 8730b855b55698ce68eed2e0e358f3160260f0c4 である場合のみ実行するような Bookmarklet は、以下のように描くことができるでしょう。

javascript:(function(url,hash){var hex_sha1=function(b){function k(a){return g(h(f(a),a.length*8))}function d(c){var a='',b;for(var d in c)b=c.charCodeAt(d),a+=(b>>4&15).toString(16)+(b&15).toString(16);return a}function e(e){var c='',d=-1,a,f;while(++d<e.length)a=e.charCodeAt(d),f=d+1<e.length?e.charCodeAt(d+1):0,55296<=a&&a<=56319&&56320<=f&&f<=57343&&(a=65536+((a&1023)<<10)+(f&1023),d++),a<=127?c+=b(a):a<=2047?c+=b(192|a>>6&31,128|a&63):a<=65535?c+=b(224|a>>12&15,128|a>>6&63,128|a&63):a<=2097151&&(c+=b(240|a>>18&7,128|a>>12&63,128|a>>6&63,128|a&63));return c}function f(c){var b=[];for(var a=0;a<c.length*8;a+=8)b[a>>5]|=(c.charCodeAt(a/8)&255)<<24-a%32;return b}function g(d){var c='';for(var a=0;a<d.length*32;a+=8)c+=b(d[a>>5]>>24-a%32&255);return c}function h(m,l){m[l>>5]|=128<<24-l%32,m[(l+64>>9<<4)+15]=l;var d=[],e=1732584193,f=-271733879,g=-1732584194,h=271733878,k=-1009589776;for(var n=0;n<m.length;n+=16){var o=e,p=f,q=g,r=h,s=k;for(var b=0;b<80;b++){b<16?d[b]=m[n+b]:d[b]=c(d[b-3]^d[b-8]^d[b-14]^d[b-16],1);var t=a(a(c(e,5),i(b,f,g,h)),a(a(k,d[b]),j(b)));k=h,h=g,g=c(f,30),f=e,e=t}e=a(e,o),f=a(f,p),g=a(g,q),h=a(h,r),k=a(k,s)}return[e,f,g,h,k]}function i(d,a,b,c){return d<20?a&b|~a&c:d<40?a^b^c:d<60?a&b|a&c|b&c:a^b^c}function j(a){return a<20?1518500249:a<40?1859775393:a<60?-1894007588:-899497514}function a(b,c){var a=(b&65535)+(c&65535),d=(b>>16)+(c>>16)+(a>>16);return d<<16|a&65535}function c(a,b){return a<<b|a>>>32-b}return b=String.fromCharCode,function(a){return d(k(e(a)))}}();var xhr=new XMLHttpRequest;xhr.onreadystatechange=function(){if(xhr.readyState==4&&xhr.status==200&&hex_sha1(xhr.responseText+'')==hash)eval(xhr.responseText)};xhr.open("GET",url);xhr.send()})("http://example.com/bookmarklet.js","8730b855b55698ce68eed2e0e358f3160260f0c4")

ぱっと作ったものなので、問題点等ありましたらご指摘いただけると助かります。

*1:http://pajhome.org.uk/crypt/md5/sha1.html から不要なものを削ぎ落した後、esmangle で minify しています

*2:ダウンロードのログが残る等、プライバシーに関する問題は別途対処が必要になる可能性があります

Monoceros雑感

Monoceros は @kazeburo さんが開発してる Plack 用ウェブサーバ。prefork型だけど、待機中の接続をイベントドリブンのマネージャで管理することで、同時接続10,000本とか行ける（ソケットの受け渡しは SCM_RIGHTS とか使う）。

で、雑感

  • 大好き！！！
  • Starletより遅い問題は、以下のようにすれば解決できると思う
    • listen するソケットに TCP_DEFER_ACCEPT つけて、accept(2) は worker でのみ実行する
    • worker は HTTP レスポンス送信後に read(2) してみて、後続のリクエストが来てない場合にのみ、マネージャプロセスにソケットを返還する
      • (追記) 「返還」ではなく、マネージャプロセスが管理しているソケットのいずれかにデータがきている場合のみ、そのソケットとworkerのソケットを「交換」する、とすればより良い
  • HTTP/1.1 のパイプラインサポートも上記の方法でサポートできるはず
    • 1.1 対応するなら、Starlet 側のリクエスト処理ループを共有できるようになってると、うれしいなうれしいな >_
      • あるいは Monceros と Starlet が共有できるリクエスト処理ループという形で別モジュールに切りだすとか

待機のみをイベントドリブンでやってリクエストのパースとレスポンスの送信を prefork でやるというアプローチは、アプリケーションの処理のみを prefork でやってそれ以外は全てイベントドリブンでやる nginx + Starman / Starlet みたいなアプローチと比べると、slowloris 攻撃等への耐性という点で難があることは確かです。ですが、それへの対処が可能な場合、あるいは、リバースプロキシの裏側で大規模な持続的接続が必要な場合（都度接続やってると TIME_WAIT があふれるとか）はとてもいい手法だと思います。

もふったーのコンシューマシークレット問題について、鍵はプログラム中に安全に埋め込めるはず。だが…

超軽量Twitterクライアント「もふったー」コンシューマシークレットキー難読化最後の挑戦 - GIGAZINE もふったーコンシューマシークレットキー難読化最後の挑戦 ・ω・ - Windows 2000 Blog あたりの話について。記憶に頼って書いてるので間違ってたらごめんなさい。

問：鍵を隠すことができるか

答：以下の理由から可能なはず。

以上より、鍵のハッシュを演算後の内部ステートをもつ、鍵ごとに特化したHMAC関数（正確に言うと、鍵ごとに特化したハッシュ値同様の安全性をもつ（つまり鍵を回復することのできないステート値）を生成し、鍵のかわりに、そのステート値を埋め込んだ専用HMAC関数をプログラム中に記述することができる。そして、ステート値から鍵を回復することはできない*2。

問：そのようにして鍵を隠すことに意味はあるのか

答：ない。

鍵を隠すのは、鍵を使って署名できないようにするためのはず。だが、上記のような方法で鍵を隠したとしても、そのステート値を使って、鍵を知らなくても署名することができる。

つまり、鍵を隠したところで意味がない。鍵を奪われなければ、ピッキングされても構わないと考えるなら話は別ですが。

10:33追記: 確認しましたが、HMACの鍵から導出したステート値を持ちまわることができるという特性と、一方で導出されたステート値も鍵同様の保護が必要であるという点は RFC 2104 の 4. Implementation Note に記載されています。HMACを提案した論文 Keying Hash Functions for Message Authentication の 5.3 もあわせて参照のこと

*1:MD-5も

*2:できたとしたら、それはハッシュ関数(SHA-1)が破られたのと同義

asm.jsの評価（JVM,PNaClとの比較、および、現在の問題と今後の可能性について）

asm.jsに関する客観的意見があまりないようなので、ツイートをまとめてメモ。

現時点での機能はC/C++コードの移植に特化している

  • 文字列にもオブジェクトにも配列にもアクセスできない
    • JavaScriptの値で使えるのは数値だけ*1
    • typedarrayについては、同時に１つだけ*2アクセスできる
  • GCがない
    • オブジェクトにアクセスできないと書いたけど、当然newもできない
    • 自分でmalloc/freeから実装する必要がある
  • 関数ポインタすらない
    • 定義された関数呼び出しは可能

つまりは、フラットなデータメモリ、シンボルベースのコード空間と、数値演算機能のみがある、とても低レベルな仮想マシンということ。ネイティブコードをJavaScriptに変換した場合に高速に動く環境を作ろうとしていることは明らかだし、それ以外の目的では非常に使いにくい。

既存の他のアプローチ（JVM, PNaCl）と比較した場合には以下のようになる

  • 対JVM
    • asm.jsはJavaScript処理系で実行可能(JVMは独自)
    • asm.jsはメモリアクセス毎にガードコードの実行が必要(JVMはJITコンパイル時のみの検証でいいのでより高速)
  • 対PNaCl
    • asm.jsはJavaScript処理系で実行可能(PNaClは独自)
    • ARM上で動作するPNaClはメモリアクセス毎にガードコード実行するという点で同様*3
      • ただ、未定義動作を許容するPNaClの方が高効率のはず

ただ、前述したとおり現状の asm.js は JavaScript の世界と細粒度でのやりとりがしづらいので、JavaScript処理系で実行できることが大きなメリットであるとは言い難い。JVMあるいはPNaClと比較して優位にあるとは言えないのではないか*4。

将来性について

asm.js - frequently asked questionsでES6 structured binary data APIへの対応を検討している旨が述べられており、今後、上記制限のうちオブジェクトの生成とアクセスについては対応するのかも。そうなると、なかなかに競争力のある選択肢となる可能性がある。

*1:と数値に変換されるundefined,null,boolean

*2:emscriptenでメモリ領域を表現するために使われる「heap」

*3:x86と違ってセグメントレジスタを使ったサンドボックスが作れないため

*4:その両者に現時点で競争力があるかはさておき