get_swap_page関数でスワップアウトする領域が決定すると、その領域のswap_info識別子を引数で、scan_swap_map関数でスワップページ（スワップスロットが取得される。）スワップスロットはswap_info識別子に紐づく配列で、スワップ領域内でスワップページ使用／未使用を管理していて、スワップスロットの取得とはこの配列の0であるインデックスを検索することである。

凡人が考えるところでは、頭からその配列が0であるところを検索すればよさそうだが、そこは頭のいい人が考えたことでそんな実装はしていない。まず、ターゲットの領域から固まった領域を取得する。これをスワップクラスタというそうで、その数を256としている。すなわちまずスワップクラスタを取得し、そこからページを割り当てる。そしてそのスワップクラスタ内のページを使い切ったら、再度スワップクラスタを取得し同じような処理を繰り返す。そしてスワップクラスタが割り当てられなくなったら、先頭から凡人の考える方法で検索するというものだ。

実装を見てみよう。まずsi->cluster_nrでスワップクラスタ内の未使用領域をチェックする。0ならクラスタが無い。従ってクラスタを取得しに行く。最初に未使用ページスロット数がクラスタ数より少なければ、先頭（未使用のという意味で。）から検索しにいく。クラスタ検索開始位置をoffset = si->lowest_bitとする。lowest_bitはそれより前は使用中という指針である。そしてクラスタ検索終了位置をlast_in_cluster = offset + SWAPFILE_CLUSTER - 1として、highest_bit（それ以降は使用中という指針）まで、クラスタ検索開始位置からクラスタ検索終了位置まで、未使用であるかチェックする。途中使用のスロットが現れると、クラスタ検索終了位置を更新し、そこから再度クラスタ分チェックすることになる。

もし、クラスタが獲得できれば、si->cluster_nextからスロットを獲得することになる。cluster_nextはくラスタ獲得時において、si->cluster_next = offset-SWAPFILE_CLUSTER+1とし、クラスタの先頭が設定されている。あとはsi->cluster_nextから取得をこころみ、lowest_bit、highest_bit、cluster_nexを次回の所得のために更新する。

もしクラスタに残存スロットがあればクラスタ獲得の処理はスキップし、si->cluster_nr--で残存クラスタ数を減産後、同じ処理となる。

そして、クラスタが獲得できない場合、offset = si->lowest_bitとし、その位置のスロットをチェックする。もし使用中なら、highest_bitまでチェックすることになる。

なお、クラス獲得およびlowest_bitからのシーケンス検索において、LATENCY_LIMITとして、その回数検索したらいったんcond_reschedを起動するようにしている。

#define SWAPFILE_CLUSTER        256
#define LATENCY_LIMIT           256

static inline unsigned long scan_swap_map(struct swap_info_struct *si)
{
       unsigned long offset, last_in_cluster;
       int latency_ration = LATENCY_LIMIT;

       si->flags += SWP_SCANNING;
       if (unlikely(!si->cluster_nr)) {
               si->cluster_nr = SWAPFILE_CLUSTER - 1;
               if (si->pages - si->inuse_pages < SWAPFILE_CLUSTER)
                       goto lowest;
               spin_unlock(&swap_lock);

               offset = si->lowest_bit;
               last_in_cluster = offset + SWAPFILE_CLUSTER - 1;

               /* Locate the first empty (unaligned) cluster */
               for (; last_in_cluster <= si->highest_bit; offset++) {
                       if (si->swap_map[offset])
                               last_in_cluster = offset + SWAPFILE_CLUSTER;
                       else if (offset == last_in_cluster) {
                               spin_lock(&swap_lock);
                               si->cluster_next = offset-SWAPFILE_CLUSTER+1;
                               goto cluster;
                       }
                       if (unlikely(--latency_ration < 0)) {
                               cond_resched();
                               latency_ration = LATENCY_LIMIT;
                       }
               }
               spin_lock(&swap_lock);
               goto lowest;
       }

       si->cluster_nr--;
cluster:
       offset = si->cluster_next;
       if (offset > si->highest_bit)
lowest:         offset = si->lowest_bit;
checks: if (!(si->flags & SWP_WRITEOK))
               goto no_page;
       if (!si->highest_bit)
               goto no_page;
       if (!si->swap_map[offset]) {
               if (offset == si->lowest_bit)
                       si->lowest_bit++;
               if (offset == si->highest_bit)
                       si->highest_bit--;
               si->inuse_pages++;
               if (si->inuse_pages == si->pages) {
                       si->lowest_bit = si->max;
                       si->highest_bit = 0;
               }
               si->swap_map[offset] = 1;
               si->cluster_next = offset + 1;
               si->flags -= SWP_SCANNING;
               return offset;
       }

       spin_unlock(&swap_lock);
       while (++offset <= si->highest_bit) {
               if (!si->swap_map[offset]) {
                       spin_lock(&swap_lock);
                       goto checks;
               }
               if (unlikely(--latency_ration < 0)) {
                       cond_resched();
                       latency_ration = LATENCY_LIMIT;
               }
       }
       spin_lock(&swap_lock);
       goto lowest;

no_page:
       si->flags -= SWP_SCANNING;
       return 0;
}

スワップ領域は実メモリーの２倍と言われている。その根拠は確たるものはないようだ。少なくともスワップ領域を検索する上、実メモリの2倍が前提で処理を高速化するようなところは見当たらない。それはともかく、３２ビットOSで上記の推奨値でスワップ領域を設定すると、実メモリを２Gとすると４Gとなる。そして４K単位でスワップページを管理しているわけで、そのスロット数は1000000であり、実際スワップ識別子において24ビットとして管理していおり、そのサイズの最大値は2＾24×4096K=64GBとなる。

大容量のスワップ領域を必要としない宅内で趣味で使っている環境だけに、スワップ検索でこうもこった実装をと思ったものだが、なるほどここまで大規模のシステムとして、サポートするスワップ領域をかんがみての実装かと思うと、ただただ頭の下がる思いである。