drivers/usb/usbehci/usb_queue.cpp

   1 /*
   2  * PROJECT:     ReactOS Universal Serial Bus Bulk Enhanced Host Controller Interface
   3  * LICENSE:     GPL - See COPYING in the top level directory
   4  * FILE:        drivers/usb/usbehci/usb_queue.cpp
   5  * PURPOSE:     USB EHCI device driver.
   6  * PROGRAMMERS:
   7  *              Michael Martin (michael.martin@reactos.org)
   8  *              Johannes Anderwald (johannes.anderwald@reactos.org)
   9  */
  10
  11 #include "usbehci.h"
  12
  13 #define NDEBUG
  14 #include <debug.h>
  15
  16 class CUSBQueue : public IEHCIQueue
  17 {
  18 public:
  19     STDMETHODIMP QueryInterface( REFIID InterfaceId, PVOID* Interface);
  20
  21     STDMETHODIMP_(ULONG) AddRef()
  22     {
  23         InterlockedIncrement(&m_Ref);
  24         return m_Ref;
  25     }
  26     STDMETHODIMP_(ULONG) Release()
  27     {
  28         InterlockedDecrement(&m_Ref);
  29
  30         if (!m_Ref)
  31         {
  32             delete this;
  33             return 0;
  34         }
  35         return m_Ref;
  36     }
  37
  38     // IUSBQueue functions
  39     IMP_IUSBQUEUE
  40
  41     // IEHCIQueue functions
  42     IMP_IEHCIQUEUE
  43
  44     // constructor / destructor
  45     CUSBQueue(IUnknown *OuterUnknown){}
  46     virtual ~CUSBQueue(){}
  47
  48 protected:
  49     LONG m_Ref;                                                                         // reference count
  50     PKSPIN_LOCK m_Lock;                                                                  // list lock
  51     PDMA_ADAPTER m_Adapter;                                                             // dma adapter
  52     PEHCIHARDWAREDEVICE m_Hardware;                                                     // stores hardware object
  53     PQUEUE_HEAD AsyncListQueueHead;                                                     // async queue head
  54     LIST_ENTRY m_CompletedRequestAsyncList;                                             // completed async request list
  55     LIST_ENTRY m_PendingRequestAsyncList;                                               // pending async request list
  56     ULONG m_MaxPeriodicListEntries;                                                     // max periodic list entries
  57     ULONG m_MaxPollingInterval;                                                         // max polling interval
  58     PHYSICAL_ADDRESS m_SyncFrameListAddr;                                               // physical address of sync frame list
  59     PULONG m_SyncFrameList;                                                             // virtual address of sync frame list
  60
  61     // queue head manipulation functions
  62     VOID LinkQueueHead(PQUEUE_HEAD HeadQueueHead, PQUEUE_HEAD NewQueueHead);
  63     VOID UnlinkQueueHead(PQUEUE_HEAD QueueHead);
  64     VOID LinkQueueHeadChain(PQUEUE_HEAD HeadQueueHead, PQUEUE_HEAD NewQueueHead);
  65     PQUEUE_HEAD UnlinkQueueHeadChain(PQUEUE_HEAD HeadQueueHead, ULONG Count);
  66
  67     // processes the async list
  68     VOID ProcessAsyncList(IN NTSTATUS Status, OUT PULONG ShouldRingDoorBell);
  69
  70     // processes the async list
  71     VOID ProcessPeriodicSchedule(IN NTSTATUS Status, OUT PULONG ShouldRingDoorBell);
  72
  73     // called for each completed queue head
  74     VOID QueueHeadCompletion(PQUEUE_HEAD QueueHead, NTSTATUS Status);
  75
  76     // called for each completed queue head
  77     VOID QueueHeadInterruptCompletion(PQUEUE_HEAD QueueHead, NTSTATUS Status);
  78
  79     // called when the completion queue is cleaned up
  80     VOID QueueHeadCleanup(PQUEUE_HEAD QueueHead);
  81
  82     // initializes the sync schedule
  83     NTSTATUS InitializeSyncSchedule(IN PEHCIHARDWAREDEVICE Hardware, IN PDMAMEMORYMANAGER MemManager);
  84
  85     // links interrupt queue head
  86     VOID LinkInterruptQueueHead(PQUEUE_HEAD QueueHead);
  87
  88     // interval index
  89     UCHAR GetIntervalIndex(UCHAR Interval);
  90
  91
  92     // interrupt queue heads
  93     PQUEUE_HEAD m_InterruptQueueHeads[EHCI_INTERRUPT_ENTRIES_COUNT];
  94
  95     // contains the periodic queue heads
  96     LIST_ENTRY m_PeriodicQueueHeads;
  97 };
  98
  99 //=================================================================================================
 100 // COM
 101 //
 102 NTSTATUS
 103 STDMETHODCALLTYPE
 104 CUSBQueue::QueryInterface(
 105     IN  REFIID refiid,
 106     OUT PVOID* Output)
 107 {
 108     if (IsEqualGUIDAligned(refiid, IID_IUnknown))
 109     {
 110         *Output = PVOID(PUNKNOWN(this));
 111         PUNKNOWN(*Output)->AddRef();
 112         return STATUS_SUCCESS;
 113     }
 114
 115     return STATUS_UNSUCCESSFUL;
 116 }
 117
 118 NTSTATUS
 119 STDMETHODCALLTYPE
 120 CUSBQueue::Initialize(
 121     IN PUSBHARDWAREDEVICE Hardware,
 122     IN PDMA_ADAPTER AdapterObject,
 123     IN PDMAMEMORYMANAGER MemManager,
 124     IN OPTIONAL PKSPIN_LOCK Lock)
 125 {
 126     NTSTATUS Status = STATUS_SUCCESS;
 127
 128     DPRINT("CUSBQueue::Initialize()\n");
 129
 130     ASSERT(Hardware);
 131
 132     //
 133     // store device lock
 134     //
 135     m_Lock = Lock;
 136
 137     //
 138     // store hardware object
 139     //
 140     m_Hardware = PEHCIHARDWAREDEVICE(Hardware);
 141
 142
 143     //
 144     // Get the AsyncQueueHead
 145     //
 146     AsyncListQueueHead = (PQUEUE_HEAD)m_Hardware->GetAsyncListQueueHead();
 147
 148     //
 149     // Initialize the List Head
 150     //
 151     InitializeListHead(&AsyncListQueueHead->LinkedQueueHeads);
 152
 153     //
 154     // Initialize completed async list head
 155     //
 156     InitializeListHead(&m_CompletedRequestAsyncList);
 157
 158     //
 159     // Initialize pending async list head
 160     //
 161     InitializeListHead(&m_PendingRequestAsyncList);
 162
 163     //
 164     // initialize periodic queue heads
 165     //
 166     InitializeListHead(&m_PeriodicQueueHeads);
 167
 168     //
 169     // now initialize sync schedule
 170     //
 171     Status = InitializeSyncSchedule(m_Hardware, MemManager);
 172
 173
 174     return Status;
 175 }
 176
 177 NTSTATUS
 178 CUSBQueue::InitializeSyncSchedule(
 179     IN PEHCIHARDWAREDEVICE Hardware,
 180     IN PDMAMEMORYMANAGER MemManager)
 181 {
 182     PHYSICAL_ADDRESS QueueHeadPhysAddr;
 183     NTSTATUS Status;
 184     ULONG Index, Interval, IntervalIndex;
 185     PQUEUE_HEAD QueueHead;
 186
 187     //
 188     // FIXME: check if smaller list sizes are supported
 189     //
 190     m_MaxPeriodicListEntries = 1024;
 191
 192     //
 193     // use polling scheme of 512ms
 194     //
 195     m_MaxPollingInterval = 512;
 196
 197     //
 198     // first allocate a page to hold the queue array
 199     //
 200     Status = MemManager->Allocate(m_MaxPeriodicListEntries * sizeof(PVOID), (PVOID*)&m_SyncFrameList, &m_SyncFrameListAddr);
 201     if (!NT_SUCCESS(Status))
 202     {
 203         //
 204         // failed to allocate sync frame list array
 205         //
 206         DPRINT1("Failed to allocate sync frame list\n");
 207         return STATUS_INSUFFICIENT_RESOURCES;
 208     }
 209
 210     for(Index = 0; Index < EHCI_INTERRUPT_ENTRIES_COUNT; Index++)
 211     {
 212         //
 213         // allocate queue head
 214         //
 215         Status = MemManager->Allocate(sizeof(QUEUE_HEAD), (PVOID*)&QueueHead, &QueueHeadPhysAddr);
 216         if (!NT_SUCCESS(Status))
 217         {
 218             //
 219             // failed to create queue head
 220             //
 221             DPRINT1("Failed to create queue head\n");
 222             return Status;
 223         }
 224
 225         //
 226         // initialize queue head
 227         //
 228         QueueHead->HorizontalLinkPointer = TERMINATE_POINTER;
 229         QueueHead->AlternateNextPointer = TERMINATE_POINTER;
 230         QueueHead->NextPointer = TERMINATE_POINTER;
 231         QueueHead->EndPointCharacteristics.MaximumPacketLength = 64;
 232         QueueHead->EndPointCharacteristics.NakCountReload = 0x3;
 233         QueueHead->EndPointCharacteristics.EndPointSpeed = QH_ENDPOINT_HIGHSPEED;
 234         QueueHead->EndPointCapabilities.NumberOfTransactionPerFrame = 0x01;
 235         QueueHead->PhysicalAddr = QueueHeadPhysAddr.LowPart;
 236         QueueHead->Token.Bits.Halted = TRUE; //FIXME
 237         m_InterruptQueueHeads[Index]= QueueHead;
 238
 239         if (Index > 0)
 240         {
 241              // link all to the first queue head
 242              QueueHead->HorizontalLinkPointer = m_InterruptQueueHeads[0]->PhysicalAddr | QH_TYPE_QH;
 243              QueueHead->NextQueueHead = m_InterruptQueueHeads[0];
 244         }
 245     }
 246
 247     //
 248     // build interrupt tree
 249     //
 250     Interval = EHCI_FRAMELIST_ENTRIES_COUNT;
 251     IntervalIndex = EHCI_INTERRUPT_ENTRIES_COUNT - 1;
 252     while (Interval > 1)
 253     {
 254         for (Index = Interval / 2; Index < EHCI_FRAMELIST_ENTRIES_COUNT; Index += Interval)
 255         {
 256             DPRINT("Index %lu IntervalIndex %lu\n", Index, IntervalIndex);
 257             m_SyncFrameList[Index] = m_InterruptQueueHeads[IntervalIndex]->PhysicalAddr | QH_TYPE_QH;
 258         }
 259         IntervalIndex--;
 260         Interval /= 2;
 261     }
 262
 263     //
 264     // now set the sync base
 265     //
 266     Hardware->SetPeriodicListRegister(m_SyncFrameListAddr.LowPart);
 267
 268     //
 269     // sync frame list initialized
 270     //
 271     return STATUS_SUCCESS;
 272 }
 273
 274 NTSTATUS
 275 STDMETHODCALLTYPE
 276 CUSBQueue::AddUSBRequest(
 277     IUSBRequest * Req)
 278 {
 279     PQUEUE_HEAD QueueHead;
 280     NTSTATUS Status;
 281     ULONG Type;
 282     KIRQL OldLevel;
 283     PEHCIREQUEST Request;
 284
 285     // sanity check
 286     ASSERT(Req != NULL);
 287
 288     // get internal req
 289     Request = PEHCIREQUEST(Req);
 290
 291     // get request type
 292     Type = Request->GetTransferType();
 293
 294     // check if supported
 295     switch(Type)
 296     {
 297         case USB_ENDPOINT_TYPE_ISOCHRONOUS:
 298             /* NOT IMPLEMENTED IN QUEUE */
 299             Status = STATUS_NOT_SUPPORTED;
 300             break;
 301         case USB_ENDPOINT_TYPE_INTERRUPT:
 302         case USB_ENDPOINT_TYPE_BULK:
 303         case USB_ENDPOINT_TYPE_CONTROL:
 304             Status = STATUS_SUCCESS;
 305             break;
 306         default:
 307             /* BUG */
 308             PC_ASSERT(FALSE);
 309             Status = STATUS_NOT_SUPPORTED;
 310     }
 311
 312     // check for success
 313     if (!NT_SUCCESS(Status))
 314     {
 315         // request not supported, please try later
 316         return Status;
 317     }
 318
 319     // get queue head
 320     Status = Request->GetQueueHead(&QueueHead);
 321
 322     // check for success
 323     if (!NT_SUCCESS(Status))
 324     {
 325         // failed to get queue head
 326         return Status;
 327     }
 328
 329     // acquire lock
 330     KeAcquireSpinLock(m_Lock, &OldLevel);
 331
 332     if (Type == USB_ENDPOINT_TYPE_BULK || Type == USB_ENDPOINT_TYPE_CONTROL)
 333     {
 334         // Add to list
 335         LinkQueueHead(AsyncListQueueHead, QueueHead);
 336     }
 337     else if (Type == USB_ENDPOINT_TYPE_INTERRUPT)
 338     {
 339         // get interval
 340         LinkInterruptQueueHead(QueueHead);
 341     }
 342
 343     // release lock
 344     KeReleaseSpinLock(m_Lock, OldLevel);
 345
 346
 347     // add extra reference which is released when the request is completed
 348     Request->AddRef();
 349
 350     // done
 351     return STATUS_SUCCESS;
 352 }
 353
 354 NTSTATUS
 355 STDMETHODCALLTYPE
 356 CUSBQueue::CreateUSBRequest(
 357     IUSBRequest **OutRequest)
 358 {
 359     PUSBREQUEST UsbRequest;
 360     NTSTATUS Status;
 361
 362     *OutRequest = NULL;
 363     Status = InternalCreateUSBRequest(&UsbRequest);
 364
 365     if (NT_SUCCESS(Status))
 366     {
 367         *OutRequest = UsbRequest;
 368     }
 369
 370     return Status;
 371 }
 372
 373 UCHAR
 374 CUSBQueue::GetIntervalIndex(
 375     UCHAR Interval)
 376 {
 377     UCHAR IntervalIndex;
 378
 379     ASSERT(Interval != 0);
 380     if (Interval == 1)
 381         IntervalIndex = 1;
 382     else if (Interval == 2)
 383         IntervalIndex = 2;
 384     else if (Interval <= 4)
 385         IntervalIndex = 3;
 386     else if (Interval <= 8)
 387         IntervalIndex = 4;
 388     else if (Interval <= 16)
 389         IntervalIndex = 5;
 390     else if (Interval <= 32)
 391         IntervalIndex = 6;
 392     else if (Interval <= 64)
 393         IntervalIndex = 7;
 394     else if (Interval <= 128)
 395         IntervalIndex = 8;
 396     else
 397         IntervalIndex = 9;
 398
 399     ASSERT(IntervalIndex < EHCI_INTERRUPT_ENTRIES_COUNT);
 400     return IntervalIndex;
 401 }
 402
 403 VOID
 404 CUSBQueue::LinkInterruptQueueHead(
 405     PQUEUE_HEAD QueueHead)
 406 {
 407     PEHCIREQUEST Request;
 408     UCHAR Interval, IntervalIndex;
 409     USB_DEVICE_SPEED DeviceSpeed;
 410     PQUEUE_HEAD InterruptQueueHead;
 411
 412     // get internal req
 413     Request = PEHCIREQUEST(QueueHead->Request);
 414     ASSERT(Request);
 415
 416     // get interval
 417     Interval = Request->GetInterval();
 418
 419     // get device speed
 420     DeviceSpeed = Request->GetSpeed();
 421     if (DeviceSpeed == UsbHighSpeed)
 422     {
 423         // interrupt queue head can be scheduled on each possible micro frame
 424         QueueHead->EndPointCapabilities.InterruptScheduleMask = 0xFF;
 425     }
 426     else
 427     {
 428         // As we do not yet support FSTNs to correctly reference low/full
 429         // speed interrupt transfers, we simply put them into the 1 interval
 430         // queue. This way we ensure that we reach them on every micro frame
 431         // and can do the corresponding start/complete split transactions.
 432         // ToDo: use FSTNs to correctly link non high speed interrupt transfers
 433         Interval = 1;
 434
 435         // For now we also force start splits to be in micro frame 0 and
 436         // complete splits to be in micro frame 2, 3 and 4.
 437         QueueHead->EndPointCapabilities.InterruptScheduleMask = 0x01;
 438         QueueHead->EndPointCapabilities.SplitCompletionMask = 0x1C;
 439     }
 440
 441     // sanitize interrupt interval
 442     Interval = max(1, Interval);
 443
 444     // get interval index
 445     IntervalIndex = GetIntervalIndex(Interval);
 446
 447
 448     // get interrupt queue head
 449     InterruptQueueHead = m_InterruptQueueHeads[IntervalIndex];
 450
 451     // link queue head
 452     QueueHead->HorizontalLinkPointer = InterruptQueueHead->HorizontalLinkPointer;
 453     QueueHead->NextQueueHead = InterruptQueueHead->NextQueueHead;
 454
 455     InterruptQueueHead->HorizontalLinkPointer = QueueHead->PhysicalAddr | QH_TYPE_QH;
 456     InterruptQueueHead->NextQueueHead = QueueHead;
 457
 458     // store in periodic list
 459     InsertTailList(&m_PeriodicQueueHeads, &QueueHead->LinkedQueueHeads);
 460 }
 461
 462 //
 463 // LinkQueueHead - Links one QueueHead to the end of HeadQueueHead list, updating HorizontalLinkPointer.
 464 //
 465 VOID
 466 CUSBQueue::LinkQueueHead(
 467     PQUEUE_HEAD HeadQueueHead,
 468     PQUEUE_HEAD NewQueueHead)
 469 {
 470     PQUEUE_HEAD LastQueueHead, NextQueueHead;
 471     PLIST_ENTRY Entry;
 472     ASSERT(HeadQueueHead);
 473     ASSERT(NewQueueHead);
 474
 475     //
 476     // Link the LIST_ENTRYs
 477     //
 478     //ASSERT(IsListEmpty(&HeadQueueHead->LinkedQueueHeads));
 479     InsertTailList(&HeadQueueHead->LinkedQueueHeads, &NewQueueHead->LinkedQueueHeads);
 480
 481     //
 482     // Update HLP for NewQueueHead to point to next, which should be the HeadQueueHead
 483     //
 484     Entry = NewQueueHead->LinkedQueueHeads.Flink;
 485     NextQueueHead = CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
 486     //ASSERT(NextQueueHead == HeadQueueHead);
 487     NewQueueHead->HorizontalLinkPointer = (NextQueueHead->PhysicalAddr | QH_TYPE_QH);
 488
 489     _ReadWriteBarrier();
 490
 491     //
 492     // Update HLP for Previous QueueHead, which should be the last in list.
 493     //
 494     Entry = NewQueueHead->LinkedQueueHeads.Blink;
 495     LastQueueHead = CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
 496     //ASSERT(LastQueueHead == HeadQueueHead);
 497     LastQueueHead->HorizontalLinkPointer = (NewQueueHead->PhysicalAddr | QH_TYPE_QH);
 498
 499     //
 500     // head queue head must be halted
 501     //
 502     //PC_ASSERT(HeadQueueHead->Token.Bits.Halted == TRUE);
 503 }
 504
 505 //
 506 // UnlinkQueueHead - Unlinks one QueueHead, updating HorizontalLinkPointer.
 507 //
 508 VOID
 509 CUSBQueue::UnlinkQueueHead(
 510     PQUEUE_HEAD QueueHead)
 511 {
 512     PQUEUE_HEAD PreviousQH, NextQH;
 513     PLIST_ENTRY Entry;
 514
 515     //
 516     // sanity check: there must be at least one queue head with halted bit set
 517     //
 518     //PC_ASSERT(QueueHead->Token.Bits.Halted == 0);
 519
 520     //
 521     // get previous link
 522     //
 523     Entry = QueueHead->LinkedQueueHeads.Blink;
 524
 525     //
 526     // get queue head structure
 527     //
 528     PreviousQH = CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
 529
 530     //
 531     // get next link
 532     //
 533     Entry = QueueHead->LinkedQueueHeads.Flink;
 534
 535     //
 536     // get queue head structure
 537     //
 538     NextQH = CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
 539
 540     //
 541     // sanity check
 542     //
 543     ASSERT(QueueHead->HorizontalLinkPointer == (NextQH->PhysicalAddr | QH_TYPE_QH));
 544
 545     //
 546     // remove queue head from linked list
 547     //
 548     PreviousQH->HorizontalLinkPointer = NextQH->PhysicalAddr | QH_TYPE_QH;
 549
 550     //
 551     // remove software link
 552     //
 553     RemoveEntryList(&QueueHead->LinkedQueueHeads);
 554 }
 555
 556 //
 557 // LinkQueueHeadChain - Links a list of QueueHeads to the HeadQueueHead list, updating HorizontalLinkPointer.
 558 //
 559 VOID
 560 CUSBQueue::LinkQueueHeadChain(
 561     PQUEUE_HEAD HeadQueueHead,
 562     PQUEUE_HEAD NewQueueHead)
 563 {
 564     PQUEUE_HEAD LastQueueHead;
 565     PLIST_ENTRY Entry;
 566     ASSERT(HeadQueueHead);
 567     ASSERT(NewQueueHead);
 568
 569     //
 570     // Find the last QueueHead in NewQueueHead
 571     //
 572     Entry = NewQueueHead->LinkedQueueHeads.Blink;
 573     ASSERT(Entry != NewQueueHead->LinkedQueueHeads.Flink);
 574     LastQueueHead = CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
 575
 576     //
 577     // Set the LinkPointer and Flink
 578     //
 579     LastQueueHead->HorizontalLinkPointer = HeadQueueHead->PhysicalAddr | QH_TYPE_QH;
 580     LastQueueHead->LinkedQueueHeads.Flink = &HeadQueueHead->LinkedQueueHeads;
 581
 582     //
 583     // Fine the last QueueHead in HeadQueueHead
 584     //
 585     Entry = HeadQueueHead->LinkedQueueHeads.Blink;
 586     HeadQueueHead->LinkedQueueHeads.Blink = &LastQueueHead->LinkedQueueHeads;
 587     LastQueueHead = CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
 588     LastQueueHead->LinkedQueueHeads.Flink = &NewQueueHead->LinkedQueueHeads;
 589     LastQueueHead->HorizontalLinkPointer = NewQueueHead->PhysicalAddr | QH_TYPE_QH;
 590 }
 591
 592 //
 593 // UnlinkQueueHeadChain - Unlinks a list number of QueueHeads from HeadQueueHead list, updating HorizontalLinkPointer.
 594 // returns the chain of QueueHeads removed from HeadQueueHead.
 595 //
 596 PQUEUE_HEAD
 597 CUSBQueue::UnlinkQueueHeadChain(
 598     PQUEUE_HEAD HeadQueueHead,
 599     ULONG Count)
 600 {
 601     PQUEUE_HEAD LastQueueHead, FirstQueueHead;
 602     PLIST_ENTRY Entry;
 603     ULONG Index;
 604
 605     //
 606     // Find the last QueueHead in NewQueueHead
 607     //
 608     Entry = &HeadQueueHead->LinkedQueueHeads;
 609     FirstQueueHead = CONTAINING_RECORD(Entry->Flink, QUEUE_HEAD, LinkedQueueHeads);
 610
 611     for (Index = 0; Index < Count; Index++)
 612     {
 613         Entry = Entry->Flink;
 614
 615         if (Entry == &HeadQueueHead->LinkedQueueHeads)
 616         {
 617             DPRINT1("Warning; Only %lu QueueHeads in HeadQueueHead\n", Index);
 618             Count = Index + 1;
 619             break;
 620         }
 621     }
 622
 623     LastQueueHead = CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
 624     HeadQueueHead->LinkedQueueHeads.Flink = LastQueueHead->LinkedQueueHeads.Flink;
 625     if (Count + 1 == Index)
 626     {
 627         HeadQueueHead->LinkedQueueHeads.Blink = &HeadQueueHead->LinkedQueueHeads;
 628     }
 629     else
 630         HeadQueueHead->LinkedQueueHeads.Blink = LastQueueHead->LinkedQueueHeads.Flink;
 631
 632     FirstQueueHead->LinkedQueueHeads.Blink = &LastQueueHead->LinkedQueueHeads;
 633     LastQueueHead->LinkedQueueHeads.Flink = &FirstQueueHead->LinkedQueueHeads;
 634     LastQueueHead->HorizontalLinkPointer = TERMINATE_POINTER;
 635     return FirstQueueHead;
 636 }
 637
 638 VOID
 639 CUSBQueue::QueueHeadInterruptCompletion(
 640     PQUEUE_HEAD QueueHead,
 641     NTSTATUS Status)
 642 {
 643     PEHCIREQUEST Request;
 644     UCHAR Interval, IntervalIndex;
 645     PQUEUE_HEAD InterruptQueueHead, LastQueueHead = NULL;
 646
 647
 648     //
 649     // sanity check
 650     //
 651     PC_ASSERT(QueueHead->Request);
 652
 653     //
 654     // get IUSBRequest interface
 655     //
 656     Request = (PEHCIREQUEST)QueueHead->Request;
 657
 658     // get interval
 659     Interval = Request->GetInterval();
 660
 661     // sanitize interval
 662     Interval = max(1, Interval);
 663
 664     // get interval index
 665     IntervalIndex = GetIntervalIndex(Interval);
 666
 667     // get interrupt queue head from index
 668     InterruptQueueHead = m_InterruptQueueHeads[IntervalIndex];
 669
 670     while(InterruptQueueHead != NULL)
 671     {
 672         if (InterruptQueueHead == QueueHead)
 673             break;
 674
 675         // move to next queue head
 676         LastQueueHead = InterruptQueueHead;
 677         InterruptQueueHead = (PQUEUE_HEAD)InterruptQueueHead->NextQueueHead;
 678     }
 679
 680     if (InterruptQueueHead != QueueHead)
 681     {
 682         // queue head not in list
 683         ASSERT(FALSE);
 684         return;
 685     }
 686
 687     // now unlink queue head
 688     LastQueueHead->HorizontalLinkPointer = QueueHead->HorizontalLinkPointer;
 689     LastQueueHead->NextQueueHead = QueueHead->NextQueueHead;
 690
 691     DPRINT1("Periodic QueueHead %p Addr %x unlinked\n", QueueHead, QueueHead->PhysicalAddr);
 692
 693     // insert into completed list
 694     InsertTailList(&m_CompletedRequestAsyncList, &QueueHead->LinkedQueueHeads);
 695 }
 696
 697
 698
 699 VOID
 700 CUSBQueue::QueueHeadCompletion(
 701     PQUEUE_HEAD CurrentQH,
 702     NTSTATUS Status)
 703 {
 704     //
 705     // now unlink the queue head
 706     // FIXME: implement chained queue heads
 707     // no need to acquire locks, as it is called with locks held
 708     //
 709
 710     //
 711     // unlink queue head
 712     //
 713     UnlinkQueueHead(CurrentQH);
 714
 715     //
 716     // insert into completed list
 717     //
 718     InsertTailList(&m_CompletedRequestAsyncList, &CurrentQH->LinkedQueueHeads);
 719 }
 720
 721
 722 VOID
 723 CUSBQueue::ProcessPeriodicSchedule(
 724     IN NTSTATUS Status,
 725     OUT PULONG ShouldRingDoorBell)
 726 {
 727     KIRQL OldLevel;
 728     PLIST_ENTRY Entry;
 729     PQUEUE_HEAD QueueHead;
 730     PEHCIREQUEST Request;
 731     BOOLEAN IsQueueHeadComplete;
 732
 733     //
 734     // lock completed async list
 735     //
 736     KeAcquireSpinLock(m_Lock, &OldLevel);
 737
 738     //
 739     // walk async list
 740     //
 741     ASSERT(AsyncListQueueHead);
 742     Entry = m_PeriodicQueueHeads.Flink;
 743
 744     while(Entry != &m_PeriodicQueueHeads)
 745     {
 746         //
 747         // get queue head structure
 748         //
 749         QueueHead = CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
 750
 751         //
 752         // sanity check
 753         //
 754         PC_ASSERT(QueueHead->Request);
 755
 756         //
 757         // get IUSBRequest interface
 758         //
 759         Request = (PEHCIREQUEST)QueueHead->Request;
 760
 761         //
 762         // move to next entry
 763         //
 764         Entry = Entry->Flink;
 765
 766         //
 767         // check if queue head is complete
 768         //
 769         IsQueueHeadComplete = Request->IsQueueHeadComplete(QueueHead);
 770
 771         DPRINT("Request %p QueueHead %p Complete %c\n", Request, QueueHead, IsQueueHeadComplete);
 772
 773         //
 774         // check if queue head is complete
 775         //
 776         if (IsQueueHeadComplete)
 777         {
 778             //
 779             // current queue head is complete
 780             //
 781             QueueHeadInterruptCompletion(QueueHead, Status);
 782
 783             //
 784             // ring door bell is going to be necessary
 785             //
 786             *ShouldRingDoorBell = TRUE;
 787         }
 788     }
 789
 790     //
 791     // release lock
 792     //
 793     KeReleaseSpinLock(m_Lock, OldLevel);
 794
 795 }
 796
 797 VOID
 798 CUSBQueue::ProcessAsyncList(
 799     IN NTSTATUS Status,
 800     OUT PULONG ShouldRingDoorBell)
 801 {
 802     KIRQL OldLevel;
 803     PLIST_ENTRY Entry;
 804     PQUEUE_HEAD QueueHead;
 805     PEHCIREQUEST Request;
 806     BOOLEAN IsQueueHeadComplete;
 807
 808     //
 809     // lock completed async list
 810     //
 811     KeAcquireSpinLock(m_Lock, &OldLevel);
 812
 813     //
 814     // walk async list
 815     //
 816     ASSERT(AsyncListQueueHead);
 817     Entry = AsyncListQueueHead->LinkedQueueHeads.Flink;
 818
 819     while(Entry != &AsyncListQueueHead->LinkedQueueHeads)
 820     {
 821         //
 822         // get queue head structure
 823         //
 824         QueueHead = CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
 825
 826         //
 827         // sanity check
 828         //
 829         PC_ASSERT(QueueHead->Request);
 830
 831         //
 832         // get IUSBRequest interface
 833         //
 834         Request = (PEHCIREQUEST)QueueHead->Request;
 835
 836         //
 837         // move to next entry
 838         //
 839         Entry = Entry->Flink;
 840
 841         //
 842         // check if queue head is complete
 843         //
 844         IsQueueHeadComplete = Request->IsQueueHeadComplete(QueueHead);
 845
 846         DPRINT("Request %p QueueHead %p Complete %c\n", Request, QueueHead, IsQueueHeadComplete);
 847
 848         //
 849         // check if queue head is complete
 850         //
 851         if (IsQueueHeadComplete)
 852         {
 853             //
 854             // current queue head is complete
 855             //
 856             QueueHeadCompletion(QueueHead, Status);
 857
 858             //
 859             // ring door bell is going to be necessary
 860             //
 861             *ShouldRingDoorBell = TRUE;
 862         }
 863     }
 864
 865     //
 866     // release lock
 867     //
 868     KeReleaseSpinLock(m_Lock, OldLevel);
 869 }
 870
 871
 872 VOID
 873 STDMETHODCALLTYPE
 874 CUSBQueue::InterruptCallback(
 875     IN NTSTATUS Status,
 876     OUT PULONG ShouldRingDoorBell)
 877 {
 878     DPRINT("CUSBQueue::InterruptCallback\n");
 879
 880     //
 881     // process periodic schedule
 882     //
 883     ProcessPeriodicSchedule(Status, ShouldRingDoorBell);
 884
 885     //
 886     // iterate asynchronous list
 887     //
 888     *ShouldRingDoorBell = FALSE;
 889     ProcessAsyncList(Status, ShouldRingDoorBell);
 890 }
 891
 892 VOID
 893 CUSBQueue::QueueHeadCleanup(
 894     PQUEUE_HEAD CurrentQH)
 895 {
 896     PQUEUE_HEAD NewQueueHead;
 897     PEHCIREQUEST Request;
 898     BOOLEAN ShouldReleaseWhenDone;
 899     USBD_STATUS UrbStatus;
 900     KIRQL OldLevel;
 901
 902     //
 903     // sanity checks
 904     //
 905     PC_ASSERT(CurrentQH->Token.Bits.Active == 0);
 906     PC_ASSERT(CurrentQH->Request);
 907
 908
 909     //
 910     // get request
 911     //
 912     Request = (PEHCIREQUEST)CurrentQH->Request;
 913
 914     //
 915     // sanity check
 916     //
 917     PC_ASSERT(Request);
 918
 919     //
 920     // check if the queue head was completed with errors
 921     //
 922     if (CurrentQH->Token.Bits.Halted)
 923     {
 924         if (CurrentQH->Token.Bits.DataBufferError)
 925         {
 926             //
 927             // data buffer error
 928             //
 929             UrbStatus = USBD_STATUS_DATA_BUFFER_ERROR;
 930         }
 931         else if (CurrentQH->Token.Bits.BabbleDetected)
 932         {
 933             //
 934             // babble detected
 935             //
 936             UrbStatus = USBD_STATUS_BABBLE_DETECTED;
 937         }
 938         else
 939         {
 940             //
 941             // stall pid
 942             //
 943             UrbStatus = USBD_STATUS_STALL_PID;
 944         }
 945     }
 946     else
 947     {
 948         //
 949         // well done ;)
 950         //
 951         UrbStatus = USBD_STATUS_SUCCESS;
 952     }
 953
 954     //
 955     // Check if the transfer was completed and if UrbStatus is ok
 956     //
 957     if ((Request->IsRequestComplete() == FALSE) && (UrbStatus == USBD_STATUS_SUCCESS))
 958     {
 959         //
 960         // request is incomplete, get new queue head
 961         //
 962         if (Request->GetQueueHead(&NewQueueHead) == STATUS_SUCCESS)
 963         {
 964             //
 965             // let IUSBRequest free the queue head
 966             //
 967             Request->FreeQueueHead(CurrentQH);
 968
 969             //
 970             // first acquire request lock
 971             //
 972             KeAcquireSpinLock(m_Lock, &OldLevel);
 973
 974             //
 975             // add to pending list
 976             //
 977             InsertTailList(&m_PendingRequestAsyncList, &NewQueueHead->LinkedQueueHeads);
 978
 979             //
 980             // release queue head
 981             //
 982             KeReleaseSpinLock(m_Lock, OldLevel);
 983
 984             //
 985             // Done for now
 986             //
 987             return;
 988         }
 989         DPRINT1("Unable to create a new QueueHead\n");
 990         //ASSERT(FALSE);
 991
 992         //
 993         // Else there was a problem
 994         // FIXME: Find better return
 995         UrbStatus = USBD_STATUS_INSUFFICIENT_RESOURCES;
 996     }
 997
 998     if (UrbStatus != USBD_STATUS_SUCCESS)
 999     {
1000         DPRINT1("URB failed with status 0x%x\n", UrbStatus);
1001         //PC_ASSERT(FALSE);
1002     }
1003
1004     //
1005     // notify request that a transfer has completed
1006     //
1007     Request->CompletionCallback(UrbStatus != USBD_STATUS_SUCCESS ?  STATUS_UNSUCCESSFUL : STATUS_SUCCESS,
1008                                 UrbStatus,
1009                                 CurrentQH);
1010
1011     //
1012     // let IUSBRequest free the queue head
1013     //
1014     Request->FreeQueueHead(CurrentQH);
1015
1016     //
1017     // check if we should release request when done
1018     //
1019     ShouldReleaseWhenDone = Request->ShouldReleaseRequestAfterCompletion();
1020
1021     //
1022     // release reference when the request was added
1023     //
1024     Request->Release();
1025
1026     //
1027     // check if the operation was asynchronous
1028     //
1029     if (ShouldReleaseWhenDone)
1030     {
1031         //
1032         // release outstanding reference count
1033         //
1034         Request->Release();
1035     }
1036
1037     //
1038     // request is now released
1039     //
1040 }
1041
1042 VOID
1043 STDMETHODCALLTYPE
1044 CUSBQueue::CompleteAsyncRequests()
1045 {
1046     KIRQL OldLevel;
1047     PLIST_ENTRY Entry;
1048     PQUEUE_HEAD CurrentQH;
1049
1050     DPRINT("CUSBQueue::CompleteAsyncRequests\n");
1051
1052     //
1053     // first acquire request lock
1054     //
1055     KeAcquireSpinLock(m_Lock, &OldLevel);
1056
1057     //
1058     // the list should not be empty
1059     //
1060     PC_ASSERT(!IsListEmpty(&m_CompletedRequestAsyncList));
1061
1062     while(!IsListEmpty(&m_CompletedRequestAsyncList))
1063     {
1064         //
1065         // remove first entry
1066         //
1067         Entry = RemoveHeadList(&m_CompletedRequestAsyncList);
1068
1069         //
1070         // get queue head structure
1071         //
1072         CurrentQH = (PQUEUE_HEAD)CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
1073
1074         //
1075         // release lock
1076         //
1077         KeReleaseSpinLock(m_Lock, OldLevel);
1078
1079         //
1080         // complete request now
1081         //
1082         QueueHeadCleanup(CurrentQH);
1083
1084         //
1085         // first acquire request lock
1086         //
1087         KeAcquireSpinLock(m_Lock, &OldLevel);
1088     }
1089
1090     //
1091     // is there a pending async entry
1092     //
1093     if (!IsListEmpty(&m_PendingRequestAsyncList))
1094     {
1095         //
1096         // remove first entry
1097         //
1098         Entry = RemoveHeadList(&m_PendingRequestAsyncList);
1099
1100         //
1101         // get queue head structure
1102         //
1103         CurrentQH = (PQUEUE_HEAD)CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
1104
1105         //
1106         // Add it to the AsyncList list
1107         //
1108         LinkQueueHead(AsyncListQueueHead, CurrentQH);
1109     }
1110
1111     //
1112     // release lock
1113     //
1114     KeReleaseSpinLock(m_Lock, OldLevel);
1115 }
1116
1117 NTSTATUS
1118 STDMETHODCALLTYPE
1119 CUSBQueue::AbortDevicePipe(
1120     IN UCHAR DeviceAddress,
1121     IN PUSB_ENDPOINT_DESCRIPTOR EndpointDescriptor)
1122 {
1123     KIRQL OldLevel;
1124     PLIST_ENTRY Entry;
1125     PQUEUE_HEAD QueueHead;
1126     LIST_ENTRY ListHead;
1127
1128     //
1129     // lock completed async list
1130     //
1131     KeAcquireSpinLock(m_Lock, &OldLevel);
1132
1133     DPRINT1("AbortDevicePipe DeviceAddress %x EndpointDescriptor %p Addr %x\n", DeviceAddress, EndpointDescriptor, EndpointDescriptor->bEndpointAddress);
1134
1135     //
1136     // init list head
1137     //
1138     InitializeListHead(&ListHead);
1139
1140
1141     //
1142     // walk async list
1143     //
1144     ASSERT(AsyncListQueueHead);
1145     Entry = AsyncListQueueHead->LinkedQueueHeads.Flink;
1146
1147     while(Entry != &AsyncListQueueHead->LinkedQueueHeads)
1148     {
1149         //
1150         // get queue head structure
1151         //
1152         QueueHead = (PQUEUE_HEAD)CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
1153         ASSERT(QueueHead);
1154
1155         //
1156         // move to next entry
1157         //
1158         Entry = Entry->Flink;
1159
1160         if (QueueHead->EndPointCharacteristics.DeviceAddress == DeviceAddress &&
1161             QueueHead->EndPointCharacteristics.EndPointNumber == (EndpointDescriptor->bEndpointAddress & 0xF) && QueueHead->Token.Bits.Halted)
1162         {
1163             //
1164             // unlink queue head
1165             //
1166             UnlinkQueueHead(QueueHead);
1167
1168             //
1169             // add to temp list
1170             //
1171             InsertTailList(&ListHead, &QueueHead->LinkedQueueHeads);
1172         }
1173     }
1174
1175     //
1176     // release lock
1177     //
1178     KeReleaseSpinLock(m_Lock, OldLevel);
1179
1180     while(!IsListEmpty(&ListHead))
1181     {
1182         //
1183         // remove entry
1184         //
1185         Entry = RemoveHeadList(&ListHead);
1186
1187         //
1188         // get queue head structure
1189         //
1190         QueueHead = (PQUEUE_HEAD)CONTAINING_RECORD(Entry, QUEUE_HEAD, LinkedQueueHeads);
1191         ASSERT(QueueHead);
1192
1193         //
1194         // cleanup queue head
1195         //
1196         QueueHeadCleanup(QueueHead);
1197     }
1198     return STATUS_SUCCESS;
1199 }
1200
1201
1202 NTSTATUS
1203 NTAPI
1204 CreateUSBQueue(
1205     PUSBQUEUE *OutUsbQueue)
1206 {
1207     PUSBQUEUE This;
1208
1209     //
1210     // allocate controller
1211     //
1212     This = new(NonPagedPool, TAG_USBEHCI) CUSBQueue(0);
1213     if (!This)
1214     {
1215         //
1216         // failed to allocate
1217         //
1218         return STATUS_INSUFFICIENT_RESOURCES;
1219     }
1220
1221     //
1222     // add reference count
1223     //
1224     This->AddRef();
1225
1226     //
1227     // return result
1228     //
1229     *OutUsbQueue = (PUSBQUEUE)This;
1230
1231     //
1232     // done
1233     //
1234     return STATUS_SUCCESS;
1235 }
1236