The actual data structures for a ``toy'' implementation of allocator
caches are shown in
Figure .
The ``Global Pool'' of Figure
is implemented by globalmem of type struct globalmempool,
and the two CPU pools by the per-CPU variable percpumem of
type percpumempool.
Both of these data structures have arrays of pointers to blocks
in their pool fields, which are filled from index zero upwards.
Thus, if globalmem.pool[3] is NULL, then the remainder of
the array from index 4 up must also be NULL.
The cur fields contain the index of the highest-numbered full
element of the pool array, or -1 if all elements are empty.
All elements from globalmem.pool[0] through
globalmem.pool[globalmem.cur] must be full, and all the rest
must be empty.7.8
The operation of the pool data structures is illustrated by
Figure ,
with the six boxes representing the array of pointers making up
the pool field, and the number preceding them representing
the cur field.
The shaded boxes represent non-NULL pointers, while the empty
boxes represent NULL pointers.
An important, though potentially confusing, invariant of this
data structure is that the cur field is always one
smaller than the number of non-NULL pointers.
Paul E. McKenney 2011-12-16