1 /*++
2 
3 Copyright (c) 2008-2012 Alexandr A. Telyatnikov (Alter)
4 
5 Module Name:
6     id_probe.cpp
7 
8 Abstract:
9     This module handles comamnd queue reordering and channel load balance
10 
11 Author:
12     Alexander A. Telyatnikov (Alter)
13 
14 Environment:
15     kernel mode only
16 
17 Notes:
18 
19     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 
30 Revision History:
31 
32 Licence:
33     GPLv2
34 
35 --*/
36 
37 #include "stdafx.h"
38 
39 /*
40     Get cost of insertion Req1 before Req2
41  */
42 LONGLONG
43 NTAPI
44 UniataGetCost(
45     PHW_LU_EXTENSION LunExt,
46     IN PATA_REQ AtaReq1,
47     IN PATA_REQ AtaReq2
48     )
49 {
50     BOOLEAN write1;
51     BOOLEAN write2;
52     UCHAR flags1;
53     UCHAR flags2;
54     LONGLONG cost;
55     // can't insert Req1 before tooooo old Req2
56     if(!AtaReq2->ttl)
57         return REORDER_COST_TTL;
58     // check if reorderable
59     flags1 = AtaReq1->Flags;
60     flags2 = AtaReq2->Flags;
61     if(!((flags2 & flags1) & REQ_FLAG_REORDERABLE_CMD))
62         return REORDER_COST_DENIED;
63     // if at least one Req is WRITE, target areas
64     // can not intersect
65     write1 = (flags1 & REQ_FLAG_RW_MASK) == REQ_FLAG_WRITE;
66     write2 = (flags2 & REQ_FLAG_RW_MASK) == REQ_FLAG_WRITE;
67     cost = AtaReq1->lba+AtaReq1->bcount - AtaReq2->lba;
68     if( write1 || write2 ) {
69         // check for intersection
70         if((AtaReq1->lba < AtaReq2->lba+AtaReq2->bcount) &&
71            (AtaReq1->lba+AtaReq1->bcount > AtaReq2->lba)) {
72             // Intersection...
73             return REORDER_COST_INTERSECT;
74         }
75     }
76     if(cost < 0) {
77         cost *= (1-LunExt->SeekBackMCost);
78     } else {
79         cost *= (LunExt->SeekBackMCost-1);
80     }
81     if( write1 == write2 ) {
82         return cost;
83     }
84     return (cost * LunExt->RwSwitchMCost) + LunExt->RwSwitchCost;
85 } // end UniataGetCost()
86 
87 /*
88     Insert command to proper place of command queue
89     Perform reorder if necessary
90  */
91 VOID
92 NTAPI
93 UniataQueueRequest(
94     IN PHW_CHANNEL chan,
95     IN PSCSI_REQUEST_BLOCK Srb
96     )
97 {
98     PATA_REQ AtaReq = (PATA_REQ)(Srb->SrbExtension);
99     PATA_REQ AtaReq1;
100     PATA_REQ AtaReq2;
101 
102     LONGLONG best_cost;
103     LONGLONG new_cost;
104     LONGLONG new_cost1;
105     LONGLONG new_cost2;
106     PATA_REQ BestAtaReq1;
107 
108     BOOLEAN use_reorder = chan->UseReorder/*EnableReorder*/;
109 #ifdef QUEUE_STATISTICS
110     BOOLEAN reordered = FALSE;
111 #endif //QUEUE_STATISTICS
112 
113     PHW_LU_EXTENSION LunExt = chan->lun[GET_CDEV(Srb)];
114     AtaReq->Srb = Srb;
115 
116 /*
117 #ifdef _DEBUG
118     if(!LunExt) {
119         PrintNtConsole("q: chan = %#x, dev %#x\n", chan, GET_CDEV(Srb));
120         int i;
121         for(i=0; i<1000; i++) {
122             AtapiStallExecution(5*1000);
123         }
124         return;
125     }
126 #endif //_DEBUG
127 */
128     // check if queue is empty
129     if(LunExt->queue_depth) {
130         AtaReq->ttl = (UCHAR)(max(LunExt->queue_depth, MIN_REQ_TTL));
131 
132         // init loop
133         BestAtaReq1 =
134         AtaReq2 = LunExt->last_req;
135 
136         if(use_reorder &&
137            (Srb->SrbFlags & SRB_FLAGS_QUEUE_ACTION_ENABLE)) {
138             switch(Srb->QueueAction) {
139             case SRB_ORDERED_QUEUE_TAG_REQUEST:
140                 use_reorder = FALSE;
141 #ifdef QUEUE_STATISTICS
142                 chan->TryReorderTailCount++;
143 #endif //QUEUE_STATISTICS
144                 break;
145             case SRB_HEAD_OF_QUEUE_TAG_REQUEST:
146                 BestAtaReq1 = LunExt->first_req;
147                 best_cost = -REORDER_COST_RESELECT;
148 #ifdef QUEUE_STATISTICS
149                 chan->TryReorderHeadCount++;
150 #endif //QUEUE_STATISTICS
151                 break;
152             case SRB_SIMPLE_TAG_REQUEST:
153             default:
154                 best_cost = UniataGetCost(LunExt, BestAtaReq1, AtaReq);
155                 use_reorder |= TRUE;
156             }
157         } else
158         if(use_reorder) {
159             best_cost = UniataGetCost(LunExt, BestAtaReq1, AtaReq);
160         }
161 
162         if(use_reorder) {
163 
164 #ifdef QUEUE_STATISTICS
165             chan->TryReorderCount++;
166 #endif //QUEUE_STATISTICS
167 
168             // walk through command queue and find the best
169             // place for insertion of the command
170             while ((AtaReq1 = AtaReq2->prev_req)) {
171                 new_cost1 = UniataGetCost(LunExt, AtaReq1, AtaReq);
172                 new_cost2 = UniataGetCost(LunExt, AtaReq, AtaReq2);
173 
174 #ifdef QUEUE_STATISTICS
175                 if(new_cost1 == REORDER_COST_INTERSECT ||
176                    new_cost2 == REORDER_COST_INTERSECT)
177                     chan->IntersectCount++;
178 #endif //QUEUE_STATISTICS
179 
180                 if(new_cost2 > REORDER_COST_RESELECT)
181                     break;
182 
183                 // for now I see nothing bad in RESELECT here
184                 //ASSERT(new_cost1 <= REORDER_COST_RESELECT);
185 
186                 new_cost = UniataGetCost(LunExt, AtaReq1, AtaReq2);
187                 new_cost = new_cost1 + new_cost2 - new_cost;
188 
189                 // check for Stop Reordering
190                 if(new_cost > REORDER_COST_RESELECT*3)
191                     break;
192 
193                 if(new_cost < best_cost) {
194                     best_cost = new_cost;
195                     BestAtaReq1 = AtaReq1;
196 #ifdef QUEUE_STATISTICS
197                     reordered = TRUE;
198 #endif //QUEUE_STATISTICS
199                 }
200                 AtaReq2 = AtaReq1;
201             }
202 #ifdef QUEUE_STATISTICS
203             if(reordered)
204                 chan->ReorderCount++;
205 #endif //QUEUE_STATISTICS
206         }
207         // Insert Req between Req2 & Req1
208         AtaReq2 = BestAtaReq1->next_req;
209         if(AtaReq2) {
210             AtaReq2->prev_req = AtaReq;
211             AtaReq->next_req = AtaReq2;
212         } else {
213             AtaReq->next_req = NULL;
214             LunExt->last_req = AtaReq;
215         }
216 //        LunExt->last_req->next_req = AtaReq;
217         BestAtaReq1->next_req = AtaReq;
218 //        AtaReq->prev_req = LunExt->last_req;
219         AtaReq->prev_req = BestAtaReq1;
220 
221         AtaReq1 = AtaReq;
222         while((AtaReq1 = AtaReq1->next_req)) {
223             //ASSERT(AtaReq1->ttl);
224             AtaReq1->ttl--;
225         }
226 
227     } else {
228         // empty queue
229         AtaReq->ttl = 0;
230         AtaReq->prev_req =
231         AtaReq->next_req = NULL;
232         LunExt->first_req =
233         LunExt->last_req = AtaReq;
234 #ifdef __REACTOS__
235         // Do nothing here, workaround for CORE-12441 and CORE-17371
236 #else
237         chan->cur_cdev = GET_CDEV(Srb);
238 #endif
239     }
240     LunExt->queue_depth++;
241     chan->queue_depth++;
242     chan->DeviceExtension->queue_depth++;
243     // check if this is the 1st request in queue
244     if(chan->queue_depth == 1) {
245         chan->cur_req = LunExt->first_req;
246     }
247 
248 #ifdef QUEUE_STATISTICS
249     //ASSERT(LunExt->queue_depth);
250     chan->QueueStat[min(MAX_QUEUE_STAT, LunExt->queue_depth)-1]++;
251 #endif //QUEUE_STATISTICS
252 /*
253     ASSERT(chan->queue_depth ==
254             (chan->lun[0]->queue_depth + chan->lun[1]->queue_depth));
255     ASSERT(!chan->queue_depth || chan->cur_req);
256 */
257     return;
258 } // end UniataQueueRequest()
259 
260 /*
261     Remove request from queue and get next request
262  */
263 VOID
264 NTAPI
265 UniataRemoveRequest(
266     IN PHW_CHANNEL chan,
267     IN PSCSI_REQUEST_BLOCK Srb
268     )
269 {
270     if(!Srb)
271         return;
272     if(!chan)
273         return;
274 
275     PATA_REQ AtaReq = (PATA_REQ)(Srb->SrbExtension);
276     //PHW_DEVICE_EXTENSION deviceExtension = chan->DeviceExtension;
277 
278     ULONG cdev = GET_CDEV(Srb);
279     PHW_LU_EXTENSION LunExt = chan->lun[cdev];
280 
281     if(!LunExt)
282         return;
283 
284 /*
285     ASSERT(chan->queue_depth ==
286             (chan->lun[0]->queue_depth + chan->lun[1]->queue_depth));
287     ASSERT(!chan->queue_depth || chan->cur_req);
288 */
289     // check if queue for the device is empty
290     if(!LunExt->queue_depth)
291         return;
292 
293     // check if request is under processing (busy)
294     if(!AtaReq->ReqState)
295         return;
296 
297     // remove reqest from queue
298     if(AtaReq->prev_req) {
299         AtaReq->prev_req->next_req =
300             AtaReq->next_req;
301     } else {
302         LunExt->first_req = AtaReq->next_req;
303     }
304     if(AtaReq->next_req) {
305         AtaReq->next_req->prev_req =
306             AtaReq->prev_req;
307     } else {
308         LunExt->last_req = AtaReq->prev_req;
309     }
310     LunExt->queue_depth--;
311     chan->queue_depth--;
312     chan->DeviceExtension->queue_depth--;
313     // set LastWrite flag for Lun
314     LunExt->last_write = ((AtaReq->Flags & REQ_FLAG_RW_MASK) == REQ_FLAG_WRITE);
315 
316     // get request from longest queue to balance load
317     if(chan->NumberLuns > 1) {
318         if(chan->lun[0]->queue_depth * (chan->lun[0]->LunSelectWaitCount+1) >
319            chan->lun[1]->queue_depth * (chan->lun[1]->LunSelectWaitCount+1)) {
320             cdev = 0;
321         } else {
322             cdev = 1;
323         }
324     }
325 /*    // prevent too long wait for actively used device
326     if(chan->lun[cdev ^ 1]->queue_depth &&
327        chan->lun[cdev ^ 1]->LunSelectWaitCount >= chan->lun[cdev]->queue_depth) {
328         cdev = cdev ^ 1;
329     }*/
330     // get next request for processing
331     chan->cur_req = chan->lun[cdev]->first_req;
332     chan->cur_cdev = cdev;
333     if(chan->NumberLuns > 1) {
334         if(!chan->lun[cdev ^ 1]->queue_depth) {
335             chan->lun[cdev ^ 1]->LunSelectWaitCount=0;
336         } else {
337             chan->lun[cdev ^ 1]->LunSelectWaitCount++;
338         }
339     }
340     chan->lun[cdev]->LunSelectWaitCount=0;
341 
342 //    chan->first_req->prev_req = NULL;
343     AtaReq->ReqState = REQ_STATE_NONE;
344 /*
345     ASSERT(chan->queue_depth ==
346             (chan->lun[0]->queue_depth + chan->lun[1]->queue_depth));
347     ASSERT(!chan->queue_depth || chan->cur_req);
348 */
349     return;
350 } // end UniataRemoveRequest()
351 
352 /*
353     Get currently processed request
354     (from head of the queue)
355  */
356 PSCSI_REQUEST_BLOCK
357 NTAPI
358 UniataGetCurRequest(
359     IN PHW_CHANNEL chan
360     )
361 {
362 //    if(!chan->lun[]->queue_depth) {
363     if(!chan || !chan->cur_req) {
364         return NULL;
365     }
366 
367     return chan->cur_req->Srb;
368 } // end UniataGetCurRequest()
369 
370 /*
371     Get next channel to be serviced
372     (used in simplex mode only)
373  */
374 PHW_CHANNEL
375 NTAPI
376 UniataGetNextChannel(
377     IN PHW_CHANNEL chan
378     )
379 {
380     ULONG c=0, _c;
381     PHW_DEVICE_EXTENSION deviceExtension;
382     ULONG best_c;
383     ULONG cost_c;
384 
385     deviceExtension = chan->DeviceExtension;
386 
387     if(!deviceExtension->simplexOnly) {
388         return chan;
389     }
390     KdPrint2((PRINT_PREFIX "UniataGetNextChannel:\n"));
391     best_c = -1;
392     cost_c = 0;
393     for(_c=0; _c<deviceExtension->NumberChannels; _c++) {
394         c = (_c+deviceExtension->FirstChannelToCheck) % deviceExtension->NumberChannels;
395         chan = &deviceExtension->chan[c];
396         if(chan->queue_depth &&
397            chan->queue_depth * (chan->ChannelSelectWaitCount+1) >
398            cost_c) {
399             best_c = c;
400             cost_c = chan->queue_depth * (chan->ChannelSelectWaitCount+1);
401         }
402     }
403     if(best_c == CHAN_NOT_SPECIFIED) {
404         KdPrint2((PRINT_PREFIX "  empty queues\n"));
405         return NULL;
406     }
407     deviceExtension->FirstChannelToCheck = c;
408     for(_c=0; _c<deviceExtension->NumberChannels; _c++) {
409         chan = &deviceExtension->chan[_c];
410         if(_c == best_c) {
411             chan->ChannelSelectWaitCount = 0;
412             continue;
413         }
414         chan->ChannelSelectWaitCount++;
415         if(!chan->queue_depth) {
416             chan->ChannelSelectWaitCount = 0;
417         } else {
418             chan->ChannelSelectWaitCount++;
419         }
420     }
421     KdPrint2((PRINT_PREFIX "  select chan %d\n", best_c));
422     return &deviceExtension->chan[best_c];
423 } // end UniataGetNextChannel()
424