storage and management of overlapped structure in multithreaded IOCP server

Question

Is it good idea to use LINKED LIST to store overlapped structure?

my overlapped structure looks like this

typedef struct _PER_IO_CONTEXT 
{

  WSAOVERLAPPED               Overlapped;
  WSABUF                      wsabuf;
  ....
  some other per operation data
  ....
  struct _PER_IO_CONTEXT      *pOverlappedForward;
  struct _PER_IO_CONTEXT      *pOverlappedBack;

 } PER_IO_CONTEXT, *PPER_IO_CONTEXT;

When iocp server starts i allocate (for example) 5000 of them in Linked List. The start of this list is stored in global variable PPER_IO_CONTEXT OvlList. I must add that i use this linked list only in a case when i have to send data to all connected clients. When Wsasend is posted or GQCS gets notification, linked list is updated( i use EnterCriticalSection for synchronization ). Thanks in advance for yours tips, opinions and suggestions for better storage(caching) overlapped structure.

Answer 1

I assume the proposed use case is that you wish to cache the "per operation" overlapped structure to avoid repeated allocation and release of dynamic memory which could lead to both contention on the allocator and heap fragmentation.

Using a single 'pool' reduces the contention from 'contention between all threads using the allocator that is used for allocating and destroying the overlapped structures' to 'to contention between all threads issuing or handling I/O operations' which is usually a good thing to do. You're right that you need to synchronise around access, a critical section or perhaps a SRW lock in exclusive mode is probably best (the later is fractionally faster for uncontended access).

The reduction in heap fragmentation is also worth achieving in a long running system.

Using a 'standard' non invasive list, such as a std::deque looks like the obvious choice at first but the problem with non invasive collections is that they tend to allocate and deallocate memory for each operation (so you're back to your original contention). Far better, IMHO, to put a pointer in each overlapped structure and simply chain them together. This requires no additional memory to be allocated or released on pool access and means that your contention is back down to just the threads that use the pool.

Personally I find that I only need a singly linked list of per-operation structures for a pool (free list) which is actually just a stack, and a doubly linked list if I want to maintain a list of 'in use' 'per-operation' data which is sometimes useful (though not something that I now do).

The next step may then be to have several pools, but this will depend on the design of your system and how your I/O works.

If you can have multiple pending send and receive operations for a given connection it may be useful to have a small pool at the connection level. This can dramatically reduce contention for your single shared pool as each connection would first attempt to use the per-connection pool and if that is empty (or full) fall back to using the global pool. This tends to result in far less contention for the lock on the global pool.