drivers/storage/ide/uniata/id_queue.cpp

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