4.2 The virtual address space for a process

4.2.1 The user segment

X86プロセッサで特権度3のユーザモードでは,プロセスはユーザセグメントのみにアクセスできる.ユーザセグメントはプロセスが使うデータとコードを内包しており,他のプロセスの所有物であるセグメントとは異なっていなければならない.これはつまり,ページディレクトリか,最新のページテーブルはプロセスごとに異なっていなければならない.

fork システムコールは親プロセスのページディレクトリとページテーブルを子プロセスにコピーする.カーネルセグメントは全プロセスに共有されるので例外.

clone システムコールは,Linux-1.2ではまだできていないので ENOSYS を返す.

fork(2) とは異なり、clone() では、子プロセス (child process) と呼び出し元のプロセスとが、メモリー空間、ファイルディスクリプターのテーブル、シグナルハンドラーのテーブルなどの 実行コンテキストの一部を共有できる。 (このマニュアルにおける「呼び出し元のプロセス」は、通常は 「親プロセス」と一致する。但し、後述の CLONE_PARENT の項も参照のこと)

clone() の主要な使用法はスレッド (threads) を実装することである: 一つのプログラムの中の複数のスレッドはは共有されたメモリー空間で 同時に実行される。

Linuxでは a.out 形式でバイナリが扱われるが,COFFやEOFフォーマットでも実行できる.これらのユーザセグメントの構造はそれぞれ違っている.

a.out 形式の構造は a.out.h で定義されている( include/linux/a.out.h).マクロなどがたくさん定義されている.

...
#ifndef __STRUCT_EXEC_OVERRIDE__

struct exec
{
   unsigned long a_info;     /* アクセスするにはN_MAGICなどのマクロを使う */
   unsigned a_text;      /* textの長さ(bytes) */
   unsigned a_data;      /* dataの長さ(bytes) */
   unsigned a_bss;       /* ファイル用の初期化されていないデータ空間の長さ(bytes) */
   unsigned a_syms;      /* ファイル内のシンボルテーブルデータの長さ(bytes) */
   unsigned a_entry;     /* アドレスの開始 */
   unsigned a_trsize;        /* text用の再割り当て情報の長さ(bytes) */
   unsigned a_drsize;        /* data用の再割り当て情報の長さ(bytes) */
};

#endif /* __STRUCT_EXEC_OVERRIDE__ */
...
/* メモリにロードされたデータセグメントのアドレス.
   ここに書いていないマシンのSEGMENT_SIZEの定義は
   君に任せるよ.  */
#if defined(vax) || defined(hp300) || defined(pyr)
#define SEGMENT_SIZE page_size
#endif
#ifdef  sony
#define SEGMENT_SIZE    0x2000
#endif  /* Sony.  */
#ifdef is68k
#define SEGMENT_SIZE 0x20000
#endif
#if defined(m68k) && defined(PORTAR)
#define PAGE_SIZE 0x400
#define SEGMENT_SIZE PAGE_SIZE
#endif
...

a.out 形式内の各共有ライブラリはそれぞれのアドレス空間に割り当てられる.

ELF形式のバイナリファイルと共有ライブラリの場合,静的なアドレス空間の割り当ては必要ない.ELFは共有ライブラリの再割り当てをサポートしている.

4.2.2 Virtual memory areas

共有ライブラリはものによってはとても大きいかもしれないので,いつも全部のコードを物理メモリにロードするのは得策ではない.共有ライブラリすべての関数をひとつのプロセスが使うわけでもないし,使わない関数は資源の無駄. もし2つのプロセスが同じ実行ファイルを動かすなら,同じのを2つもメモリにロードする必要はない.データセグメントはだいたい一緒.データセグメントは2つのプロセスで共有して,変更があったときはcopy-on-writeする.

仮想メモリのおおまかなコンセプトはLinuxの開発の間に導入された.仮想アドレス空間はvm_area_struct構造体によって定義されている( include/linux/mm.h ).

/*
 * この構造体は仮想メモリマネージャのメモリ空間を定義している. ひとつのタスクにつきひとつの
 * 仮想メモリ(VM)空間がある.  VM空間はハンドラ用の特別なルールを持つ,
 * プロセスの仮想メモリ空間の一部である(例
 * 共有ライブラリ,実行可能な空間など).
 */
struct vm_area_struct {
    struct task_struct * vm_task;       /* VM空間のパラメータ */
    unsigned long vm_start;
    unsigned long vm_end;
    pgprot_t vm_page_prot;
    unsigned short vm_flags;
/* アドレスでソートされた,タスクごとのVM空間のAVL枝 */
    short vm_avl_height;
    struct vm_area_struct * vm_avl_left;
    struct vm_area_struct * vm_avl_right;
/* アドレスでソートされた,タスクごとのVM空間の連結リスト */
    struct vm_area_struct * vm_next;
/* inodeつき空間用.循環リスト inode->i_mmap */
/* shm空間用の付属の循環リスト */
/* そうでなければ使われない */
    struct vm_area_struct * vm_next_share;
    struct vm_area_struct * vm_prev_share;
/* もっと */
    struct vm_operations_struct * vm_ops;
    unsigned long vm_offset;
    struct inode * vm_inode;
    unsigned long vm_pte;           /* 共有メモリ */
};

/*
 * 仮想メモリマネージャの関数 - 空間を開閉し,
 * マッピングを外したり (ディスク上のファイルを最新に保つのを求められた),
 * no-pageまたはwp-page例外が発生したときに呼ばれた関数を指す.
 */
struct vm_operations_struct {
    void (*open)(struct vm_area_struct * area);
    void (*close)(struct vm_area_struct * area);
    void (*unmap)(struct vm_area_struct *area, unsigned long, size_t);
    void (*protect)(struct vm_area_struct *area, unsigned long, size_t, unsigned int newprot);
    void (*sync)(struct vm_area_struct *area, unsigned long, size_t, unsigned int flags);
    void (*advise)(struct vm_area_struct *area, unsigned long, size_t, unsigned int advise);
     unsigned long (*nopage)(struct vm_area_struct * area, unsigned long address,
         unsigned long page, int write_access);
     unsigned long (*wppage)(struct vm_area_struct * area, unsigned long address,
         unsigned long page);
     void (*swapout)(struct vm_area_struct *,  unsigned long, pte_t *);
     pte_t (*swapin)(struct vm_area_struct *, unsigned long, unsigned long);
 };

実体( ipc/shm.c

/*
 * セグメント管理のための各プロセス内部の構造体は
 * `struct vm_area_struct'である.
 * このリストからshmdtは削除され,shmatが加わるだろう.
 * shmd->vm_task        the attacher
 * shmd->vm_start       virt addr of attach, multiple of SHMLBA
 * shmd->vm_end         multiple of SHMLBA
 * shmd->vm_next        next attach for task
 * shmd->vm_next_share  next attach for segment
 * shmd->vm_offset      offset into segment
 * shmd->vm_pte         signature for this attach
 */
static struct vm_operations_struct shm_vm_ops = {
        shm_open,               /* open */
        shm_close,              /* close */
        NULL,                   /* unmap */
        NULL,                   /* protect */
        NULL,                   /* sync */
        NULL,                   /* advise */
        NULL,                   /* nopage (done with swapin) */
        NULL,                   /* wppage */
        NULL,                   /* swapout (hardcoded right now) */
        shm_swap_in             /* swapin */
};

/* forkによって呼び出され,共有メモリがアタッチされる.*/
static void shm_open (struct vm_area_struct *shmd)
{
        unsigned int id;
        struct shmid_ds *shp;

        id = (shmd->vm_pte >> SHM_ID_SHIFT) & SHM_ID_MASK;
        shp = shm_segs[id];
        if (shp == IPC_UNUSED) {
                printk("shm_open: unused id=%d PANIC\n", id);
                return;
        }
        insert_attach(shp,shmd);  /* shmdをshp->attachesへ挿入する */
        shp->shm_nattch++;
        shp->shm_atime = CURRENT_TIME;
        shp->shm_lpid = current->pid;
}

使用例( mm/swap.c

static inline int try_to_swap_out(struct vm_area_struct* vma, unsigned long address, pte_t * page_table)
{
    ...
    if (pte_dirty(pte)) {
        if (mem_map[MAP_NR(page)] != 1)
            return 0;
        if (vma->vm_ops && vma->vm_ops->swapout) {
            vma->vm_task->mm->rss--;
            vma->vm_ops->swapout(vma, address-vma->vm_start, page_table);
        } else {
        ...

Linuxカーネルではプロセスの仮想メモリ空間はdo_mmap関数を使って設定できる( include/linux/mm.h).

extern unsigned long do_mmap(struct file * file, unsigned long addr, unsigned long len,
    unsigned long prot, unsigned long flags, unsigned long off);

実体は mm/mmap.c にある.

unsigned long do_mmap(struct file * file, unsigned long addr, unsigned long len,
        unsigned long prot, unsigned long flags, unsigned long off)
{
    ...
    struct vm_area_struct * vma;
    ...
    vma = (struct vm_area_struct *)kmalloc(sizeof(struct vm_area_struct),
            GFP_KERNEL);
    if (!vma)
        return -ENOMEM;

    vma->vm_task = current;
    vma->vm_start = addr;
    vma->vm_end = addr + len;
    vma->vm_flags = prot & (VM_READ | VM_WRITE | VM_EXEC);
    vma->vm_flags |= flags & (VM_GROWSDOWN | VM_DENYWRITE | VM_EXECUTABLE);

    if (file) {
        if (file->f_mode & 1)
            vma->vm_flags |= VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;
        if (flags & MAP_SHARED) {
            vma->vm_flags |= VM_SHARED | VM_MAYSHARE;
            /*
             * 一見変だが,書き込みのためにファイルを開けなかったとき,
             * 共有マッピングを簡易なプライベートマッピングへ降格できる.
             * これはptrace()が書き込み権限なしに共有マッピングへ
             * 書き込んでしまうセキュリティホールに対処するためだ.
             *
             * VM_MAYSHAREビットを立てておき,/proc/xxx/mapsから
             * ただしい出力を取得するようにする.
             */
            if (!(file->f_mode & 2))
                vma->vm_flags &= ~(VM_MAYWRITE | VM_SHARED);
        }
    } else
        vma->vm_flags |= VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;
    vma->vm_page_prot = protection_map[vma->vm_flags & 0x0f];
    vma->vm_ops = NULL;
    vma->vm_offset = off;
    vma->vm_inode = NULL;
    vma->vm_pte = 0;

    do_munmap(addr, len);   /* 古いマップを綺麗にする */

    if (file)
            error = file->f_op->mmap(file->f_inode, file, vma);
    else
            error = anon_map(NULL, NULL, vma);

    if (error) {
            kfree(vma);
            return error;
    }
    insert_vm_struct(current, vma);
    merge_segments(current, vma->vm_start, vma->vm_end);
    return addr;
}

4.2.3 The system call brk

brkinclude/linux/sched.h で定義されている.タスク構造体内のmm_struct

struct task_struct {
    ...
    struct mm_struct mm[1];
};

brk に関係した mm_structの中身は以下の通り

struct mm_struct {
    ...
    unsigned long start_brk, brk, start_stack, start_mmap;
    ...

プロセスの開始時,ページテーブル内の brk フィールドの値はBSSセグメントの終わりを指すポインタである.これが変更されるなら,プロセスは動的メモリを割り当て,解放できる.このさい標準C関数のmalloc()が呼ばれる.

brkシステムコールは現在のポインタの値を探すか,新しい値をセットするさいに使われる.

この新しい値は整合性の検査に使われる.すなわち,新しい値はもしプライマリかセカンダリのメモリで利用可能なサイズを超えた量のメモリが必要になった場合,それを拒否する.

整合性の検査のあと,カーネル関数sys_brk()do_mmap()を呼ぶ.

asmlinkage int sys_brk(unsigned long brk)
{
        int freepages;
        unsigned long rlim;
        unsigned long newbrk, oldbrk;

        if (brk < current->mm->end_code)
                return current->mm->brk;
        newbrk = PAGE_ALIGN(brk);
        oldbrk = PAGE_ALIGN(current->mm->brk);
        if (oldbrk == newbrk)
                return current->mm->brk = brk;

        /*
         * brkの縮小はいつも許可される
         */
        if (brk <= current->mm->brk) {
                current->mm->brk = brk;
                do_munmap(newbrk, oldbrk-newbrk);
                return brk;
        }
        /*
         * Check against rlimit and stack..
         */
        rlim = current->rlim[RLIMIT_DATA].rlim_cur;
        if (rlim >= RLIM_INFINITY)
                rlim = ~0;
        if (brk - current->mm->end_code > rlim ||
            brk >= current->mm->start_stack - 16384)
                return current->mm->brk;
        /*
         * 既存のmmapマッピングに違反していないか調べる.
         */
        if (find_vma_intersection(current, oldbrk, newbrk))
                return current->mm->brk;
        /*
         * stupidアルゴリズムは利用可能なメモリがあるかどうか決める:
         * とても単純.うまく動くといいな.
         * だまされやすいけれども,多くの間違いは捉えてくれる
         */
        freepages = buffermem >> 12;
        freepages += nr_free_pages;
        freepages += nr_swap_pages;
        freepages -= (high_memory - 0x100000) >> 16;
        freepages -= (newbrk-oldbrk) >> 12;
        if (freepages < 0)
                return current->mm->brk;
#if 0
        freepages += current->mm->rss;
        freepages -= oldbrk >> 12;
        if (freepages < 0)
                return current->mm->brk;
#endif
        /*
         * 大丈夫.使えるメモリはある.いくぞ.
         */
        current->mm->brk = brk;
        do_mmap(NULL, oldbrk, newbrk-oldbrk,
                PROT_READ|PROT_WRITE|PROT_EXEC,
                MAP_FIXED|MAP_PRIVATE, 0);
        return brk;
}

4.2.4 Mapping functions

標準C関数は3つ提供している( /usr/include/sys/mman.h).

/* マップアドレスは近くのADDRから始まりLENバイト分拡がる.
   OFFSETからファイルFD記述子がPROTとFLAGへ記録する.
   もしADDRがゼロでないなら,それは望まれたマッピングアドレスである.
   もしMAP_FIXEDビットがFLAGSにセットされたなら,マッピングはちょうど
   ADDRになるだろう(これはpage-alignedにならなければならない).
   そうしなければ,システムは都合の良い近くのアドレスを選ぶ
   戻り値は実際のマッピングアドレスか,MAP_FAILEDである.
   成功したmmap()は前のマッピングの割り当てを解除する.*/

#ifndef __USE_FILE_OFFSET64
extern void *mmap (void *__addr, size_t __len, int __prot,
               int __flags, int __fd, __off_t __offset) __THROW;
#else
# ifdef __REDIRECT_NTH
extern void * __REDIRECT_NTH (mmap,
                             (void *__addr, size_t __len, int __prot,
                              int __flags, int __fd, __off64_t __offset),
                              mmap64);
# else
#  define mmap mmap64
# endif
#endif
#ifdef __USE_LARGEFILE64
extern void *mmap64 (void *__addr, size_t __len, int __prot,
                     int __flags, int __fd, __off64_t __offset) __THROW;
#endif

/* ADDRからLENバイト拡がる領域のためにマッピングの割り当てを解除する.
   もし成功したなら0が帰る.-1が帰るとエラーである.*/
extern int munmap (void *__addr, size_t __len) __THROW;

/* PROTのために,ADDRからLENバイト拡がる領域のメモリプロテクションを変える.
   成功したなら0を,失敗したなら-1を返す.
   (そしてerrnoをセットする).  */
extern int mprotect (void *__addr, size_t __len, int __prot) __THROW;

これはオンラインマニュアルを読んだほうが早い.

4.2.5 The kernel segment

システム関数が初期化されたとき,プロセッサはシステムモードに切り替わる.x86アーキテクチャでは,Linuxシステムコールはソフトウェア割り込み128(0x80)が起こったとき初期化される.プロセッサはその後割り込み記述子テーブルに格納されているゲート記述子を読む.これは kernel/sys_call.S 内の system_call アセンブラルーチンを指すトラップゲート記述子である.

プロセッサはカーネルセグメントを指すCSレジスタ内のセグメント記述子のアドレスへジャンプする.その後アセンブラルーチンはDSとESレジスタ内のセグメントセレクタにセットする.このような方法でメモリアクセスはカーネルセグメントのデータを読み書きする.

カーネルセグメントのページテーブルはどのプロセスでも同じ.これはシステムモードのプロセスが同じカーネルセグメントに遭遇するのを保証する.カーネルセグメントでは,物理アドレスと仮想アドレスは,仮想アドレスがvmalloc()によってマッピングされるのを除いて同じ.

4.2.6 Static memory allocation in the kernel segment

メモリを段々と確保していく.

...
static unsigned long memory_start = 0;
...
asmlinkage void start_kernel(void)
{
        char * command_line;
/*
 * 割り込みはしばらく無効になる.
 * セットアップが成功したあとに有効になる.
 */

        setup_arch(&command_line, &memory_start, &memory_end);
        memory_start = paging_init(memory_start,memory_end);
        ...
        memory_start = console_init(memory_start, memory_end);
        memory_start = bios32_init(memory_start, memory_end);
        ...

4.2.7 Dynamic allocation of memory in the kernel segment

システムカーネルでは一時的なバッファのために動的にメモリを割り当てる必要がある.Linuxではkmalloc()kfree()を使う( mm/kmalloc.c).

void * kmalloc (size_t size, int priority)
{

void kfree_s (void *ptr, int size)
{

include/linux/malloc.h

#define kfree(x) kfree_s((x), 0)

kfree()はマクロ.

kmalloc()アルゴリズムは必要なサイズに合うブロックを担当しているメモリ空間の空きブロックすべてを検索する.見つからなかった場合,新しいメモリ空間と空きブロックを設定しなければならない.一度ブロックが見つかるか利用可能なものを作ったら,メモリ空間の空きブロックのリストから取り除き,それを占有する.

kfree()は占有されているブロックを解放する.

カーネルの古いバージョンではkmalloc()はカーネルのメモリの動的割り当てしか提供していない.加えて,メモリの量はひとつのメモリのページに限られる.複数のページを扱うにはvmalloc()vmfree()を使う.これらの関数は mm/vmalloc.c で定義されている.