win-pvdrivers

diff liblfds.6/src/queue/queue_query.c @ 766:6300617040e0

Big changes - not ready for production use.
Removed all the custom DMA handling code as it was completely incompatible with the Windows verifier.
Added liblfds (using the lock free stack) from liblfds.org so that grant's can be obtained at DIRQL.
Fixed xennet and xenvbd to support the changes.
xenusb and xenscsi almost certainly will not yet work after the changes.
author James Harper <james.harper@bendigoit.com.au>
date Sun Jan 31 21:28:42 2010 +1100 (2010-01-31)
parents
children
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/liblfds.6/src/queue/queue_query.c	Sun Jan 31 21:28:42 2010 +1100
     1.3 @@ -0,0 +1,153 @@
     1.4 +#include "queue_internal.h"
     1.5 +
     1.6 +
     1.7 +
     1.8 +
     1.9 +
    1.10 +/****************************************************************************/
    1.11 +#pragma warning( disable : 4100 )
    1.12 +
    1.13 +void queue_query( struct queue_state *qs, enum queue_query_type query_type, void *query_input, void *query_output )
    1.14 +{
    1.15 +  assert( qs != NULL );
    1.16 +  // TRD : query_type can be any value in its range
    1.17 +  // TRD : query_input can be NULL
    1.18 +  assert( query_output != NULL );
    1.19 +
    1.20 +  switch( query_type )
    1.21 +  {
    1.22 +    case QUEUE_QUERY_ELEMENT_COUNT:
    1.23 +      assert( query_input == NULL );
    1.24 +
    1.25 +      freelist_query( qs->fs, FREELIST_QUERY_ELEMENT_COUNT, NULL, query_output );
    1.26 +    break;
    1.27 +
    1.28 +    case QUEUE_QUERY_VALIDATE:
    1.29 +      // TRD : query_input can be NULL
    1.30 +
    1.31 +      queue_internal_validate( qs, (struct validation_info *) query_input, (enum data_structure_validity *) query_output, ((enum data_structure_validity *) query_output)+1 );
    1.32 +    break;
    1.33 +  }
    1.34 +
    1.35 +  return;
    1.36 +}
    1.37 +
    1.38 +#pragma warning( default : 4100 )
    1.39 +
    1.40 +
    1.41 +
    1.42 +
    1.43 +
    1.44 +/****************************************************************************/
    1.45 +void queue_internal_validate( struct queue_state *qs, struct validation_info *vi, enum data_structure_validity *queue_validity, enum data_structure_validity *freelist_validity )
    1.46 +{
    1.47 +  struct queue_element
    1.48 +    *qe,
    1.49 +    *qe_slow,
    1.50 +    *qe_fast;
    1.51 +
    1.52 +  atom_t
    1.53 +    element_count = 0,
    1.54 +    total_elements;
    1.55 +
    1.56 +  struct validation_info
    1.57 +    freelist_vi;
    1.58 +
    1.59 +  assert( qs != NULL );
    1.60 +  // TRD : vi can be NULL
    1.61 +  assert( queue_validity != NULL );
    1.62 +  assert( freelist_validity != NULL );
    1.63 +
    1.64 +  *queue_validity = VALIDITY_VALID;
    1.65 +
    1.66 +  qe_slow = qe_fast = (struct queue_element *) qs->dequeue[QUEUE_POINTER];
    1.67 +
    1.68 +  /* TRD : first, check for a loop
    1.69 +           we have two pointers
    1.70 +           both of which start at the dequeue end of the queue
    1.71 +           we enter a loop
    1.72 +           and on each iteration
    1.73 +           we advance one pointer by one element
    1.74 +           and the other by two
    1.75 +
    1.76 +           we exit the loop when both pointers are NULL
    1.77 +           (have reached the end of the queue)
    1.78 +
    1.79 +           or
    1.80 +
    1.81 +           if we fast pointer 'sees' the slow pointer
    1.82 +           which means we have a loop
    1.83 +  */
    1.84 +
    1.85 +  if( qe_slow != NULL )
    1.86 +    do
    1.87 +    {
    1.88 +      qe_slow = qe_slow->next[QUEUE_POINTER];
    1.89 +
    1.90 +      if( qe_fast != NULL )
    1.91 +        qe_fast = qe_fast->next[QUEUE_POINTER];
    1.92 +
    1.93 +      if( qe_fast != NULL )
    1.94 +        qe_fast = qe_fast->next[QUEUE_POINTER];
    1.95 +    }
    1.96 +    while( qe_slow != NULL and qe_fast != qe_slow );
    1.97 +
    1.98 +  if( qe_fast != NULL and qe_slow != NULL and qe_fast == qe_slow )
    1.99 +    *queue_validity = VALIDITY_INVALID_LOOP;
   1.100 +
   1.101 +  /* TRD : now check for expected number of elements
   1.102 +           vi can be NULL, in which case we do not check
   1.103 +           we know we don't have a loop from our earlier check
   1.104 +  */
   1.105 +
   1.106 +  if( *queue_validity == VALIDITY_VALID and vi != NULL )
   1.107 +  {
   1.108 +    qe = (struct queue_element *) qs->dequeue[QUEUE_POINTER];
   1.109 +
   1.110 +    while( qe != NULL )
   1.111 +    {
   1.112 +      element_count++;
   1.113 +      qe = (struct queue_element *) qe->next[QUEUE_POINTER];
   1.114 +    }
   1.115 +
   1.116 +    /* TRD : remember there is a dummy element in the queue */
   1.117 +    element_count--;
   1.118 +
   1.119 +    if( element_count < vi->min_elements )
   1.120 +      *queue_validity = VALIDITY_INVALID_MISSING_ELEMENTS;
   1.121 +
   1.122 +    if( element_count > vi->max_elements )
   1.123 +      *queue_validity = VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
   1.124 +  }
   1.125 +
   1.126 +  /* TRD : now we validate the freelist
   1.127 +
   1.128 +           we may be able to check for the expected number of
   1.129 +           elements in the freelist
   1.130 +
   1.131 +           if the caller has given us an expected min and max
   1.132 +           number of elements in the queue, then the total number
   1.133 +           of elements in the freelist, minus that min and max,
   1.134 +           gives us the expected number of elements in the
   1.135 +           freelist
   1.136 +  */
   1.137 +
   1.138 +  if( vi != NULL )
   1.139 +  {
   1.140 +    freelist_query( qs->fs, FREELIST_QUERY_ELEMENT_COUNT, NULL, (void *) &total_elements );
   1.141 +
   1.142 +    /* TRD : remember there is a dummy element in the queue */
   1.143 +    total_elements--;
   1.144 +
   1.145 +    freelist_vi.min_elements = total_elements - vi->max_elements;
   1.146 +    freelist_vi.max_elements = total_elements - vi->min_elements;
   1.147 +
   1.148 +    freelist_query( qs->fs, FREELIST_QUERY_VALIDATE, (void *) &freelist_vi, (void *) freelist_validity );
   1.149 +  }
   1.150 +
   1.151 +  if( vi == NULL )
   1.152 +    freelist_query( qs->fs, FREELIST_QUERY_VALIDATE, NULL, (void *) freelist_validity );
   1.153 +
   1.154 +  return;
   1.155 +}
   1.156 +