win-pvdrivers

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