WL#6906: Improve locality of reference by allocating trx_t in blocks

Status: Complete

trx_t instances are allocating on the heap at random locations. This imposes a 
cost when iterating over the transactions.
Allocate memory in configurable sized blocks that are a multiple of sizeof(trx_t).  
Put the trx_t instances on a priority queue that is ordered on their memory 
addresses so that when we allocate trx_t instances from the pool they are close 
together.

When a transaction is freed the instance is released back into the pool.
The public interface of the pool. Each instance is prefixed with a pointer to the 
pool that is belongs. When we free the instance we get the pointer to the pool 
that it belongs to and then request that pool instance to add the object to the 
priority queue.

template 
struct Pool {

        typedef Type value_type;

        struct Element {
                Pool*           m_pool;
                value_type      m_type;
        };

        /** Constructor
        @param size     size of the memory block */
        Pool(size_t size);

        /** Destructor */
        ~Pool();

        /** Get an object from the pool.
        @retrun a free transaction or NULL if exhausted. */
        Type*   get();

        /** Add the object to the pool.
        @param ptr      object to free */
        static void free(value_type* ptr);
};

The Factory template parameter is for initialising and destroying the instance. It 
must support the following interface:

struct SomeFactory {
        /**
        Initializes some object.
        @param some_type_t    block of memory to initialise */
        static void init(some_type_t* ptr);

        /**
        Destroy the object */
        static void destroy(some_type_t* ptr);
};

The memory is always owned by the pool. For C++ classes/structs the use case will 
be around placement new.

The public interface of the pool manager. The pools are managed by a PoolManager. 
The PoolManager tracks the pools and can create a new  one if all current ones are 
empty.

template 
struct PoolManager {

        typedef Pool PoolType;
        typedef typename PoolType::value_type value_type;

        PoolManager(size_t size);
        ~PoolManager() { }

        /** Add a new pool */
        void add_pool();

        /** Get an element from one of the pools.
        @return instance or NULL if pool is empty. */
        value_type* get();

        static void free(value_type* ptr);
};

The LockStrategy template argument must support the following interface. The aim 
is to provide a flexible locking strategy. e.g., if the pool should be covered by 
the trx_sys_t::mutex we can create a class that acquires/releases that specific 
mutex. This should be possible without changing the Pool implementation.

/** The lock strategy for TrxPool */
struct SomeLockStrategy {
        TrxPoolLock() { }

        /** Create the mutex */
        void create();

        /** Acquire the mutex */
        void enter();

        /** Release the mutex */
        void exit();

        /** Free the mutex */
        void destroy();
};


In the case of trx_t, we allocate the following:

/** Use explicit mutexes for the trx_t pool and its manager. */
typedef Pool trx_pool_t;
typedef PoolManager trx_pools_t;

We create a special purpose factory that acts as a proxy for the current trx_t 
instance initialisation and destruction.

We create two new mutex types, one for the pools and the other for the pool 
manager.


/** The lock strategy for TrxPool */
struct TrxPoolLock;

/** The lock strategy for the TrxPoolManager */
struct TrxPoolManagerLock;


The life cycle of the transaction pool
======================================
On server startup we call trx_pool_init() from src_general_init() and on shutdown 
we call trx_pool_close() from innobase_shutdown_for_mysql() to free the pools.