Scalable Statistics Counters

Overview:

The basic idea behind the approach is to have per cpu versions of these counters and update per-cpu versions. The per cpu versions can be consolidated on a read request to the counter. This improves performance significantly in multiprocessor environments by reducing the bouncing of the counter cache lines among different CPUs. At the same time, this implementation switches to code that is completely devoid of overheads for SMP when compiled without CONFIG_SMP option set.

Interfaces:

Counters where exactness is not important (like statistics counters) can be declared as of type statctr_t. This is an opaque type and users of the counters do not need to bother about its fields. For an SMP kernel (CONFIG_SMP=y), this is a structure that has information which can be used to quickly compute the appropriate per-cpu counter. For uniprocessor kernel, this is just a unsigned long and thus there is no overhead.

	#ifdef CONFIG_SMP
	typedef struct statctr {
		pcpu_ctr_t *ctr;
	} statctr_t;
	#else
	typedef unsigned long statctr_t;
	#endif

1. int statctr_init(statctr_t *stctr, unsinged long value)
2. int statctr_ninit(statctr_t *stctr, int count, unsinged long value)

All statctrs must be initialized using one of these interfaces. These counters cannot be just used by statically allocating statctr_t types at compile time, simply because the counter is going to refer to per cpu versions in different cachelines (which is going to be allocated during statctr_init()). Counters allocated using these functions must be freed using statctr_cleanup() or statctr_ncleanup(). For, uniprocessor kernels, statctr_init()/statctr_ninit() reduce to simply initializing the unsigned long counter or an array of them, there is no separate allocation involved here. These functions return 0 on success and a non-zero value on failure.
3. void statctr_cleanup(statctr_t *stctr)
4. void statctr_ncleanup(statctr_t *stctr, int count)

These interfaces must be used to free statistics counters initialized using statctr_init() or statctr_ninit() respectively. These function frees up the per-cpu counter(s)/internal data structure(s) allocated during statctr_init() or statctr_ninit(). They are NOP for uniprocessor kernels.
5. void statctr_inc(statctr_t *stctr)

This interface increments the counter by one. Internally, only the per-cpu counter is incremented. For uniprocessor kernels, it simply non-atomically increments the unsigned long statistics counter.
6. void statctr_dec(statctr_t *stctr)

Decrements the counter by one. Internally, only the per-cpu counter is decremented. For uniprocessor kernels, it non-atomically decrements the counter.
7. void statctr_add(statctr_t *stctr, unsigned long addend)

Adds the addend value to counter. Internally, only the per-cpu counter is added for SMP kernels.
8. void statctr_sub(statctr_t *stctr, unsigned long subtrahend)

Subtracts the subrtrahend value from the counter. Internally, only the per-cpu counter is updated for SMP kernels.
9. unsigned long statctr_read(statctr_t *stctr)

Returns the counter value. This function reads all of the per-cpu versions of this counters, adds them and returns to the caller. For uniprocessor kernels, it just returns the value of the counter.
10. void statctr_set(statctr_t *stctr, unsigned long i)

Sets the statctr to the value i. If statctr_read() is invoked on a counter after statctr_set(), the return value should reflect the value set.

Statistics Counter Maintenance:

             CPU #0                  CPU #1
	-----------------	-----------------       ^
	|		|	|		|	|
	|   counter #0  |       |  counter #0   |	|
	|		|	|		|	|
	-----------------	-----------------	|
	|		|	|		|	|
	|   counter #1  |       |  counter #1   |	|
	|		|	|		|	|
	-----------------	-----------------	|
	|		|	|		|	|
	|   counter #3  |       |  counter #2   |	|
	|		|	|		|
	-----------------	----------------- SMP_CACHE_BYTES
	|		|	|		|	
	|   counter #4  |       |  counter #4   |	|
	|		|	|		|	|
	-----------------	-----------------	|
	|		|	|		|	|
	|		|	|		|	|
	|		|	|		|	|
	-----------------	-----------------	|
               .                        .		|
               .                        .		|
               .                        .		|
               .                        .		|
               .                        .		|
               .                        .		v

We use a separate allocator to allocate and maintain interlaced per-cpu counters. Currently there are two implementations of this allocator - Fixed and Flexible. They differ in flexibility provided, specially with respect to handling addition or removal of CPUs in the system. The statctr implementation uses a common set of APIs to access the per-cpu counters irrespective of the underlying allocator. A per-cpu counter is represented by an opaque type pcpu_ctr_t. The APIs are -

1. pcpu_ctr_t *pcpu_ctr_alloc(int flag)

This allocates a per-CPU counter including all the data structures necessary in the underlying implementation. Returns NULL on failure.
2. pcpu_ctr_t *pcpu_ctr_free(pcpu_ctr_t *ctr)

Frees the counter.
3. unsigned long *PCPU_CTR(pcpu_ctr_t *ctr, int cpu)

Given a cpu, returns a pointer to its own version of the counter.

Fixed counters:

  my_struct
  ------------
  |          |
  | statctr0 |------|
  |          |      v
  -----------        -----------------    ^
  |          |       |	             |    |
  | statctr1 |----   |   counter #0  |    |
                 |   |	             |    |
                 --> -----------------    |
		     |		     | SMP_CACHE_BYTES
		     |   counter #1  | (for CPU #0)
		     |		     |    |
		     -----------------    |
		             .            |
		             .            |
		     |		     |    v
		     -----------------    ^
		     |		     |    |
		     |   counter #0  |    |
		     |		     |    |
		     -----------------    |
		     |		     | SMP_CACHE_BYTES
		     |   counter #1  | (for CPU #1)
		     |		     |    |
		     -----------------    |
		            .        
		            .       
		            .      
		            .     
		            .    

The statctr_t opaque type contains a pointer to the CPU #0 version of the statistics counter. This pointer resides on line 0 of the statctr_t block (of size smp_num_cpus * SMP_CACHE_BYTES). The address of the per-cpu version of this counter is computed using pointer arithmatic.

typedef void *pcpu_ctr_t;

#define PCPU_CTR(ctr,cpu) \
       ((unsigned long *)(ctr + SMP_CACHE_BYTES * cpu))

static __inline__ void statctr_inc(statctr_t *stctr)
{
	(*PCPU_CTR(statctr->ctr, smp_processor_id()))++;
}

Because SMP_CACHE_BYTES will be a power of 2, reasonable compliers would generate code without using costlier instructions.

Flexible counters:

1. Each statctr is represented by a an array of size NR_CPUS that contains the pointers to the per-cpu versions of the counters. Initially we fill out the array with the pointers for the currently online CPUs. Onlining/Offlining would only requiring updates to the affected CPUs entry in this array. The data structures that contain the statctr will not need any modification and will continue to available to other CPUs for increment/decrement/read operations.

                  ---------------          ---------------
                  |             |          |             |
                  |    next     |--------->|     next    |--------->
                  |             |          |             |
		  ---------------          ---------------
                  |             |          |             |
                  |             |          |             |
                  |             |          |             |
                  ---------------          --------------
                         |                        |
   my_struct             |                        |
  -----------            |
  |         |            v
  | statctr |----->---------------
  |         |  ^  |              |
  ----------   |  |   CPU #0     |--------->-----------------  ^
  |         |  |  |              |          |                |  |
  |         |  |  ----------------          |                |  |
               |  |              |          |                |  |
               |  |   CPU #1     |----      |                |  |
          NR_CPUS |              |   |      |                | SMP_CACHE_BYTES
               |  ----------------   |      |                |  |
               |  |              |   |      |                |  |
               |  |   CPU #2     |   |      |                |  |
               |  |              |   |      |                |  v
               |  ----------------   ------>------------------  
               |  |              |          |                |
               |          .                 |                |
               |          .                 |                |
               |          .                 |                |
               |          .                 |                |
               v

2. The allocator maintains the counters in counter blocks. Each block consists of an array of size NR_CPUS with each element corresponding to an online CPU pointing to a cacheline sized, cacheline aligned counter chunk (of SMP_CACHE_BYTES). These chunks are allocated using the existing kmem_cache_alloc() slab allocator. The counter block also has a free list to allocate a single counter within itself.
3. The fast path code (increment/decrement) involves an extra load to get the given CPUs version of the counter, but it isn't likely to be as significant compared to the savings since the extra load will not result in cache line bouncing.

   
   typedef struct pcpu_ctr_s {
          void *arr[NR_CPUS];     /* Pcpu counter array */
          void *blkp;             /* Pointer to block from which ctr was
                                     allocated from (for use with free code) */
   } pcpu_ctr_t;
   
   #define PCPU_CTR(ctr, cpuid) ((unsigned long *)ctr->arr[cpuid]) 
   
   static __inline__ void statctr_inc(statctr_t *statctr)
   {
   	(*PCPU_CTR(statctr->ctr, smp_processor_id()))++;
   }
   

4. We may maintain a list of all such counters allocated (linked list of the counter pointer-arrays). During onlining or offlining CPUs, this list is to be traversed and the corresponding pointer in the array updated. There is no locking here necessary since different CPUs will change their own pointers. Of course locking is needed for creating new counters.
5. If the number of CPUs in the system decreases, then we can live with letting the previously allocated cache lines be around unused. If the number of CPUs increase, then we need to allocate an additional cache line for each additional CPU.
6. This scheme will also handle sparse CPU numbers.

Results:

All measurements were done in a 8-way PIII 700MHz Xeon (1MB L2 cache) machine with 4GB RAM.

Microbenchmarking:

Obvservations:

• 6 cycles per global counter increment includes the overhead of loop termination check and a delay of couple of cycles to allow cacheline requests from other CPUs to come in before the next increment. This is a more realistic scenerio.
• Single processor cost (11 cycles) is greater for statctr, but the measurements were done using an SMP kernel. In UP kernel, statctrs are reduced to a long..
• The cost of statctr while greater is negated by cacheline delays with global counters enough that we see benefits from 2 CPUs upwards for frequently used counters.
• Other than negligible associativity misses, statctr implementation doesn't have any bad cache overhead.

Tbench over loopback:

Obvservations:

• Cost of statctr is higher for 1 processor, but that is for SMP kernels, for UP kernels, statctr is a long.
• Effect of cacheline bouncing in loopback_xmit under tbench load is sufficient enough to see benefit of statctr from 2 CPUs upwards.
• The flattening of the cost curve from 2 CPUs upward is probably due to the fact that loopback_xmit() is serialized. The cacheline related delay is always limited to getting a modified cacheline and there aren't multiple CPUs trying to modify the cacheline simultaneously.

Download: