コグノスケ


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)

コメント一覧

コメントはありません。

この記事にコメントする

2016年 3月 30日

permalink

編集する

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

昨日の 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)