reactos/drivers/storage/ide/uniata/id_queue.cpp

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