Victim list Management

The best candidate for victimization is a RAID1 stripe that has not been accessed for the longest time. But we found searching through the entire maptable for finding such a perfect victim to be extremely time consuming loading the host CPU. The problem is even more serious for a kernel module as kernel threads are not preempted when they run out of their time slice (even in Solaris 2.5.1, a kernel thread is preempted only if a higher priority thread becomes runnable), affecting all other processes and drastically reducing the system response. To reduce the amount of searching, we implemented victim lists.

A victim list is a list of RAID1 stripes that are sorted in the increasing order of access frequency. This list is consulted to find a victim but only as a hint. The stripe is again checked to see if it still remains a RAID1 stripe, or if it had any accesses after the (re)construction of the list, or if there is an access currently active against it. If any of these conditions is true, the entry is dropped and the next entry in the list is checked.

When the list is exhausted, it is reconstructed by searching through the maptable populating the list with RAID1 stripes that do not have their access bit set, and do not have any accesses active against them.

In the current implementation, victim list reconstruction is done by a kernel thread. This thread sleeps waiting for requests and, on being woken up with a request, does the reconstruction and sleeps again till the next request. The size of the list is fixed at 4096. A victim can be sought in either blocking and non-blocking mode. In the blocking mode, on failing to find a victim, the calling thread is suspended till the reconstruction of the victim list is done. This mode is used for invalid-RAID5 migrations which can not continue till a victim is obtained. In non-blocking mode, if no victim can be found, the victim list reconstruction thread is signalled with a request and the call immediately returns failure. This mode is used by RAID5-RAID1 migrations.