disksim_ioqueue.c

disksim是一个非常优秀的磁盘仿真工具

   }
   if (queue->printsizestats) {
      stat_update(&queue->reqsizestats, (double) curr->bcount);
      if (curr->flags & READ) {
         stat_update(&queue->readsizestats, (double) curr->bcount);
      } else {
         stat_update(&queue->writesizestats, (double) curr->bcount);
      }
   }
   if (curr->blkno == queue->seqblkno) {
      if ((curr->flags & READ) && (queue->seqflags & READ)) {
	 queue->seqreads++;
      } else if (!(curr->flags & READ) && !(queue->seqflags & READ)) {
	 queue->seqwrites++;
      }
   }
   queue->seqblkno = curr->blkno + curr->bcount;
   queue->seqflags = curr->flags;
}


static void ioqueue_update_subqueue_statistics (subqueue *queue)
{
   double tdiff = simtime - queue->lastalt;

   queue->runlistlen += tdiff * queue->listlen;
   queue->runreadlen += tdiff * queue->readlen;
   if (queue->readlen > queue->maxreadlen) {
      queue->maxreadlen = queue->readlen;
   }
   if ((queue->listlen - queue->readlen) > queue->maxwritelen) {
      queue->maxwritelen = queue->listlen - queue->readlen;
   }
   queue->runoutstanding += tdiff * queue->numoutstanding;
   if (queue->numoutstanding > queue->maxoutstanding) {
      queue->maxoutstanding = queue->numoutstanding;
   }
   if (queue->listlen > queue->maxlistlen) {
      queue->maxlistlen = queue->listlen;
   }
   if ((queue->listlen - queue->numoutstanding) > queue->maxqlen) {
      queue->maxqlen = queue->listlen - queue->numoutstanding;
   }
   queue->lastalt = simtime;
}
static void remove_tsps(iobuf *tmp);

static void ioqueue_remove_from_subqueue (subqueue *queue, iobuf *tmp)
{
  if(queue->sched_alg == TSPS){
    remove_tsps(tmp);
  }

   if ((queue->list == tmp) && (tmp == tmp->next)) {
      queue->list = NULL;
   } else {
      tmp->next->prev = tmp->prev;
      tmp->prev->next = tmp->next;
      if (queue->list == tmp) {
         queue->list = tmp->prev;
      }
   }
   tmp->next = NULL;
   tmp->prev = NULL;
}

static void ioqueue_remove_from_batch_fcfs_subqueue (subqueue *queue, iobuf *tmp, ioreq_event *done)
{
  if(queue->sched_alg == TSPS){
    remove_tsps(tmp);
  }

   if ((queue->list == tmp) && (tmp == tmp->next)) {
      queue->list = NULL;
   } else {
      tmp->next->prev = tmp->prev;
      tmp->prev->next = tmp->next;
      if (queue->list == tmp) {
         queue->list = tmp->prev;
      }
   }
   tmp->next = NULL;
   tmp->prev = NULL;
}

static void ioqueue_insert_batch_fcfs_to_queue (subqueue *queue, iobuf *new_iobuf)
{
  iobuf *tmp;
  iobuf *first_in_batch = NULL;
  ioreq_event *event_ptr;
  int i;

  //  printf("ioqueue_insert_batch_fcfs_to_queue:: inserting %d\n", new_iobuf->blkno);

  queue->iobufcnt--;
  //  printf("ioqueue_insert_batch_fcfs_to_queue:: queue contents before\n");
  // print_batch_fcfs_queue(queue);
  queue->iobufcnt++;

  // if this request is not part of a batch, then just add it at the end of the queue.
  if (new_iobuf->batchno == -1) {
    new_iobuf->next = queue->list->next;
    new_iobuf->prev = queue->list;
    new_iobuf->next->prev = new_iobuf;
    new_iobuf->prev->next = new_iobuf;
    queue->list = new_iobuf;

    new_iobuf->batch_complete = TRUE;

    // printf("ioqueue_insert_batch_fcfs_to_queue:: queue contents after\n");
    // print_batch_fcfs_queue(queue);

    return;
  }

  // if it is part of a batch, walk the entire queue and find where to insert it.
  // the new iobuf should go after the last request in its batch, or at the end of the queue
  // if this is the first request in the batch.

  tmp = queue->list;

  for (i = 0; i < (queue->iobufcnt - 1); i++) {
    if (tmp->batchno == new_iobuf->batchno) {
      // chain the new request onto this batch and free new_iobuf
      event_ptr = tmp->batch_list;

      while (event_ptr->batch_next != NULL) {
	event_ptr = event_ptr->batch_next;
      }
      
      event_ptr->batch_next = new_iobuf->iolist;
      event_ptr->batch_next->batch_prev = event_ptr;
      event_ptr->batch_next->batch_next = NULL;

      if (new_iobuf->iolist->batch_complete == TRUE) {
	tmp->batch_complete = TRUE;
      } else {
	tmp->batch_complete = FALSE;
      }

      tmp->batch_size++;
      tmp->reqcnt++;

      // queue->listlen--;
      // because we didn't actually add an iobuf to the queue after all
      queue->iobufcnt--;
      addtoextraq((event *)new_iobuf);

      // printf("ioqueue_insert_batch_fcfs_to_queue:: queue contents after\n");
      // print_batch_fcfs_queue(queue);

      return;
    } else {
      tmp = tmp->next;
    }
  }

  // this batch doesn't exist in the queue yet, so insert new_iobuf at the end of the queue
  new_iobuf->next = queue->list->next;
  new_iobuf->prev = queue->list;
  new_iobuf->next->prev = new_iobuf;
  new_iobuf->prev->next = new_iobuf;
  queue->list = new_iobuf;

  new_iobuf->batch_size = 1;
  
  // printf("ioqueue_insert_batch_fcfs_to_queue:: queue contents after\n");
  // print_batch_fcfs_queue(queue);

  return;
}


/* queue->list not NULL when entered */

static void ioqueue_insert_fcfs_to_queue (subqueue *queue, iobuf *temp)
{
   temp->next = queue->list->next;
   temp->prev = queue->list;
   temp->next->prev = temp;
   temp->prev->next = temp;
   queue->list = temp;
}


/* queue->list not NULL when entered */

static void ioqueue_insert_ordered_to_queue (subqueue *queue, iobuf *temp)
{
   iobuf *head;
   iobuf *run;

   head = queue->list->next;

   if ((temp->cylinder < head->cylinder)       ||
       ((temp->cylinder == head->cylinder) && 
        (temp->surface < head->surface))       ||
       ((temp->cylinder == head->cylinder) && 
        (temp->surface == head->surface)   && 
        (temp->blkno < head->blkno))) {
      queue->list->next = temp;
      temp->next = head;
      temp->prev = queue->list;
      head->prev = temp;

   } else if ((temp->cylinder > queue->list->cylinder)       ||
              ((temp->cylinder == queue->list->cylinder) && 
               (temp->surface > queue->list->surface))       ||
              ((temp->cylinder == queue->list->cylinder) && 
               (temp->surface == queue->list->surface)   && 
               (temp->blkno >= queue->list->blkno))) {
      temp->next = head;
      temp->prev = queue->list;
      head->prev = temp;
      queue->list->next = temp;
      queue->list = temp;
   } else {
      run = head;
      while ((temp->cylinder > run->next->cylinder)     ||
             ((temp->cylinder == run->next->cylinder)  && 
              (temp->surface > run->next->surface))     ||
             ((temp->cylinder == run->next->cylinder)  && 
              (temp->surface == run->next->surface)    && 
              (temp->blkno >= run->next->blkno))) {
         run = run->next;
      }
      temp->next = run->next;
      temp->prev = run;
      temp->next->prev = temp;
      run->next = temp;
   }
}


static int ioqueue_check_concat (subqueue *queue, iobuf *req1, iobuf *req2, int concatmax)
{
   ioreq_event *tmp;
   int seqscheme = queue->bigqueue->seqscheme;
   int (**concatok)(void *,int,int,int,int) = queue->bigqueue->concatok;
   void *concatokparam = queue->bigqueue->concatokparam;

   if (req1->next != req2) {
      fprintf(stderr, "Non-adjacent requests sent to ioqueue_check_concat\n");
      exit(1);
   }
   if (req1->flags & READ) {
      if (!(seqscheme & IOQUEUE_CONCAT_READS) || !(req2->flags & READ)) {
	 return(0);
      }
   } else {
      if (!(seqscheme & IOQUEUE_CONCAT_WRITES) || (req2->flags & READ)) {
	 return(0);
      }
   }
   if ((req1 == queue->list) || (req1 == req2) || !READY_TO_GO(req1,queue) || !READY_TO_GO(req2,queue) || ((req1->blkno + req1->totalsize) != req2->blkno) || ((req1->totalsize + req2->totalsize) > concatmax)) {
      return(0);
   }
   if (concatok) {
      if ((*concatok)(concatokparam, req1->blkno, req1->totalsize, req2->blkno, req2->totalsize) == 0) {
	 return(0);
      }
   }
   tmp = req1->iolist;
   if (tmp == NULL) {
      req1->iolist = req2->iolist;
   } else {
      while (tmp->next) {
         tmp = tmp->next;
      }
      tmp->next = req2->iolist;
   }
   req1->next = req2->next;
   req1->next->prev = req1;
   req1->reqcnt += req2->reqcnt;
   req1->totalsize += req2->totalsize;
   if (queue->list == req2) {
      queue->list = req1;
   }
   queue->iobufcnt--;
   addtoextraq((event *) req2);
   return(1);
}


static void ioqueue_insert_new_request (subqueue *queue, iobuf *temp)
{
   int concatmax;

   // ioqueue_print_contents(queue);

   ioqueue_update_subqueue_statistics(queue);
   queue->iobufcnt++;
   queue->listlen++;  // COULD BE A BUG!
   if (temp->flags & READ) {
      queue->readlen++;
      queue->numreads++;
   } else {
      queue->numwrites++;
   }

   if (queue->list == NULL) {
      queue->list = temp;
      temp->next = temp;
      temp->prev = temp;
      if ((queue->sched_alg == BATCH_FCFS) && (temp->batchno != -1)) {
	temp->batch_size = 1;
	temp->batch_list = temp->iolist;
      }
   } else {
      if ((queue->sched_alg == FCFS) || (queue->sched_alg == PRI_VSCAN_LBN)) {
         ioqueue_insert_fcfs_to_queue(queue, temp);
      } else if (queue->sched_alg == BATCH_FCFS) {
	ioqueue_insert_batch_fcfs_to_queue(queue, temp);
      }
      else {
         ioqueue_insert_ordered_to_queue(queue, temp);
      }
   }
   concatmax = queue->bigqueue->concatmax;
   if (concatmax) {
      temp = temp->prev;
      if (!(ioqueue_check_concat(queue, temp, temp->next, concatmax))) {
	 temp = temp->next;
      }
      ioqueue_check_concat(queue, temp, temp->next, concatmax);
   }
   // ioqueue_print_contents(queue);
}


/* Returns 0 if request is sequential from a previous request (and detection */
/* enabled).  Otherwise returns 1.				             */
/* Assuming no command queueing.					     */

static int ioqueue_seqstream_head (ioqueue *queue, iobuf *listhead, iobuf *current)
{
   int idiff;
   int ret = 0;

   if (!(queue->seqscheme & (IOQUEUE_SEQSTREAM_READS|IOQUEUE_SEQSTREAM_WRITES|IOQUEUE_SEQSTREAM_EITHER))) {
      return(1);
   }
   idiff = queue->seqstreamdiff;
   if ((current == listhead) || !READY_TO_GO(current->prev,(&queue->base))) {
      ret = 1;
   }
   if (ret == 0) {
      if (current->flags & READ) {
         if (current->prev->flags & READ) {
	    if (!(queue->seqscheme & (IOQUEUE_SEQSTREAM_READS|IOQUEUE_SEQSTREAM_EITHER))) {
	       ret = 1;
	    }
         } else {
	    if (!(queue->seqscheme & IOQUEUE_SEQSTREAM_EITHER)) {
	       ret = 1;
	    }
         }
	 if ((current->prev->blkno != current->blkno) && (((current->prev->blkno + current->prev->totalsize + idiff) < current->blkno))) {
	    ret = 1;
	 }
      } else {
         if (current->prev->flags & READ) {
	    if (!(queue->seqscheme & IOQUEUE_SEQSTREAM_EITHER)) {
	       ret = 1;
	    }
         } else {
	    if (!(queue->seqscheme & (IOQUEUE_SEQSTREAM_WRITES|IOQUEUE_SEQSTREAM_EITHER))) {
	       ret = 1;
	    }
         }
	 if ((current->prev->blkno != current->blkno) && ((current->prev->blkno + current->prev->totalsize) != current->blkno)) {
	    ret = 1;
	 }
      }
   }
   return(ret);
}


/* Queue contains >= 2 items when called */

static iobuf * ioqueue_get_request_from_fcfs_queue (subqueue *queue)
{
   iobuf *tmp;
   int i;

   tmp = queue->list->next;
   for (i = 0; i < queue->iobufcnt; i++) {
      if (queue->force_absolute_fcfs) {
         if (tmp->state == WAITING) {
            if (READY_TO_GO(tmp,queue)) {
               return(tmp);
            } else {
               return(NULL);
            }
         }
      } else {
         if (READY_TO_GO(tmp,queue)) {
            return(tmp);
         }
      }
      tmp = tmp->next;
   }
   return(NULL);
}


/* Queue contains >= 2 items when called */

static int ioqueue_get_priority_level (ioqueue *ioqueue, iobuf *req)
{
   int ret = 0;

   if (ioqueue->priority_mix == 1) {
      if ((req->flags & TIME_CRITICAL) || (req->flags & READ)) {
	 ret = 1;
      }
   } else if (ioqueue->priority_mix == 2) {
      if (req->flags & TIME_CRITICAL) {
	 ret = 2;
      } else if (req->flags & READ) {
	 ret = 1;
      }
   } else if (ioqueue->priority_mix == 3) {
      if (req->flags & READ) {
	 ret = 2;
      } else if (req->flags & TIME_CRITICAL) {
	 ret = 1;
      }
   } else if (ioqueue->priority_mix == 4) {
      if (req->flags & TIME_CRITICAL) {
	 ret = (req->flags & READ) ? 2 : 3;
      } else {
	 ret = (req->flags & READ) ? 1 : 0;
      }
   } else if (ioqueue->priority_mix == 5) {
      if (req->flags & READ) {
	 ret = 1;
      }
   } else if (ioqueue->priority_mix == 6) {
      if (req->flags & TIME_CRITICAL) {
	 ret = 1;