ReactOS  0.4.15-dev-3302-ga37d9a4
id_queue.cpp
Go to the documentation of this file.
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  */
43 NTAPI
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...
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
94  IN PHW_CHANNEL chan,
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 &&
138  switch(Srb->QueueAction) {
140  use_reorder = FALSE;
141 #ifdef QUEUE_STATISTICS
142  chan->TryReorderTailCount++;
143 #endif //QUEUE_STATISTICS
144  break;
146  BestAtaReq1 = LunExt->first_req;
147  best_cost = -REORDER_COST_RESELECT;
148 #ifdef QUEUE_STATISTICS
149  chan->TryReorderHeadCount++;
150 #endif //QUEUE_STATISTICS
151  break;
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
266  IN PHW_CHANNEL chan,
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  */
357 NTAPI
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  */
375 NTAPI
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()
union _ATA_REQ * next_req
Definition: bsmaster.h:877
#define REQ_STATE_NONE
Definition: bsmaster.h:943
#define IN
Definition: typedefs.h:39
#define max(a, b)
Definition: svc.c:63
#define KdPrint2(_x_)
Definition: atapi.h:154
ULONG SrbFlags
Definition: srb.h:252
PVOID SrbExtension
Definition: srb.h:259
#define CHAN_NOT_SPECIFIED
Definition: atapi.h:1483
UCHAR ReqState
Definition: bsmaster.h:893
_In_ PSCSI_REQUEST_BLOCK Srb
Definition: cdrom.h:989
#define TRUE
Definition: types.h:120
#define REQ_FLAG_RW_MASK
Definition: bsmaster.h:934
PHW_CHANNEL chan
Definition: bsmaster.h:1257
#define MAX_QUEUE_STAT
Definition: bm_devs_decl.h:50
UCHAR QueueAction
Definition: srb.h:249
NTSTATUS(* NTAPI)(IN PFILE_FULL_EA_INFORMATION EaBuffer, IN ULONG EaLength, OUT PULONG ErrorOffset)
Definition: IoEaTest.cpp:117
#define FALSE
Definition: types.h:117
#define REQ_FLAG_WRITE
Definition: bsmaster.h:936
LONGLONG NTAPI UniataGetCost(PHW_LU_EXTENSION LunExt, IN PATA_REQ AtaReq1, IN PATA_REQ AtaReq2)
Definition: id_queue.cpp:44
VOID NTAPI UniataRemoveRequest(IN PHW_CHANNEL chan, IN PSCSI_REQUEST_BLOCK Srb)
Definition: id_queue.cpp:265
unsigned char BOOLEAN
int64_t LONGLONG
Definition: typedefs.h:68
ULONG ChannelSelectWaitCount
Definition: bsmaster.h:1028
#define GET_CDEV(Srb)
Definition: bsmaster.h:1850
LONGLONG RwSwitchCost
Definition: bsmaster.h:1181
PSCSI_REQUEST_BLOCK NTAPI UniataGetCurRequest(IN PHW_CHANNEL chan)
Definition: id_queue.cpp:358
const GLubyte * c
Definition: glext.h:8905
#define MIN_REQ_TTL
Definition: bsmaster.h:866
union _ATA_REQ * prev_req
Definition: bsmaster.h:878
#define REORDER_COST_DENIED
Definition: bsmaster.h:982
unsigned char UCHAR
Definition: xmlstorage.h:181
#define REORDER_COST_RESELECT
Definition: bsmaster.h:983
LONGLONG SeekBackMCost
Definition: bsmaster.h:1183
#define REORDER_COST_TTL
Definition: bsmaster.h:980
#define SRB_ORDERED_QUEUE_TAG_REQUEST
Definition: srb.h:417
PATA_REQ first_req
Definition: bsmaster.h:1185
UCHAR Flags
Definition: bsmaster.h:892
LONGLONG RwSwitchMCost
Definition: bsmaster.h:1182
#define SRB_SIMPLE_TAG_REQUEST
Definition: srb.h:415
#define min(a, b)
Definition: monoChain.cc:55
#define NULL
Definition: types.h:112
PSCSI_REQUEST_BLOCK Srb
Definition: bsmaster.h:880
#define PRINT_PREFIX
Definition: atapi.h:150
#define SRB_HEAD_OF_QUEUE_TAG_REQUEST
Definition: srb.h:416
#define REORDER_COST_INTERSECT
Definition: bsmaster.h:981
#define REQ_FLAG_REORDERABLE_CMD
Definition: bsmaster.h:933
#define c
Definition: ke_i.h:80
unsigned int ULONG
Definition: retypes.h:1
UCHAR ttl
Definition: bsmaster.h:890
PHW_CHANNEL NTAPI UniataGetNextChannel(IN PHW_CHANNEL chan)
Definition: id_queue.cpp:376
PATA_REQ last_req
Definition: bsmaster.h:1186
VOID NTAPI UniataQueueRequest(IN PHW_CHANNEL chan, IN PSCSI_REQUEST_BLOCK Srb)
Definition: id_queue.cpp:93
union _ATA_REQ * PATA_REQ
ULONG NumberChannels
Definition: atapi.c:68
#define SRB_FLAGS_QUEUE_ACTION_ENABLE
Definition: srb.h:387