win-pvdrivers

annotate 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
rev   line source
james@766 1 #include "queue_internal.h"
james@766 2
james@766 3
james@766 4
james@766 5
james@766 6
james@766 7 /****************************************************************************/
james@766 8 #pragma warning( disable : 4100 )
james@766 9
james@766 10 void queue_query( struct queue_state *qs, enum queue_query_type query_type, void *query_input, void *query_output )
james@766 11 {
james@766 12 assert( qs != NULL );
james@766 13 // TRD : query_type can be any value in its range
james@766 14 // TRD : query_input can be NULL
james@766 15 assert( query_output != NULL );
james@766 16
james@766 17 switch( query_type )
james@766 18 {
james@766 19 case QUEUE_QUERY_ELEMENT_COUNT:
james@766 20 assert( query_input == NULL );
james@766 21
james@766 22 freelist_query( qs->fs, FREELIST_QUERY_ELEMENT_COUNT, NULL, query_output );
james@766 23 break;
james@766 24
james@766 25 case QUEUE_QUERY_VALIDATE:
james@766 26 // TRD : query_input can be NULL
james@766 27
james@766 28 queue_internal_validate( qs, (struct validation_info *) query_input, (enum data_structure_validity *) query_output, ((enum data_structure_validity *) query_output)+1 );
james@766 29 break;
james@766 30 }
james@766 31
james@766 32 return;
james@766 33 }
james@766 34
james@766 35 #pragma warning( default : 4100 )
james@766 36
james@766 37
james@766 38
james@766 39
james@766 40
james@766 41 /****************************************************************************/
james@766 42 void queue_internal_validate( struct queue_state *qs, struct validation_info *vi, enum data_structure_validity *queue_validity, enum data_structure_validity *freelist_validity )
james@766 43 {
james@766 44 struct queue_element
james@766 45 *qe,
james@766 46 *qe_slow,
james@766 47 *qe_fast;
james@766 48
james@766 49 atom_t
james@766 50 element_count = 0,
james@766 51 total_elements;
james@766 52
james@766 53 struct validation_info
james@766 54 freelist_vi;
james@766 55
james@766 56 assert( qs != NULL );
james@766 57 // TRD : vi can be NULL
james@766 58 assert( queue_validity != NULL );
james@766 59 assert( freelist_validity != NULL );
james@766 60
james@766 61 *queue_validity = VALIDITY_VALID;
james@766 62
james@766 63 qe_slow = qe_fast = (struct queue_element *) qs->dequeue[QUEUE_POINTER];
james@766 64
james@766 65 /* TRD : first, check for a loop
james@766 66 we have two pointers
james@766 67 both of which start at the dequeue end of the queue
james@766 68 we enter a loop
james@766 69 and on each iteration
james@766 70 we advance one pointer by one element
james@766 71 and the other by two
james@766 72
james@766 73 we exit the loop when both pointers are NULL
james@766 74 (have reached the end of the queue)
james@766 75
james@766 76 or
james@766 77
james@766 78 if we fast pointer 'sees' the slow pointer
james@766 79 which means we have a loop
james@766 80 */
james@766 81
james@766 82 if( qe_slow != NULL )
james@766 83 do
james@766 84 {
james@766 85 qe_slow = qe_slow->next[QUEUE_POINTER];
james@766 86
james@766 87 if( qe_fast != NULL )
james@766 88 qe_fast = qe_fast->next[QUEUE_POINTER];
james@766 89
james@766 90 if( qe_fast != NULL )
james@766 91 qe_fast = qe_fast->next[QUEUE_POINTER];
james@766 92 }
james@766 93 while( qe_slow != NULL and qe_fast != qe_slow );
james@766 94
james@766 95 if( qe_fast != NULL and qe_slow != NULL and qe_fast == qe_slow )
james@766 96 *queue_validity = VALIDITY_INVALID_LOOP;
james@766 97
james@766 98 /* TRD : now check for expected number of elements
james@766 99 vi can be NULL, in which case we do not check
james@766 100 we know we don't have a loop from our earlier check
james@766 101 */
james@766 102
james@766 103 if( *queue_validity == VALIDITY_VALID and vi != NULL )
james@766 104 {
james@766 105 qe = (struct queue_element *) qs->dequeue[QUEUE_POINTER];
james@766 106
james@766 107 while( qe != NULL )
james@766 108 {
james@766 109 element_count++;
james@766 110 qe = (struct queue_element *) qe->next[QUEUE_POINTER];
james@766 111 }
james@766 112
james@766 113 /* TRD : remember there is a dummy element in the queue */
james@766 114 element_count--;
james@766 115
james@766 116 if( element_count < vi->min_elements )
james@766 117 *queue_validity = VALIDITY_INVALID_MISSING_ELEMENTS;
james@766 118
james@766 119 if( element_count > vi->max_elements )
james@766 120 *queue_validity = VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
james@766 121 }
james@766 122
james@766 123 /* TRD : now we validate the freelist
james@766 124
james@766 125 we may be able to check for the expected number of
james@766 126 elements in the freelist
james@766 127
james@766 128 if the caller has given us an expected min and max
james@766 129 number of elements in the queue, then the total number
james@766 130 of elements in the freelist, minus that min and max,
james@766 131 gives us the expected number of elements in the
james@766 132 freelist
james@766 133 */
james@766 134
james@766 135 if( vi != NULL )
james@766 136 {
james@766 137 freelist_query( qs->fs, FREELIST_QUERY_ELEMENT_COUNT, NULL, (void *) &total_elements );
james@766 138
james@766 139 /* TRD : remember there is a dummy element in the queue */
james@766 140 total_elements--;
james@766 141
james@766 142 freelist_vi.min_elements = total_elements - vi->max_elements;
james@766 143 freelist_vi.max_elements = total_elements - vi->min_elements;
james@766 144
james@766 145 freelist_query( qs->fs, FREELIST_QUERY_VALIDATE, (void *) &freelist_vi, (void *) freelist_validity );
james@766 146 }
james@766 147
james@766 148 if( vi == NULL )
james@766 149 freelist_query( qs->fs, FREELIST_QUERY_VALIDATE, NULL, (void *) freelist_validity );
james@766 150
james@766 151 return;
james@766 152 }
james@766 153