ReactOS  0.4.15-dev-1201-gb2cf5a4
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 &&
137  (Srb->SrbFlags & SRB_FLAGS_QUEUE_ACTION_ENABLE)) {
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  chan->cur_cdev = GET_CDEV(Srb);
235  }
236  LunExt->queue_depth++;
237  chan->queue_depth++;
238  chan->DeviceExtension->queue_depth++;
239  // check if this is the 1st request in queue
240  if(chan->queue_depth == 1) {
241  chan->cur_req = LunExt->first_req;
242  }
243 
244 #ifdef QUEUE_STATISTICS
245  //ASSERT(LunExt->queue_depth);
246  chan->QueueStat[min(MAX_QUEUE_STAT, LunExt->queue_depth)-1]++;
247 #endif //QUEUE_STATISTICS
248 /*
249  ASSERT(chan->queue_depth ==
250  (chan->lun[0]->queue_depth + chan->lun[1]->queue_depth));
251  ASSERT(!chan->queue_depth || chan->cur_req);
252 */
253  return;
254 } // end UniataQueueRequest()
255 
256 /*
257  Remove request from queue and get next request
258  */
259 VOID
260 NTAPI
262  IN PHW_CHANNEL chan,
264  )
265 {
266  if(!Srb)
267  return;
268  if(!chan)
269  return;
270 
271  PATA_REQ AtaReq = (PATA_REQ)(Srb->SrbExtension);
272  //PHW_DEVICE_EXTENSION deviceExtension = chan->DeviceExtension;
273 
274  ULONG cdev = GET_CDEV(Srb);
275  PHW_LU_EXTENSION LunExt = chan->lun[cdev];
276 
277  if(!LunExt)
278  return;
279 
280 /*
281  ASSERT(chan->queue_depth ==
282  (chan->lun[0]->queue_depth + chan->lun[1]->queue_depth));
283  ASSERT(!chan->queue_depth || chan->cur_req);
284 */
285  // check if queue for the device is empty
286  if(!LunExt->queue_depth)
287  return;
288 
289  // check if request is under processing (busy)
290  if(!AtaReq->ReqState)
291  return;
292 
293  // remove reqest from queue
294  if(AtaReq->prev_req) {
295  AtaReq->prev_req->next_req =
296  AtaReq->next_req;
297  } else {
298  LunExt->first_req = AtaReq->next_req;
299  }
300  if(AtaReq->next_req) {
301  AtaReq->next_req->prev_req =
302  AtaReq->prev_req;
303  } else {
304  LunExt->last_req = AtaReq->prev_req;
305  }
306  LunExt->queue_depth--;
307  chan->queue_depth--;
308  chan->DeviceExtension->queue_depth--;
309  // set LastWrite flag for Lun
310  LunExt->last_write = ((AtaReq->Flags & REQ_FLAG_RW_MASK) == REQ_FLAG_WRITE);
311 
312  // get request from longest queue to balance load
313  if(chan->NumberLuns > 1) {
314  if(chan->lun[0]->queue_depth * (chan->lun[0]->LunSelectWaitCount+1) >
315  chan->lun[1]->queue_depth * (chan->lun[1]->LunSelectWaitCount+1)) {
316  cdev = 0;
317  } else {
318  cdev = 1;
319  }
320  }
321 /* // prevent too long wait for actively used device
322  if(chan->lun[cdev ^ 1]->queue_depth &&
323  chan->lun[cdev ^ 1]->LunSelectWaitCount >= chan->lun[cdev]->queue_depth) {
324  cdev = cdev ^ 1;
325  }*/
326  // get next request for processing
327  chan->cur_req = chan->lun[cdev]->first_req;
328  chan->cur_cdev = cdev;
329  if(chan->NumberLuns > 1) {
330  if(!chan->lun[cdev ^ 1]->queue_depth) {
331  chan->lun[cdev ^ 1]->LunSelectWaitCount=0;
332  } else {
333  chan->lun[cdev ^ 1]->LunSelectWaitCount++;
334  }
335  }
336  chan->lun[cdev]->LunSelectWaitCount=0;
337 
338 // chan->first_req->prev_req = NULL;
339  AtaReq->ReqState = REQ_STATE_NONE;
340 /*
341  ASSERT(chan->queue_depth ==
342  (chan->lun[0]->queue_depth + chan->lun[1]->queue_depth));
343  ASSERT(!chan->queue_depth || chan->cur_req);
344 */
345  return;
346 } // end UniataRemoveRequest()
347 
348 /*
349  Get currently processed request
350  (from head of the queue)
351  */
353 NTAPI
355  IN PHW_CHANNEL chan
356  )
357 {
358 // if(!chan->lun[]->queue_depth) {
359  if(!chan || !chan->cur_req) {
360  return NULL;
361  }
362 
363  return chan->cur_req->Srb;
364 } // end UniataGetCurRequest()
365 
366 /*
367  Get next channel to be serviced
368  (used in simplex mode only)
369  */
371 NTAPI
373  IN PHW_CHANNEL chan
374  )
375 {
376  ULONG c=0, _c;
377  PHW_DEVICE_EXTENSION deviceExtension;
378  ULONG best_c;
379  ULONG cost_c;
380 
381  deviceExtension = chan->DeviceExtension;
382 
383  if(!deviceExtension->simplexOnly) {
384  return chan;
385  }
386  KdPrint2((PRINT_PREFIX "UniataGetNextChannel:\n"));
387  best_c = -1;
388  cost_c = 0;
389  for(_c=0; _c<deviceExtension->NumberChannels; _c++) {
390  c = (_c+deviceExtension->FirstChannelToCheck) % deviceExtension->NumberChannels;
391  chan = &deviceExtension->chan[c];
392  if(chan->queue_depth &&
393  chan->queue_depth * (chan->ChannelSelectWaitCount+1) >
394  cost_c) {
395  best_c = c;
396  cost_c = chan->queue_depth * (chan->ChannelSelectWaitCount+1);
397  }
398  }
399  if(best_c == CHAN_NOT_SPECIFIED) {
400  KdPrint2((PRINT_PREFIX " empty queues\n"));
401  return NULL;
402  }
403  deviceExtension->FirstChannelToCheck = c;
404  for(_c=0; _c<deviceExtension->NumberChannels; _c++) {
405  chan = &deviceExtension->chan[_c];
406  if(_c == best_c) {
407  chan->ChannelSelectWaitCount = 0;
408  continue;
409  }
410  chan->ChannelSelectWaitCount++;
411  if(!chan->queue_depth) {
412  chan->ChannelSelectWaitCount = 0;
413  } else {
414  chan->ChannelSelectWaitCount++;
415  }
416  }
417  KdPrint2((PRINT_PREFIX " select chan %d\n", best_c));
418  return &deviceExtension->chan[best_c];
419 } // 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
#define CHAN_NOT_SPECIFIED
Definition: atapi.h:1483
UCHAR ReqState
Definition: bsmaster.h:893
#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
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:261
unsigned char BOOLEAN
smooth NULL
Definition: ftsmooth.c:416
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:354
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
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:372
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
IN PSCSI_REQUEST_BLOCK Srb
Definition: class2.h:49
union _ATA_REQ * PATA_REQ
ULONG NumberChannels
Definition: atapi.c:68
#define SRB_FLAGS_QUEUE_ACTION_ENABLE
Definition: srb.h:387