datapath: keep mask array compact when deleting mask
When deleting a mask from the mask array, we always move the last entry
into its current location. Another approach can be NULL in its
current place, and periodically compact it.
The approach taken by this patch is more efficient during run
time. During look up, fast path packet don't have to skip over NULL
pointers.
A more important advantage of this approach is that it tries to
keep the mask array index stable by avoiding periodic index
reshuffle.
This patch implements an optimization to further promote index
stability. By leaving the last entry value intact when moving it
to a new location, the old cache index can 'fix' themselves, by noticing
the index in the cache is outside the valid mask array region. The
new index can be found by scanning the mask pointer within the valid
rtegion.
Signed-off-by: Andy Zhou <azhou@nicira.com>
Acked-by: Pravin B Shelar <pshelar@nicira.com>