コグノスケ


2016年 3月 2日

Device Tree の謎

Device Tree を使って ARM Linux を起動したとき、どうやってコマンドラインや initramfs のアドレスをカーネルに伝えるんでしょうか?

U-boot のコードを見ていると *.dtb を一回メモリにロードして、わざわざメモリ上で書き換えているように見えたのですが、そんな面倒なことしないとダメなのかなあ。

ATAGS の時はコマンドラインと initramfs の位置は簡単に伝えられたのに、新しいはずの Device Tree が退化しているように見えるのは何故だろう…。

ちなみに x86 でも Device Tree はあまりメジャーではないものの、一応使えたはずですが、*.dtb の書き換えは誰がやるのだろう?GRUB や UEFI がやるのかなあ?

メモ: 技術系の話は Facebook から転記しておくことにした。

編集者: すずき(更新: 2016年 3月 8日 23:13)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2016年 3月 3日

懐かしい

EXPORT_SYMBOL(※)でググると、2年くらい前に自分が書いた解説が未だに一番上に出るんですね。かなり時間が経っているし、更新もしていないので、他のサイトが出るかと思いましたが、案外、誰も調べないもんですね。

(※)Linux カーネル内のシンボルを、カーネルモジュールに公開するためのマクロ。

メモ: 技術系の話は Facebook から転記しておくことにした。

編集者: すずき(更新: 2016年 3月 8日 23:15)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2016年 3月 7日

スマホの電池

自分のスマホ SH-01F がヘタレてきて、ほぼ何も操作していないのに、半日で電池の容量が 4割近く減るようになってしまいました…。


電池残量

そろそろ 2年経つし、もう電池が寿命なのかなあ。

メモ: 技術系の話は Facebook から転記しておくことにした。

編集者: すずき(更新: 2016年 3月 8日 23:24)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2016年 3月 8日

Linux と ARMv7 MMU の魔術

超マニアックです。Linux と ARM が多少分かっていればわかるくらいに説明できていたら良いなあ…。

Linux カーネルの pte_t に設定する L_PTE_MT_BUFFERABLE などの L_PTE_MT_ 系マクロが指定するメモリタイプと、ARM のページテーブルエントリに指定するビット値をどうやってマッピングしているか?を解説します。

突然そんなこと言われても L_PTE_MT_ なんちゃらというのは何なのか全く意味が分からないと思うので、どこで出会うかから説明します。

前置き

Linux のデバイスドライバにて mmap() システムコールを実装する際に、下記のように実装することがあります。

mmap() の実装例

int hogedrv_mmap(struct file *filp, struct vm_area_struct *vma)
{
        if (filp->f_flags & O_SYNC) {
                vma->vm_page_prot = pgprot_noncached(vma->vm_page_prot); //★これ★
        }

        return remap_pfn_range(vma, vma->vm_start, vma->vm_pgoff,
                vma->vm_end - vma->vm_start, vma->vm_page_prot);
}

やりたいことをざっと説明すると、このドライバを open() したとき O_SYNC を指定されていなければキャッシュを有効にして mmap() し、O_SYNC を指定されたらキャッシュを無効に、つまり pgprot_noncached() を呼んでから mmap() しています。

なお vma->vm_page_prot は pgprot_t 型の変数で、ページをマップするときの属性を指定するために使います。

API の詳細な意味は特に分からなくても、コードの書き方からして pgprot_noncached() を呼ぶと pgprot_t の値が何か変化するのだろう、ということは分かると思います。

前置き その 2: 追ってみよう pgprot_noncached()

ページをマップするときの属性を変更する際に pgprot_t の値がどう変化するか?を追ってみます。

pgprot_noncached() の実装(ARM 向け)

arch/arm/include/asm/pgtable.h:

#define __pgprot_modify(prot,mask,bits)         \
        __pgprot((pgprot_val(prot) & ~(mask)) | (bits))

#define pgprot_noncached(prot) \
        __pgprot_modify(prot, L_PTE_MT_MASK, L_PTE_MT_UNCACHED)

難しく見えますが大したことはなくて、prot の値を L_PTE_MT_MASK でマスク(つまり bit5〜bit2 の値だけを 0 に書き換え)して、そこに L_PTE_MT_UNCACHED を OR するだけのマクロです。

ここでやっと L_PTE_MT_ なんちゃらが出てきました。長い導入でしたね。でも残念なことに、まだ話の 1/3 も終わってないんですよこれが。

なお L_PTE_MT_ 系マクロの代表的なシンボルと値は下記の通りです。他の定義もありますが、ARMv7 では最上位ビットに意味がない(理由は後でわかります)ので、無視して構いません。

L_PTE_MT_ 系マクロの値

#define L_PTE_MT_UNCACHED       (_AT(pteval_t, 0x00) << 2)      /* 0000 */
#define L_PTE_MT_BUFFERABLE     (_AT(pteval_t, 0x01) << 2)      /* 0001 */
#define L_PTE_MT_WRITETHROUGH   (_AT(pteval_t, 0x02) << 2)      /* 0010 */
#define L_PTE_MT_WRITEBACK      (_AT(pteval_t, 0x03) << 2)      /* 0011 */
#define L_PTE_MT_MINICACHE      (_AT(pteval_t, 0x06) << 2)      /* 0110 (sa1100, xscale) */
#define L_PTE_MT_WRITEALLOC     (_AT(pteval_t, 0x07) << 2)      /* 0111 */
#define L_PTE_MT_DEV_SHARED     (_AT(pteval_t, 0x04) << 2)      /* 0100 */

つまり簡単に言えば pgprot_noncached() を呼ぶと pgprot_t の値の bit5〜bit2 が 2進数の 0000 に書き換えられるってことです。

他にも pgprot_xxxx() 関数は色々ありますが、一例として pgprot_writecombine() を見ると、

pgprot_writecombine() の実装(ARM 向け)

#define pgprot_writecombine(prot) \
        __pgprot_modify(prot, L_PTE_MT_MASK, L_PTE_MT_BUFFERABLE)

このような実装になっていますので、この関数を呼ぶと pgprot_t の値の bit5〜bit2 が 2進数の 0001 に書き換えられます。

追ってみよう remap_pfn_range()

ここまでで pgprot_xxxx() で pgprot_t 型の値を書き換えられること、pgprot_xxxx() に対応した L_PTE_MT_XXXX マクロがあって、bit5〜bit2 が書き換えられること、の 2つが分かりました。

書き換える仕組みはわかっても、pgprot_t 自体が何の役に立つのかがわからないですよね?次に pgprot_t の値がどこでどうやって使われて、なぜキャッシュ有効/無効の設定に寄与するのか?を追いたいと思います。

手がかりは remap_pfn_range() ですので、第五引数に渡した vma->vm_page_prot の値がどこで使われるか?カーネルのコードを追いかけます。

remap_pfn_range() から set_pte_at() まで

 -- remap_pfn_range()
   -- remap_pud_range()
      -- remap_pmd_range()
         -- remap_pte_range()
            pte_t *pte;
            ...
            pte = pte_alloc_map_lock(mm, pmd, addr, &ptl);
            ...
            set_pte_at(mm, addr, pte, pte_mkspecial(pfn_pte(pfn, prot)));

いくつかの関数を経由しますが、最終的にはマップしたいアドレスの pte(Linux のページテーブルエントリ、pte_t 型)を取ってきて、pgprot_t の値と一緒に set_pte_at() 関数に渡されます。

関数がゴチャゴチャ呼ばれてややこしいので、先に pfn_pte() と pte_mkspecial() をやっつけます。

pte_mkspecial() の実装(ARM 向け)

arch/arm/include/asm/pgtable-2level.h: 

static inline pte_t pte_mkspecial(pte_t pte) { return pte; }

ARM では素通しするだけの実装なので、無視して良いです。

pfn_pte() の実装(ARM 向け)

arch/arm/include/asm/pgtable.h: 

#define pfn_pte(pfn,prot)       __pte(__pfn_to_phys(pfn) | pgprot_val(prot))


include/asm-generic/memory_model.h: 

#define __pfn_to_phys(pfn)      PFN_PHYS(pfn)


include/linux/pfn.h: 

#define PFN_PHYS(x)     ((phys_addr_t)(x) << PAGE_SHIFT)

まず pgprot_val() は pgprot_t から値を取り出すマクロです。実は pgprot_t は構造体などの typedef となっていて、prot | 1 のように直接演算できません。察するに、間違って int などを足して、値をぶっ壊す事故を防ぐためだと思われます。

次に __pfn_to_phys() ですが PFN(Page Frame Number, ページフレーム番号)から物理アドレスを得るマクロです。といっても、ページサイズ分だけ左シフトするだけです。ARM の場合はページサイズが 4KB なので、12bit 左シフトします。

最後に __pte() は pte_t 型にキャストするためのマクロです。pgprot_t と同様に pte_t も構造体などの typedef であることが多いので、(pte_t) でキャストするとコンパイラに怒られるのです。

以上を総合すると、pte_mkspecial(pfn_pte(pfn, prot)) がやっていることは、要は (pfn << 12 | prot) なので、


 set_pte_at(mm, addr, pte, (pfn << 12 | prot));

意味だけを見ればこんなもんです(型の問題で実際にこう書くとコンパイルエラーですが…)。

追ってみよう set_pte_at()

さらに渡されたページテーブルエントリと pgprot_t の値の行方を追いかけます。

set_pte_at() から set_pte_ext() まで

-- set_pte_at(..., pte_t *ptep, pte_t pteval)
   -- set_pte_ext(ptep, pteval, ext)
      -- cpu_set_pte_ext(ptep, pteval, ext)
         -- cpu_v7_set_pte_ext(ptep, pteval, ext)

※ext は基本的には 0 です。

最終的にはアセンブラの関数にたどり着きます。実装は arch/arm/mm/proc-v7-2level.S にあります。この関数は第二引数 pteval の値を使って、第一引数 ptep の指す pte_t を書き換えると共に、ARM のハードウェア MMU に渡しているページテーブルの「第 2レベル記述子」も同時に変更する関数です。

前置き その 3: 調べてみよう ARMv7 の MMU

この関数を追う前に、ARMv7 の MMU について少し説明しておきます。

ARMv7 の MMU の第 2レベル記述子の構成は下記の通りです。
(ARM DDI406B B3-10: B3.3.1 Translation table entry formats の表 B3-2より)

ARM MMU の第 2レベル記述子

| bit      |     9|    8 7 6|     5 4| 3| 2| 1|  0|
|----------+------+---------+--------+--+--+--+---|
| Lv2 entry| AP[2]| TEX[2:0]| AP[1:0]| C| B| 1| XN|

一方で Linux の pte_t の構成は下記の通りです。

Linux の pte_t

| bit            |  9|    8|      7|     6| 5 4 3 2|     1|     0|
|----------------+---+-----+-------+------+--------+------+------|
| ARM Linux pte_t| XN| USER| RDONLY| DIRTY| MT[3:0]| YOUNG| VALID|

並べてみます。

Linux の pte_t と ARM MMU の第 2レベル記述子

| bit            |     9|      8|      7|      6|     5 4|     3|     2|     1|     0|
|----------------+------+-------+-------+-------+--------+------+------+------+------|
| ARM Linux pte_t|    XN|   USER| RDONLY|  DIRTY| MT[3:2]| MT[1]| MT[0]| YOUNG| VALID|
| Lv2 entry      | AP[2]| TEX[2]| TEX[1]| TEX[0]| AP[1:0]|     C|     B|     1|    XN|

以降、この表を使って Linux の pte_t の値から、ARM MMU の第 2レベル記述子をどうやって作っていくか?を説明します。

追ってみよう cpu_v7_set_pte_ext()

前置きはこのくらいにして cpu_v7_set_pte_ext() 関数を見ていきます。

この関数は、まず第 2レベル記述子の bit9〜bit4, bit1〜bit0 を 0 クリアして、bit1 と AP[0] (bit4) に 1 をセットします。


| bit            |     9|      8|      7|      6|     5|     4|     3|     2|     1|     0|
|----------------+------+-------+-------+-------+------+------+------+------+------+------|
| ARM Linux pte_t|    XN|   USER| RDONLY|  DIRTY| MT[3]| MT[2]| MT[1]| MT[0]| YOUNG| VALID|
| Lv2 entry      | AP[2]| TEX[2]| TEX[1]| TEX[0]| AP[1]| AP[0]|     C|     B|     1|    XN|
|----------------+------+-------+-------+-------+------+------+------+------+------+------|
| Clear?         | Yes  | Yes   | Yes   | Yes   | Yes  | Yes  | No   | No   | Yes  | Yes  |
| After Clear    |     -|      -|      -|      -|     -|     -|     x|     x|     -|     -|
| After Set      |     -|      -|      -|      -|     -|     1|     x|     x|     1|     -|

次に pte_t の MT[2] を TEX[0] にコピーします。


| bit            |     9|      8|      7|      6|     5|     4|     3|     2|     1|     0|
|----------------+------+-------+-------+-------+------+------+------+------+------+------|
| ARM Linux pte_t|    XN|   USER| RDONLY|  DIRTY| MT[3]| MT[2]| MT[1]| MT[0]| YOUNG| VALID|
| Lv2 entry      | AP[2]| TEX[2]| TEX[1]| TEX[0]| AP[1]| AP[0]|     C|     B|     1|    XN|
|----------------+------+-------+-------+-------+------+------+------+------+------+------|
| MT2 -> TEX0    |     -|      -|      -|  MT[2]|     -|     1|     x|     x|     1|     -|

さらに pte_t が !RDONLY && DIRTY なら AP[2] を 0、それ以外は 1 にし、pte_t の USER を AP[1] にコピーします。


| bit            |     9|      8|      7|      6|     5|     4|     3|     2|     1|     0|
|----------------+------+-------+-------+-------+------+------+------+------+------+------|
| ARM Linux pte_t|    XN|   USER| RDONLY|  DIRTY| MT[3]| MT[2]| MT[1]| MT[0]| YOUNG| VALID|
| Lv2 entry      | AP[2]| TEX[2]| TEX[1]| TEX[0]| AP[1]| AP[0]|     C|     B|     1|    XN|
|----------------+------+-------+-------+-------+------+------+------+------+------+------|
| Set AP         |  0or1|      -|      -|  MT[2]|  USER|     1|     x|     x|     1|     -|

最初の処理で AP[0] を常に 1 にしていましたよね。その値と組み合わせると AP[2:0] の値が完成します。AP[2:0] は ARM の MMU に対して、ページのアクセス権を指示するためのビットフィールドです。

具体的な値の対応表は下記の通りです。値がどういう意味を持つか、横に補足しておきました。


|USER  |RDONLY|DIRTY|AP[2:0] 結果|特権 R|特権 W|ユーザ R|ユーザ W|
|------+------+-----+------------+------+------+--------+--------|
|0     |0     |0    |101         |Yes   |No    |No      |No      |
|0     |0     |1    |001         |Yes   |Yes   |No      |No      |
|0     |1     |0    |101         |Yes   |No    |No      |No      |
|0     |1     |1    |101         |Yes   |No    |No      |No      |
|1     |0     |0    |111         |Yes   |No    |Yes     |No      |
|1     |0     |1    |011         |Yes   |Yes   |Yes     |Yes     |
|1     |1     |0    |111         |Yes   |No    |Yes     |No      |
|1     |1     |1    |111         |Yes   |No    |Yes     |No      |

続いて pte_t の XN ビット(bit9)を XN(bit0)にコピーします。


| bit            |     9|      8|      7|      6|     5|     4|     3|     2|     1|     0|
|----------------+------+-------+-------+-------+------+------+------+------+------+------|
| ARM Linux pte_t|    XN|   USER| RDONLY|  DIRTY| MT[3]| MT[2]| MT[1]| MT[0]| YOUNG| VALID|
| Lv2 entry      | AP[2]| TEX[2]| TEX[1]| TEX[0]| AP[1]| AP[0]|     C|     B|     1|    XN|
|----------------+------+-------+-------+-------+------+------+------+------+------+------|
| Set XN         |  0or1|      -|      -|  MT[2]|  USER|     1|     x|     x|     1|    XN|

この後は、無効なページだったら All 0 にする処理とか、MMU が見ているページテーブルに実際に値を書く処理が続きますが、それは省略します。

追ってみようページテーブルエントリ

既に誰も付いてきていないような気がしますが、ここから ARMv7 の魔術が始まります。

ARMv6 までの MMU をご存じの方であれば、先ほど作成した第 2レベル記述子の値を見たとき「その設定おかしいだろ?」と感じるはずです。私もその一人でした。

何がおかしいかといえば、

  • ARM MMU にて、メモリタイプとキャッシュ属性を指示するための TEX[2:1] が 0 のまま
  • Linux の pte_t にて、メモリタイプとキャッシュ属性を指示するための MT[3:0] のはずなのに、MT[3] を使わない。

辺りがとても不思議に見えて、間違っているのではないかとすら思います。が、しかしこれで間違ってないんです。理由は ARMv7 の MMU には 2つの動作モードがあって、ARMv6 までの動作モードは使っていないからです。

  • モード 1つ目は ARMv6 までと同様の TEX[2:0] と C, B ビットを使って、キャッシュ属性を指定する方法です。
  • モード 2つ目は ARMv7 からの機能で TEX 再マップ(TEX remap)というモードです。実は Linux はこちらを使っています。

TEX 再マップが有効になると、指定できる属性が 8パターンに制限され、TEX の意味が変わります。どの 8パターンを選ぶかは自由で、選び方の作法もあるのですが、余りに細かすぎるのでここでは割愛します。どうしても気になる方はコメントください…。

TEX 再マップを有効にしたとき、ARM MMU の第 2レベル記述子のうち、使われるビットは TEX[0], C, B の 3つのみになります。TEX, C, B ビットの意味も変わり、ARMv6 での TEX, C, B ビットの意味は失われ、8パターンのうち何番目のパターンにするか?を表す数値として解釈されます。

以上を踏まえて先ほどのページテーブルエントリを見直すと、


TEX[0]: MT[2]
C: MT[1]
B: MT[0]

こうなってました。なので MT[2:0] は 8パターンのうち何番を使うか?を表すインデックスそのものを意味していたんですね。

悲しみのビット達

こんな感じで良くできていて感心しますが、使われない悲しいビット達も居ます。

TEX 再マップモードでは、第 2レベル記述子の TEX[2:1] ビットに意味がありません。なので 0 のまま放置されています。

Linux の pte_t の MT[3:0] は 4ビットなので本来 16パターンの表現力があります。しかし ARMv7 の TEX 再マップモードの仕様で 8パターンしか選べませんので、MT[3] は使い道がありません。

「前置き その 2: 追ってみよう pgprot_noncached()」にて L_PTE_MT_ 系マクロの値のうち、MT[3] に値が入っているものを紹介しなかったのはこれが理由です。

まとめ

まとめるの難しいですが、ムリヤリまとめると pgprot_noncached() を prot に指定すると、pte_t の MT[2:0] に 000 が入ります。

これは TEX 再マップモードの ARMv7 MMU にとって、属性のパターン 0 を選びなさいという意味になります。もし pgprot_writecombine() なら pte_t の MT[2:0] には 001 が入り、パターン 1を選びなさい、という意味になります。

参考までに Linux-4.4.1 でのパターン 0 の設定内容は、メモリタイプ Strongly-ordered、内部キャッシュ不可、外部キャッシュ不可です。パターン 1 は、メモリタイプ Normal Memory、内部キャッシュ不可、外部キャッシュ不可です。

編集者: すずき(更新: 2016年 3月 9日 09:09)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2016年 3月 30日

表計算ソフトの列名変換問題

昨日の hdk さんの日記(リンク)を見て、自分も挑戦してみました。

元ネタは 2011年のブログ(リンク)ですね。

列名を数字(atod)と数字を列名(dtoa)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int atod(char *str)
{
        int len = strlen(str);
        int r = 0;
        int i;

        for (i = 0; i < len; i++) {
                r *= 26;
                r += str[i] - 'A' + 1;
        }

        return r;
}

void dtoa(int r, char *buf)
{
        char tmp[256];
        int p = 0;
        int i, len;

        memset(tmp, 0, sizeof(tmp));
        r -= 1;
        while (r >= 0) {
                tmp[p] = 'A' + (r % 26);
                r = r / 26 - 1;
                p++;
        }

        len = strlen(tmp);
        for (i = 0; i < len; i++) {
                buf[len - i - 1] = tmp[i];
        }
}

int main(int argc, char *argv[])
{
        int dir = atoi(argv[1]);
        char *str = argv[2];
        int r;
        char buf[256];

        switch (dir) {
        case 0:
                r = atod(str);
                printf("%d\n", r);
                break;
        case 1:
                memset(buf, 0, strlen(buf));
                dtoa(atoi(str), buf);
                printf("'%s'\n", buf);
                break;
        }

        return 0;
}

掛かった時間は正確に計ってないですが、atod の方が 10分くらいで、dtoa の方が 1時間くらいだったと思います。

2文字目以降を求める式(r = r / 26 - 1)を思いつくのに、予想以上に時間が掛かりました。

動作チェック
$ for i in `seq 1 100` `seq 650 750` `seq 17550 17650`; do echo $i `./a.out 1 $i`; done | egrep "[ABYZ]'"
1 'A'
2 'B'
25 'Y'
26 'Z'
27 'AA'
28 'AB'
51 'AY'
52 'AZ'
53 'BA'
54 'BB'
77 'BY'
78 'BZ'
79 'CA'
80 'CB'
650 'XZ'
651 'YA'
652 'YB'
675 'YY'
676 'YZ'
677 'ZA'
678 'ZB'
701 'ZY'
702 'ZZ'
703 'AAA'
704 'AAB'
727 'AAY'
728 'AAZ'
729 'ABA'
730 'ABB'
17550 'YXZ'
17551 'YYA'
17552 'YYB'
17575 'YYY'
17576 'YYZ'
17577 'YZA'
17578 'YZB'
17601 'YZY'
17602 'YZZ'
17603 'ZAA'
17604 'ZAB'
17627 'ZAY'
17628 'ZAZ'
17629 'ZBA'
17630 'ZBB'

二桁目が A になるとき、二桁目が Z になるとき、三桁目が A になるとき、三桁目が Z になるとき、いずれも特におかしくならないので、他の桁数でもたぶん大丈夫でしょう。

編集者: すずき(更新: 2016年 3月 31日 00:12)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



こんてんつ

open/close wiki
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報