YOS OPENSONAR

  2. >
  3. freebsd
  4. >
  5. man
  6. >
  7. ja
  8. >
  9. man9
  2. >
  3. freebsd
  4. >
  5. man
  6. >
  7. ja
  8. >
  9. man9
EN JA
VM_MAP_ENTRY_RESIZE_FREE(9)
VM_MAP_ENTRY_RESIZE_FREE(9) FreeBSD Kernel Developer's Manual VM_MAP_ENTRY_RESIZE_FREE(9)

名称

vm_map_entry_resize_free — vm マップ空き空間アルゴリズム

書式

#include < sys/param.h>
#include < vm/vm.h>
#include < vm/vm_map.h>

void
vm_map_entry_resize_free( vm_map_t map, vm_map_entry_t entry);

解説

このマニュアルページは、VM マップ空き空間アルゴリズムで使用される vm_map_entry フィールドに関して、どのように、これらの変数の一貫性と vm_map_entry_resize_free() 関数を保持するかについて説明しています。

VM マップエントリは二重リンクリスト ( prev と next ポインタ) と二分検索ツリー ( left と right ポインタ) として構成されています。検索ツリーは、 Sleator と Tarjan splay ツリーとして構成されており、また、“self-adjusting tree” (自動調整ツリー) としても知られています。

struct vm_map_entry { 
        struct vm_map_entry *prev; 
        struct vm_map_entry *next; 
        struct vm_map_entry *left; 
        struct vm_map_entry *right; 
        vm_offset_t start; 
        vm_offset_t end; 
        vm_offset_t avail_ssize; 
        vm_size_t adj_free; 
        vm_size_t max_free; 
        ... 
};

空き空間アルゴリズムは struct vm_map_entry に 2 つのフィールドを追加します: adj_free と max_free です。 adj_free フィールドは空きアドレス空間の総量であり、直後に (より高いアドレスに) マップエントリが続きます。このフィールドはマップヘッダで未使用です。 adj_free は、splay ツリーではなく、リンクリストによって決まり、 adj_free は、次のように計算することができることに注意してください。

entry->adj_free = (entry->next == &map->header ? 
    map->max_offset : entry->next->start) - entry->end;

max_free フィールドはエントリのサブツリーで隣接する空き空間の最大の総量です。 max_free は、リンクリストではなく、splay ツリーによって決まり、 max_free は、それ自体の adj_free の最大と、左と右のサブツリーの max_free を取ることによって計算されることに注意してください。また一方、 max_free はマップヘッダで未使用です。

これらのフィールドは vm_map_findspace() の O( log n) 実装を考慮に入れます。 max_free を使用して、直ちに全体のサブツリーで大きい空き領域をテストすることができます。これは、ツリーの 1 つ下のパスで与えられたサイズの最初に適任の空き領域を見つけるのが可能になるので、 splay ツリーを使用して O( log n) は償却しました。訳注: 意味不明。

空き領域がサイズを変更するとき、以前のマップエントリで adj_free と max_free を更新して、 max_free を上のツリーに伝播しなければなりません。これはエントリを挿入して、削除する場合のために vm_map_entry_link() と vm_map_entry_unlink() で取り扱われます。 vm_map_entry_link() が新しいエントリと前のエントリの両方を更新して、 vm_map_entry_unlink() が前のエントリを更新することに注意してください。また、 max_free は実際にツリー上に伝播されないことに注意してください。代わりに、そのエントリは最初に root に splay され、次に、変更はそこで行われます。これは、splay ツリーの一般的なテクニックであり、またマップエントリがツリーに対してどのようにリンクされ、アンリンクされるかということです。

vm_map_entry_resize_free() 関数は、与えられた entry で空き空間変数を更新して、それらの値をツリー上に伝播します。この関数は、マップエントリが適切な位置でリサイズされるときはいつも、呼び出されるべきです、すなわち、 start または end の値を変更することによってです。利用者が、 end を変更するなら、そのエントリをリサイズするべきですが、 start を変更するなら、前のエントリをリサイズするべきであることに注意してください。マップは、この関数を呼び出す前にロックされなければなりません、そして、また一方、 max_free を伝播することは、そのエントリをルートに splay することによって実行されます。

使用例

vm_map_insert() でマップエントリを追加することを考慮してください。 

ret = vm_map_insert(map, object, offset, start, end, prot, 
    max_prot, cow);

この場合は、これ以上の動作は、空き空間変数の一貫性を保持するために必要ではありません。 vm_map_insert() 関数は、新しいエントリと前のエントリの両方を更新する vm_map_entry_link() を呼び出します。これは vm_map_delete() と vm_map_entry_link() または vm_map_entry_unlink() を直接呼び出すことと同等です。

今度は、 vm_map_entry_link() または vm_map_entry_unlink() への呼び出しなしで、適切な場所でにエントリをリサイズすることを考慮してください。

entry->start = new_start; 
if (entry->prev != &map->header) 
        vm_map_entry_resize_free(map, entry->prev);

この場合は、 start を再設定することは、前のエントリに続いて、空き空間の総量を変更します。したがって、前のエントリを更新するために vm_map_entry_resize_free() を使用します。

最後に、エントリの end アドレスを変更すると仮定してください。

entry->end = new_end; 
vm_map_entry_resize_free(map, entry);

ここで、エントリ自体で vm_map_entry_resize_free() を呼び出します。

関連項目

vm_map(9), vm_map_findspace(9) Daniel D. Sleator and Robert E. Tarjan, Self-Adjusting Binary Search Trees, JACM, vol. 32(3), pp. 652-686, July 1985.

歴史

splay ツリーは、 FreeBSD 5.0 の VM マップに追加され、 O( log n) ツリーベースの空き空間アルゴリズムは、 FreeBSD 5.3 で追加されました。

作者

ツリーベースの空き空間アルゴリズムとこのマニュアルページは、 Mark W. Krentel <krentel@dreamscape.com>によって書かれました。
August 17, 2004 FreeBSD