コグノスケ


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/03/08 23:13)

コメント一覧

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



2016年3月3日

懐かしい

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

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

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

編集者:すずき(2016/03/08 23:15)

コメント一覧

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



2016年3月7日

スマホの電池

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


電池残量

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

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

編集者:すずき(2016/03/08 23:24)

コメント一覧

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



2016年3月8日

LinuxとARMv7 MMUの魔術

目次: Linux

超マニアックです。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、内部キャッシュ不可、外部キャッシュ不可です。

編集者:すずき(2023/04/29 21:35)

コメント一覧

  • コメントはありません。
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/03/31 00:12)

コメント一覧

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



こんてんつ

open/close wiki
open/close Linux JM
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 2024年
open/close 過去日記について

その他の情報

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