To speed up the search for free page slots, the kernel keeps the lowest_bit and highest_bit fields of each swap area descriptor up to date. These fields specify the first and the last page slots that could be free; in other words, any page slot below lowest_bit and above highest_bit is known to be occupied.
220.127.116.11 The scan_swap_map( ) function
The scan_swap_map( ) function is used to find a free page slot in a given swap area. It acts on a single parameter, which points to a swap area descriptor and returns the index of a free page slot. It returns 0 if the swap area does not contain any free slots. The function performs the following steps:
1. It tries first to use the current cluster. If the cluster_nr field of the swap area descriptor is positive, it scans the swap_map array of counters starting from the element at index cluster_next and looks for a null entry. If a null entry is found, it decrements the cluster_nr field and goes to Step 4.
2. If this point is reached, either the cluster_nr field is null or the search starting from cluster_next didn't find a null entry in the swap_map array. It is time to try the second stage of the hybrid search. It reinitializes cluster_nr to SWAPFILE_CLUSTER and restarts scanning the array from the lowest_bit index that is trying to find a group of swapfile_cluster free page slots. If such a group is found, it goes to Step 4.
3. No group of swapfile_cluster free page slots exists. It restarts scanning the array from the lowest_bit index that is trying to find a single free page slot. If no null entry is found, it sets the lowest_bit field to the maximum index in the array, the highest_bit field to 0, and returns 0 (the swap area is full).
4. A null entry is found. Puts the value 1 in the entry, decrements nr_swap_pages, updates the lowest_bit and highest_bit fields if necessary, and sets the cluster_next field to the index of the page slot just allocated plus 1.
5. Returns the index of the allocated page slot.
18.104.22.168 The get_swap_page( ) function
The get_swap_page( ) function is used to find a free page slot by searching all the active swap areas. The function, which returns the index of a newly allocated page slot or 0 if all swap areas are filled, takes into consideration the different priorities of the active swap areas.
Two passes are necessary. The first pass is partial and applies only to areas that have a single priority; the function searches such areas in a round-robin fashion for a free slot. If no free page slot is found, a second pass is made starting from the beginning of the swap area list; during this second pass, all swap areas are examined. More precisely, the function performs the following steps:
1. If nr_swap_pages is null or if there are no active swap areas, returns 0.
2. Starts by considering the swap area pointed to by swap_list.next (recall that the swap area list is sorted by decreasing priorities).
3. If the swap area is active and not being deactivated, invokes scan_swap_map( ) to allocate a free page slot. If scan_swap_map( ) returns a page slot index, the function's job is essentially done, but it must prepare for its next invocation. Thus, it updates swap_list.next to point to the next swap area in the swap area list, if the latter has the same priority (thus continuing the round-robin use of these swap areas). If the next swap area does not have the same priority as the current one, the function sets swap_list.next to the first swap area in the list (so that the next search will start with the swap areas that have the highest priority). The function finishes by returning the identifier corresponding to the page slot just allocated.
4. Either the swap area is not writable, or it does not have free page slots. If the next swap area in the swap area list has the same priority as the current one, the function makes it the current one and goes to Step 3.
5. At this point, the next swap area in the swap area list has a lower priority than the previous one. The next step depends on which of the two passes the function is performing.
a. If this is the first (partial) pass, it considers the first swap area in the list and goes to Step 3, thus starting the second pass.
b. Otherwise, it checks if there is a next element in the list; if so, it considers it and goes to Step 3.
6. At this point the list is completely scanned by the second pass and no free page slot has been found; it returns 0.
22.214.171.124 The swap_free( ) function
The swap_free( ) function is invoked when swapping in a page to decrement the corresponding swap_map counter (see Table 16-1). When the counter reaches 0, the page slot becomes free since its identifier is no longer included in any Page Table entry. We'll see in the later section Section 16.3, however, that the swap cache counts as an owner of the page slot.
The function acts on a single entry parameter that specifies a swapped-out page identifier and performs the following steps:
1. Derives the swap area index and the offset page slot index from the entry parameter and gets the address of the swap area descriptor.
3. If the swap_map counter corresponding to the page slot being freed is smaller than swap_map_max, decrements it. Recall that entries that have the swap_map_max value are considered persistent (undeletable).
4. If the swap_map counter becomes 0, increments the value of nr_swap_pages and updates, if necessary, the lowest_bit and highest_bit fields of the swap area descriptor.
I [email protected] RuBoard
Was this article helpful?