NAKAMURA Minoru's Diary (2013年6月)

6/27 (木)

[Prog] 非アスキー文字列の文字比較

アスキーの文字列比較は strcmp だが、EUC や UTF-8 などのローケルがある言語の場合には strcoll や strcoll_l を使うことになる。例えばこんな感じ。

#define __USE_XOPEN2K8
#include <stdio.h>
#include <string.h>
#include <locale.h>

int main(int argc, char ** argv) {
    const char str1[] = "漢字入力";
    const char str2[] = "漢字だす";

    locale_t mylocale = newlocale(LC_ALL_MASK, "ja_JP.utf8", (locale_t)NULL);

    int ret = strcoll_l(str1, str2, mylocale);

    printf("string compare: %s %s %s\n",
           str1,
           ((ret == 0) ? "==" : ((ret > 0) ? ">" : "<")),
           str2);

    return 0;
}

strcoll_l ではなく strcoll を使うなら、事前に LC_COLLATE を setlocale してから行う(デフォルトでは LC_COLLATE は "C" になっている)。

setlocale(LC_COLLATE, "ja_JP.utf8");
result = strcoll(str1, str2);

しかし strcoll らは strcmp に比べて圧倒的に遅いので、ソートのような文字列比較を何度も繰り返す箇所に使うと性能が低下する。

こういう場合には strxfrm、strxfrm_l を使用するとよい。 strxfrm らは引数 src で与えられた文字列を謎のコードに変換して dest に書き込む。変換後の文字列同士を strcmp で比較した結果は strcoll らで比較した結果と一致する。 strxfrm らは重い処理だが、いったん変換してしまえば何度でも strcmp を使うことができる。

size_t strxfrm(char *dest, const char *src, size_t n);
size_t strxfrm(char *dest, const char *src, size_t n, localte_t locale);

元の文字列 src は NULL 終端の文字列であり strxfrm は現在のロケールに従い strxfrm_l は引数 locale のロケールに従っているとみなされる。この src が 1 文字づつ変換され dest に書き込まれてゆく。 dest もサイズは n で制限されている。変換が成功した場合には dest の最後に '0' を書き込んでから、dest に書き込んだ文字数('0' を除いた値)を戻り値として返す。もし戻り値が n 以上の場合には変換に失敗している。

strxfrm らは戻り値でエラーを報告しないで、エラーが起きた場合だけ errno にエラー番号をセットする。そのため strxfrm らを呼び出す前に errno を 0 にセットして、呼び出し後にに errno をチェックすべきであろう。

#include <stdio.h>
#include <string.h>
#include <alloca.h>
#include <locale.h>

int main(int argc, char ** argv)
{
    const char str1[] = "漢字入力";
    const char str2[] = "漢字だす";
    locale_t mylocale = newlocale(LC_ALL_MASK, "ja_JP.utf8", (locale_t)NULL);
    size_t len1 = strlen(str1);
    size_t len2 = strlen(str2);
    char *xfrm_str1 = alloca(len1 * 2);
    char *xfrm_str2 = alloca(len2 * 2);
    int ret1 = strxfrm_l(xfrm_str1, str1, len1 * 2, mylocale);
    int ret2 = strxfrm_l(xfrm_str2, str2, len2 * 2, mylocale);

    int ret = strcmp(xfrm_str1, xfrm_str2);

    printf("string compare: %s %s %s\n",
           str1,
           ((ret == 0) ? "==" : ((ret > 0) ? ">" : "<")),
           str2);

    int i;
    printf("Orig: ");
    for (i=0 ; str1[i] ; i++)
        printf("%02x ", (unsigned char)str1[i]);
    printf("\n");
    printf("Xfrm: ");
    for (i=0 ; xfrm_str1[i] ; i++)
        printf("%02x ", (unsigned char)xfrm_str1[i]);
    printf("\n");

    return 0;
}

strxfrm が変換後の文字列がどのようなエンコードに従うかは明記されていない。よく分からないコードに変換されている。

string compare: 漢字入力 > 漢字だす
Orig: e6 bc a2 e5 ad 97 e5 85 a5 e5 8a 9b
Xfrm: d2 83 dd 8e e0 ad 9c e0 b8 9d

追記：7/7

strcoll を UTF-8 の場合に追ってみたが、UTF-8 を「ユニコード」に変換し、そのコード番号で大小比較している。

UTF-8 は 1～6 バイトのマルチバイト文字列である。 ASCII を拡張しているので、NULL ターミネートされ、0x01～0x7F までは ASCII と同じ配列をとる。

2 バイト以上の文字列はまず最初のバイトの MSB に 1 が立ち、そこから N ビット分 1 が続いて 0 で止まる。続いた 1 の数がエンコーディングされている文字数となる。 2 文字目からは 0b10 がつく。よって下の表のような構成となり、x が連続する部分を使ってユニコードを記録している。

	1バイト目	2バイト目	3バイト目	4バイト目	範囲
1バイトシーケンス	0b0xxx,xxxx				U+0000 ～ U+007F
2バイトシーケンス	0b110x,xxxx	0b10xx,xxxx			U+0080 ～ U+07FF
3バイトシーケンス	0b1110,xxxx	0b10xx,xxxx	0b10xx,xxxx		U+0800 ～ U+FFFF
4バイトシーケンス	0b1111,0xxx	0b10xx,xxxx	0b10xx,xxxx	0b10xx,xxxx	U+10000 ～ U+1FFFFF

一部の文字列内の文字は strcoll から見て「無効」と判断される。これには 1. UTF-8 のエンコードに沿ってない場合、2. ユニコード内に定義されてない番号の場合の 2 種類がある。

誤ったエンコードは「無効」とされる。例えば最初の 1 バイトが 3 バイトシーケンス(0b110)を示したのに、後続の 2 バイトが並ばなかった場合。あるいは UTF-8 は一つのエンコードに対して、1つのフォーマットしか許さないので、0x7F なら 0xC1BF のようにも書けるが、後者は「無効」となる。あるいは 0xFE や 0xFF など UTF-8 では許されないエンコードを使った場合も「無効」となる。
エンコーディングは正しいが、ユニコード空間に文字が定義されてない番号も「無効」となる。そのため 5バイトシーケンスと6バイトシーケンスは UTF-8 では定義されいるが、ユニコードとしては未使用なので「無効」である。

strcoll は 1. のパターンでも 2. のパターンでも、「無効」と判断された文字を構成するバイトが全て 0x1 であったように変換され、その上で比較文字列と比べられる。

~~文字単体で見ると「無効」化されたバイトはユニード最小の U+0001 と同じ文字だと見做される。~~
~~1. のパターンにおいては UTF-8 のエンコードに従わないので、UTF-8 と解釈できないバイトの 1 つ 1 つが U+0001 と同じ文字と見做される。~~ 2. のパターンにおいては UTF-8 エンコードには従っているので、何バイトシーケンスかは分かっている。しかしそれでも各バイトの 1 つ 1 つが U+0001 と同じ文字と見做される。

strxfrm による文字変換は、変換後の文字列を strcmp で比較したものが strcoll と一致するようにするが、このために以下の変換をしている。

UTF-8 からユニコードにデコードされる。
ユニコードに対して、U+0001 以上のコードは全て +2 される。さらにユニコード上で存在しないコードはスキップされる。
UTF-8 のエンコードされ直す。

上記の処理に加えて strcoll の無効パターンであれば、~~不正なバイトを全て 0x03 に置き換え直される。~~

追記：2014/3/12

上記の無効パターンを 0x03 に書き換えるというのは GLIC の "ja_JP.utf8" 固有の特性であり、strxfrm で使える話ではなかった。

コメントを書き込む

6/26 (木)

コーランにおける豚の扱い

The Voice of Russia の記事によると米国の South Fork Industries というメーカーが豚肉を使用した塗料でコーティングされた銃弾の販売に着手したそうだ。同社の説明では、イスラムの教えにおいて豚肉は不浄なものとされているため、この弾丸で銃殺されたイスラム過激派戦闘員の身体は「汚された」ものであり、聖戦士たちは自らの基本的な天国に入るという目的を達する事ができなくなるという。

元記事はSBC Seattleで、"Jihawg Ammo" bullet と紹介しているが、だいたい同内容だ。 South Fork Industries の Web サイトにはそのようなページは見当たらない。削除されたのかもしれない。

Pork-laced bullet というとムガル朝最後に起きたインドのセポイの反乱が連想される(セポイは英東インド社の雇ったインド人傭兵)。この反乱は新型ライフル銃の薬包が(ヒンズー教徒が神聖視する)牛か(ムスリムが不浄視する)豚の獣脂が塗られているという噂から始まったんだよなぁ。

それはそれとして、The Voice of Russia の記事よると South Fork Industries 社のプレス・リリースではコーランは、状況に関わりなく豚肉と接触したいかなるイスラム教徒も「不浄である」とし、天国へは行かれないと説いている。と書いているそうだ。だが自分の持っている岩波文庫の井筒俊彦訳ではコーランで豚に関して記述されている箇所は3ヶ所だけ。順に抜粋してみる。

アッラーが汝らに禁じ給うた食物といえば、死肉、血、豚の肉、それから(屠る時に)アッラー以外の名が唱えられたもの(異神に捧げられたもの)のみ。

それとても、自分から食い気を起こしたり、わざと(神命に)そむこうとの心からではなくて、やむなく(食べた)場合には、別に罪にはなりはせぬ。まことにアッラーはよく罪をゆるし給うお方。まことに慈悲の心ふかきお方。

(牝牛フリューゲル版第168節/カイロ版第173節)

汝らが食べてならぬものは、死獣の肉、血、豚肉、それからアッラーならぬ(邪神)に捧げられたもの、絞め殺された動物、打ち殺された動物、墜落死した動物、角で突き殺された動物、また他の猛獣の喰らったもの ―(この種のものでも)汝らが自ら手を下して最後の止めをさしたものはよろしい― それに偶像神の石壇で屠られたもの。それから賭矢を使って(肉を)分配することも許されぬ。これはまことに罪深い行いであるぞ。

だがはげしい飢饉の時、自ら好んで罪を犯そうとてするのではなく、無理強いされる(前掲の禁止された食物を食べざる得ない)者はたいしては、まことにアッラーは限りなき寛容と慈悲を示し給う。

(食卓フリューゲル版第4節/カイロ版第3節)

宣言せよ、「わしに啓示されたもの(『コーラン』)の中には、死肉、流れ出た血、豚の肉―これは全く穢れもの―それにアッラー以外の(邪神)に捧げられた不浄物、これらを除いては何を食べても禁忌というこおにはなっていない。そればかりか、(たといこれらの不浄物でも)、別に自分で食気を起こしたとか、ただやたらに規則に叛きたくてするのではなしに、やむを得ず(食ってしまった)場合には、神様は(大目に見て下さる)。よくお赦しになる情深いお方だから。」

(家畜フリューゲル版第146節/カイロ版第145節)

だがユダヤ教の人々には、(回教徒より規定を重くして)爪牙をもつ動物は一切御法度にしておいた。また牛や羊でも、脂肉は、背中の上部と内臓のところ、それから骨にからんでいる部分を除き御法度にしておいた。これは、彼らが不遜だからその報いじゃ。我ら(アッラー)の言葉はことごとく本当のこと。

(家畜フリューゲル版第147節/カイロ版第146節)

South Fork Industries 社のプレス・リリースを書いた人の持っているコーランは、私の持っているのとは違うようだ。

コメントを書き込む

6/23 (日)

[Movie] アフター・アース

川崎まで出たので帰りに川崎チネチッタで「アフター・アース」(公式)を観て帰る。

[Food] ビタースイーツ・ビュッフェ＠ラゾーナ川崎

ラゾーナの4階にはアメリカンビュッフェ THE OVEN (2012年6月13日の日記)以外にも 2 軒、ビュッフェ形式のレストランがある。そのうちの 1 軒ビタースイーツ・ビュッフェ (公式)に行ってみた。最後の 1軒は柿安三尺三寸箸である。

お店のメニュー的に THE OVEN に被るところが多いがスイーツはこっちの方が多い。ジャンバラヤのような腹にたまるメニューは少ない。


ディナー時にだけ注文できるステーキ。量が少ない。		ソフトクリーム製造機で作る

コメントを書き込む

6/19 (水)

[Linux] BIOS の ACPI テーブルにパッチを宛てる

Intel Core i7 からは PCIe バスが CPU ソケットに直結し、CPU (ソケット)を複数搭載できるシステムではバスがどちらの CPU につながっているかでアクセス速度が変わるようになった。これを NUMA I/O と呼ぶことがある。特にレイテンシー性能を重視するなら、バスと CPU のトポロジーを考えて処理する必要がある。

バスがどちらの CPU ソケットにつながっているかは、BIOS 内の ACPI 情報で渡すことになっている。 Linux カーネルは起動時に ACPI テーブルを読み込んで、ユーザーが /sys/class/*/*/device/numa_node を読むと 0、1、… という NUMA ノード番号を返してくれる(2013年2月27日の日記)。この情報は ACPI テーブルの中でも特に DSDT(Differentiated System Description Table) と呼ばれるテーブルに記載される。

しかし機種によっては DSDT にバスのノード番号が正しく記載されてないことがある。この場合 /sys/class/*/*/device/numa_node が -1 になり、ユーザーはトポロジー情報を得られない。

正しいトポロジー情報を埋め込むためには DSDT にパッチを宛てる必要がある。この日記ではその方法を解説する。

ACPI BIOS から DSDT を取得 → デコンパイル → 修正 → コンパイル

ACPI の情報は ACPI Machine Language(AML) という言語で記述する。 ACPI BIOS は AML をコンパイルしたバイナリデータを内部に持っている。この ACPI テーブルの内容は Linux の場合は /sys/firmware/acpi/tables/DSDT から取得できる。 /proc/acpi/dsdt からも取得できるが推奨されない。

# cat /sys/firmware/acpi/tables/DSDT > dsdt.dat

AML を解読するには ACPICA から acpica-unix-(日付).tar.gz を落として導入する。例えば acpica-unix-20130517.tar.gz の場合は以下のようになる。

$ tar xzvf acpica-unix-20130517.tar.gz
$ cd acpica-unix-20130517/
$ make
# make install

ACPI Tool の中の iasl コマンドが AML 形式のファイルをコンパイル・デコンパイルを可能にする。さきほどの dsdt.dat を iasl でデコンパイルすると、最後の拡張子の .dat を .dsl に変更した dsdt.dsl という名前のファイルが生成される。これは人間が見て理解可能なテキストファイルである。

$ iasl -d dsdt.dat

このファイルを少し修正する。

修正した dsdt.dsl は iasl に -tc オプションをつけることでコンパイルできる。コンパイルが成功すると最後の拡張子 .dsl を .aml に変更した dsdt.aml という名前のファイルが生成される。

$ iasl -tc dsdt.dsl

もしエラーが出て途中でコンパイルが止まるようであれば、エラーを無視する -f オプションも加えてみる。

$ iasl -f -tc dsdt.dsl

DSDT DSL の修正

DSDT をデコンパイルすると、例えば以下のような DSL ファイルが生成される。下記は VMWare Player 5.0.2 の DSDT である。

DefinitionBlock ("vmware.aml", "DSDT", 1, "PTLTD ", "Custom  ", 0x06040000)
{
    Name (\GPIC, 0x00)
    Method (\_PIC, 1, NotSerialized)  // _PIC: Interrupt Model
    {
        Store (Arg0, GPIC)
    }

PCI0 という名前のデバイスに _PXM を足してやる。 0x00 は NUMA のソケット番号 0 を意味している。

        Device (PCI0)
        {
            Name (_HID, EisaId ("PNP0A03"))  // _HID: Hardware ID
            Name (_CID, EisaId ("PNP0A08"))  // _CID: Compatible ID
            Name (_BBN, 0x00)  // _BBN: BIOS Bus Number
            Name (_ADR, 0x00)  // _ADR: Address
            Name (_PXM, 0x00)  // _PXM: Device Proximity

同様に PCI1 デバイスには Name (_PXM, 0x01) を足してやればよい。

修正した DSDT を Linux カーネルに読み込ませる

DSDT を修正したからと言って勝手に BIOS を書き換えるわけにはいかない。替わりに Linux カーネルのブート時に dsdt.aml をロードして、メモリ上の DSDT を上書きしてもらう。

ACPI テーブルの置き換えは Linux カーネルの ACPI tables override via initrd 機能を有効にすることで実現できる。マクロは CONFIG_ACPI_INITRD_TABLE_OVERRIDE である。 CONFIG_ACPI_INITRD_TABLE_OVERRIDE は、本来の initrd または initramfs の先頭に cpio 形式のデータをつけることでブート時におまけファイルを読ませることが可能になるという機能(early cpio decoder)をベースとしている。この early cpio 内に kernel/firmware/acpi/ というディレクトリ階層を作り、その下に適当な名前の ACPI テーブルを配置すればブート時に BIOS の ACPI テーブルを上書きしてくれるようになる。

デフォルトで有効になっていない場合は、CONFIG_ACPI_INITRD_TABLE_OVERRIDE=y をつけてビルドし直す必要がある。

次に修正後の dsdt.aml を含めた early cpio ファイルを作成する。

$ cd /tmp
$ mkdir -p kernel/firmware/acpi/
$ cp dsdt.aml kernel/firmware/acpi/
$ find kernel | cpio -H newc --create > /tmp/instrumented_initrd

次に instrumented_initrd を先頭に、本来の initrd または initramfs を繋げる形で新しい initrd または initramfs を作る。

# cat /tmp/instrumented_initrd /boot/initramfs-3.9.6.img > /boot/initramfs-3.9.6.img.dsdt

最後に grub.conf などを編集し、initramfs-3.9.6.img.dsdt を使うように書き換える。編集後に reboot を実施。

title CentOS (3.9.6)
        root (hd0,0)
        kernel /vmlinuz-3.9.6 ro root=UUID=e38c37f0-2ee8-49e3-9bf9-d6fe4205a613 rd_NO_LUKS rd_NO_MD  KEYBOARDTYPE=pc KEYTABLE=jp106 LANG=ja_JP.UTF-8 rd_NO_LVM rd_NO_DM rhgb quiet crashkernel=auto
        initrd /initramfs-3.9.6.img.dsdt

dmesg でブート時のカーネルログを見ると、修正版 DSDT が読み込まれたのが分かる。

RAMDISK: [mem 0x37a8e000-0x37feffff]
DSDT ACPI table found in initrd [kernel/firmware/acpi/dsdt.aml][0xfe1f]

これで PCI バスには NUMA 情報が設定された。試しに /sys/class/net/eth0/device/numa_node を見ると、DSDT 中で _PXM で指定した値が入っている。万歳。

コメントを書き込む

6/15 (土)

[Movie] 二流小説家

デイヴィッド・ゴードンのミステリー小説を舞台を日本に置き換えて映画化した「二流小説家」(公式)を観てきた。場所は相変わらず川崎チネチッタ。公開初週だがほとんど客が入ってないのが悲しい。

原作だと野暮ったい死刑囚ダリアン・クレイが映画だと武田真治が演じるオーバーアクションなサイコキラーに様変わりしている以外は原作どおり。

コメントを書き込む

6/14 (金)

[Movie] 華麗なるギャツビー

川崎チネチッタで「華麗なるギャツビー」(公式)を観てきた。レオナルド・デュカプリオ主演だけあって女性客が多い。

コメントを書き込む

6/13 (水)

[Book] In-Memory Database 本

In-Memory Database の構成方法の勉強がしたくて今年の初めに Hasso Plattner 先生の「In-Memory Data Management: Technology and Applications」を購入した。 Hasso Plattner は独 SAP 社の設立者の一人で、2003 年までは CEO を務めていた。今はドイツに Hasso-Plattner-Institute 工科大学を設立し、自らも指導にあたっているそうな。「In-Memory Data Management」はこの工科大で開発された Sanssouci DB と呼ばれるプロトタイプ In-Memory DB を例に解説されている。

Sanssouci DB は一般にはバイナリもソースコードも公開されていないのだが、実は SAP 社の商用 In-Memory DB である SAP HANA は Sanssouci DB がベースになっているらしい。つまり「In-Memory Data Management」を読むと SAP HANA の構成方法が透けて見えることになる。

ただ「In-Memory Data Management」は、In-Memory DB の登場した商業的なバックグラウンドや In-Memory DB の実際の使われ方にページが多く割かれており、技術的な内容は一部分しかない。一般的な RDBMS の構成方法や、RDBMS をクラスタ化する際に必要な分散アルゴリズムの話は割愛されている。加えて言うと推敲不足なのか、同じことが何度も出てきて非常に読み辛い。

他の教科書も探していたのだが、Amazon から同じ Plattner 先生の「A Course in In-Memory Data Management: The Inner Mechanics of In-Memory Databases」をお薦めされる。まだ買っていないのだが、「なか見」で見れる目次を見る限り Sanssouci DB の技術的な側面を中心の教科書のようだ。おそらく「In-Memory Data Management」と2冊買うと内容が重複すると思われるので、In-Memory DB の技術的な興味に絞られるなら「A Course in In-Memory Data Management」だけ買った方がよさげ。

コメントを書き込む

6/12 (火)

Tweet API 1.0 が廃止に

Twitter 社の Tweet API 1.0 が廃止。南無三。

コメントを書き込む

6/5 (水)

[PostgreSQL] SQL の手習い

PostgreSQL を対象に SQL の勉強をはじめるが、まだ理解できてない。 SQL 文をレキシカルに解析はできるようになったが、セマンティクスを掴むことが難しい。

SELECT 文一つとっても expression に書ける項目が、後置される ORDER BY/GROUP BY/OVER などで制約を受ける。

例えば以下のようなテーブルがあった場合、

CREATE TABLE orders (
    o_orderkey      INTEGER,
    o_custkey       INTEGER,
    o_orderstatus   CHAR(1),
    o_totalprice    REAL,
    o_orderDATE     DATE,
    o_orderpriority CHAR(15),
    o_clerk         CHAR(15),
    o_shippriority  INTEGER,
    o_comment       VARCHAR(79)
)

例えば o_custkey でソートを掛けて、o_custkey と o_orderkey を表示。これは問題ない。

SELECT o_custkey, o_orderkey FROM orders ORDER BY o_custkey;

一方、GROUP BY 句を使ってグループ化して、o_custkey と o_orderkey を表示。これはエラーとなる。

SELECT o_custkey, o_orderkey FROM orders GROUP BY o_custkey;

ERROR:  column "orders.o_orderkey" must appear in the GROUP BY clause or be used in an aggregate function

ウィンドウ関数を使うとまた expression に書けるものが変わる。 RANK() のようなウィンドウ関数がないとエラーにとられる。

SELECT o_custkey,o_orderkey, RANK() OVER (PARTITION BY o_custkey  ORDER BY o_orderkey) FROM orders;

GROUP BY と ORDER BY を同時に使うことができるのかどうかよく分からない。 PostgreSQL はエラーにとるが、動作する DB もあるようだ。

SELECT o_custkey, count(o_orderkey) FROM orders GROUP BY o_custkey ORDER BY o_orderkey;

何が正しい SQL で、何がエラーな SQL を理解できるようになるには時間がかかりそうだ。

コメントを書き込む

6/3 (月)

[Prog] 名前付きパイプ(named pipe)のオープン時のブロックを防ぐ

名前付きパイプ(named piep)または FIFO をオープンする場合の動作のまとめ。

FIFO は reader と writer の二つの終端(ends)があり、デフォルト(blocking mode)では両方の終端が開かれるまで最初の終端を開いたスレッドは open 関数内でブロックされる。だが open の flags に O_NONBLOCK フラグをつけると non-blocking mode となり、ブロックされなくなる。

flags	blocking mode	non-blocking mode
O_RDONLY	FIFO が writing(O_WRONLY or O_RDWR) でオープンされるまでブロックされる。	即時成功する。
O_WRONLY	FIFO が reading(O_RDONLY or O_RDWR) でオープンされるまでブロックされる。	FIFO が reading(O_RDONLY or O_RDWR) でオープンされていなければ、EXIO のエラーとなる。
O_RDWR	(Linuxでは)即時成功する。	(Linuxでは)即時成功する。