7.4.3.3 Data Structures

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

Figure: Allocator-Cache Data Structures
\begin{figure}{ \scriptsize
\begin{verbatim}1  ...

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.

Figure: Allocator Pool Schematic
\resizebox{3in}{!}{\includegraphics{SMPdesign/AllocatorPool}}

Paul E. McKenney 2011-12-16