ReactOS 0.4.15-dev-8119-g4fb2fdb
id_queue.cpp
Go to the documentation of this file.
1/*++
2
3Copyright (c) 2008-2012 Alexandr A. Telyatnikov (Alter)
4
5Module Name:
6 id_probe.cpp
7
8Abstract:
9 This module handles comamnd queue reordering and channel load balance
10
11Author:
12 Alexander A. Telyatnikov (Alter)
13
14Environment:
15 kernel mode only
16
17Notes:
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
30Revision History:
31
32Licence:
33 GPLv2
34
35--*/
36
37#include "stdafx.h"
38
39/*
40 Get cost of insertion Req1 before Req2
41 */
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))
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 */
91VOID
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 */
263VOID
264NTAPI
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 */
357NTAPI
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 */
375NTAPI
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()
unsigned char BOOLEAN
#define MAX_QUEUE_STAT
Definition: bm_devs_decl.h:50
#define REORDER_COST_DENIED
Definition: bsmaster.h:982
#define REORDER_COST_INTERSECT
Definition: bsmaster.h:981
#define REQ_FLAG_RW_MASK
Definition: bsmaster.h:934
#define REQ_FLAG_WRITE
Definition: bsmaster.h:936
#define REQ_STATE_NONE
Definition: bsmaster.h:943
#define REQ_FLAG_REORDERABLE_CMD
Definition: bsmaster.h:933
#define MIN_REQ_TTL
Definition: bsmaster.h:866
#define GET_CDEV(Srb)
Definition: bsmaster.h:1850
union _ATA_REQ * PATA_REQ
#define REORDER_COST_RESELECT
Definition: bsmaster.h:983
#define REORDER_COST_TTL
Definition: bsmaster.h:980
_In_ PSCSI_REQUEST_BLOCK Srb
Definition: cdrom.h:989
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define SRB_SIMPLE_TAG_REQUEST
Definition: srb.h:423
#define SRB_ORDERED_QUEUE_TAG_REQUEST
Definition: srb.h:425
#define SRB_FLAGS_QUEUE_ACTION_ENABLE
Definition: srb.h:395
#define SRB_HEAD_OF_QUEUE_TAG_REQUEST
Definition: srb.h:424
const GLubyte * c
Definition: glext.h:8905
VOID NTAPI UniataRemoveRequest(IN PHW_CHANNEL chan, IN PSCSI_REQUEST_BLOCK Srb)
Definition: id_queue.cpp:265
VOID NTAPI UniataQueueRequest(IN PHW_CHANNEL chan, IN PSCSI_REQUEST_BLOCK Srb)
Definition: id_queue.cpp:93
PHW_CHANNEL NTAPI UniataGetNextChannel(IN PHW_CHANNEL chan)
Definition: id_queue.cpp:376
LONGLONG NTAPI UniataGetCost(PHW_LU_EXTENSION LunExt, IN PATA_REQ AtaReq1, IN PATA_REQ AtaReq2)
Definition: id_queue.cpp:44
PSCSI_REQUEST_BLOCK NTAPI UniataGetCurRequest(IN PHW_CHANNEL chan)
Definition: id_queue.cpp:358
#define c
Definition: ke_i.h:80
#define min(a, b)
Definition: monoChain.cc:55
ULONG ChannelSelectWaitCount
Definition: bsmaster.h:1028
ULONG NumberChannels
Definition: atapi.c:68
PHW_CHANNEL chan
Definition: bsmaster.h:1257
PATA_REQ first_req
Definition: bsmaster.h:1185
LONGLONG RwSwitchMCost
Definition: bsmaster.h:1182
LONGLONG RwSwitchCost
Definition: bsmaster.h:1181
PATA_REQ last_req
Definition: bsmaster.h:1186
LONGLONG SeekBackMCost
Definition: bsmaster.h:1183
UCHAR QueueAction
Definition: srb.h:257
PVOID SrbExtension
Definition: srb.h:267
ULONG SrbFlags
Definition: srb.h:260
#define max(a, b)
Definition: svc.c:63
int64_t LONGLONG
Definition: typedefs.h:68
#define NTAPI
Definition: typedefs.h:36
#define IN
Definition: typedefs.h:39
uint32_t ULONG
Definition: typedefs.h:59
#define KdPrint2(_x_)
Definition: atapi.h:154
#define CHAN_NOT_SPECIFIED
Definition: atapi.h:1481
#define PRINT_PREFIX
Definition: atapi.h:150
PSCSI_REQUEST_BLOCK Srb
Definition: bsmaster.h:880
union _ATA_REQ * next_req
Definition: bsmaster.h:877
union _ATA_REQ * prev_req
Definition: bsmaster.h:878
UCHAR Flags
Definition: bsmaster.h:892
UCHAR ReqState
Definition: bsmaster.h:893
UCHAR ttl
Definition: bsmaster.h:890
unsigned char UCHAR
Definition: xmlstorage.h:181