Kernel/USB: Implement UHCI Data structures

Implemented both Queue Heads and Transfer Descriptors. These
are required to actually perform USB transactions. The UHCI
driver sets up a pool of these that can be allocated when we
need them. It seems some drivers have these statically
allocated, so it might be worth looking into that, but
for now, the simple way seems to be to allocate them on
the fly as we need them, and then release them.

3 files changed, 529 insertions, 12 deletions

diff --git a/Kernel/Devices/USB/UHCIController.cpp b/Kernel/Devices/USB/UHCIController.cpp
index 2f26bdb092..372db51729 100644
--- a/Kernel/Devices/USB/UHCIController.cpp
+++ b/Kernel/Devices/USB/UHCIController.cpp
@@ -1,5 +1,6 @@
 /*
  * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2020, Jesse Buhagiar <jooster669@gmail.com>
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -25,13 +26,22 @@
  */
 
 #include <Kernel/Devices/USB/UHCIController.h>
+#include <Kernel/Process.h>
 #include <Kernel/StdLib.h>
+#include <Kernel/Time/TimeManagement.h>
+#include <Kernel/VM/AnonymousVMObject.h>
 #include <Kernel/VM/MemoryManager.h>
 
 #define UHCI_ENABLED 1
+#define UHCI_DEBUG
+
+static constexpr u8 MAXIMUM_NUMBER_OF_TDS = 128; // Upper pool limit. This consumes the second page we have allocated
+static constexpr u8 MAXIMUM_NUMBER_OF_QHS = 64;
 
 namespace Kernel::USB {
 
+static UHCIController* s_the;
+
 static constexpr u16 UHCI_USBCMD_RUN = 0x0001;
 static constexpr u16 UHCI_USBCMD_HOST_CONTROLLER_RESET = 0x0002;
 static constexpr u16 UHCI_USBCMD_GLOBAL_RESET = 0x0004;
@@ -53,6 +63,18 @@ static constexpr u8 UHCI_USBINTR_RESUME_INTR_ENABLE = 0x02;
 static constexpr u8 UHCI_USBINTR_IOC_ENABLE = 0x04;
 static constexpr u8 UHCI_USBINTR_SHORT_PACKET_INTR_ENABLE = 0x08;
 
+static constexpr u16 UHCI_FRAMELIST_FRAME_COUNT = 1024; // Each entry is 4 bytes in our allocated page
+static constexpr u16 UHCI_FRAMELIST_FRAME_INVALID = 0x0001;
+
+// *BSD and a few other drivers seem to use this number
+static constexpr u8 UHCI_NUMBER_OF_ISOCHRONOUS_TDS = 128;
+static constexpr u16 UHCI_NUMBER_OF_FRAMES = 1024;
+
+UHCIController& UHCIController::the()
+{
+    return *s_the;
+}
+
 void UHCIController::detect()
 {
 #if !UHCI_ENABLED
@@ -63,7 +85,8 @@ void UHCIController::detect()
             return;
 
         if (PCI::get_class(address) == 0xc && PCI::get_subclass(address) == 0x03 && PCI::get_programming_interface(address) == 0) {
-            new UHCIController(address, id);
+            if (!s_the)
+                s_the = new UHCIController(address, id);
         }
     });
 }
@@ -98,19 +121,202 @@ void UHCIController::reset()
     }
 
     // Let's allocate the physical page for the Frame List (which is 4KiB aligned)
-    m_framelist = MemoryManager::the().allocate_supervisor_physical_page()->paddr();
-    klog() << "UHCI: Allocated framelist at physical address " << m_framelist;
-    memset(reinterpret_cast<u32*>(low_physical_to_virtual(m_framelist.as_ptr())), 1, 1024); // All frames are TERMINATE frames
+    auto framelist_vmobj = ContiguousVMObject::create_with_size(PAGE_SIZE);
+    m_framelist = MemoryManager::the().allocate_kernel_region_with_vmobject(*framelist_vmobj, PAGE_SIZE, "UHCI Framelist", Region::Access::Write);
+    klog() << "UHCI: Allocated framelist at physical address " << m_framelist->physical_page(0)->paddr();
+    klog() << "UHCI: Framelist is at virtual address " << m_framelist->vaddr();
+    write_sofmod(64); // 1mS frame time
 
-    write_sofmod(64);                   // 1mS frame time
-    write_flbaseadd(m_framelist.get()); // Frame list (physical) address
-    write_frnum(0);                     // Set the initial frame number
+    create_structures();
+    setup_schedule();
+
+    // Let's set each of the frame values to TERMINATE so that the controller ignores them
+    for (auto frame = 0; frame < 1024; frame++) {
+    }
+
+    write_flbaseadd(m_framelist->physical_page(0)->paddr().get()); // Frame list (physical) address
+    write_frnum(0);                                                // Set the initial frame number
 
     // Enable all interrupt types
     write_frnum(UHCI_USBINTR_TIMEOUT_CRC_ENABLE | UHCI_USBINTR_RESUME_INTR_ENABLE | UHCI_USBINTR_IOC_ENABLE | UHCI_USBINTR_SHORT_PACKET_INTR_ENABLE);
     klog() << "UHCI: Reset completed!";
 }
 
+void UHCIController::create_structures()
+{
+    // Let's allocate memory for botht the QH and TD pools
+    // First the QH pool and all of the Interrupt QH's
+    auto qh_pool_vmobject = ContiguousVMObject::create_with_size(2 * PAGE_SIZE);
+    m_qh_pool = MemoryManager::the().allocate_kernel_region_with_vmobject(*qh_pool_vmobject, 2 * PAGE_SIZE, "UHCI Queue Head Pool", Region::Access::Write);
+    memset(m_qh_pool->vaddr().as_ptr(), 0, 2 * PAGE_SIZE); // Zero out both pages
+
+    // Let's populate our free qh list (so we have some we can allocate later on)
+    m_free_qh_pool.resize(MAXIMUM_NUMBER_OF_TDS);
+    for (size_t i = 0; i < m_free_qh_pool.size(); i++) {
+        auto placement_addr = reinterpret_cast<void*>(m_qh_pool->vaddr().get() + (i * sizeof(QueueHead)));
+        auto paddr = static_cast<u32>(m_qh_pool->physical_page(0)->paddr().get() + (i * sizeof(QueueHead)));
+        m_free_qh_pool.at(i) = new (placement_addr) QueueHead(paddr);
+
+        //auto& queue_head = m_free_qh_pool.at(i);
+    }
+
+    // Create the Interrupt Transfer, Full Speed/Low Speed Control and Bulk Queue Heads
+    m_interrupt_transfer_queue = allocate_queue_head();
+    m_lowspeed_control_qh = allocate_queue_head();
+    m_fullspeed_control_qh = allocate_queue_head();
+    m_bulk_qh = allocate_queue_head();
+    m_dummy_qh = allocate_queue_head();
+
+    // Now let's create the interrupt Queue Heads
+    m_interrupt_qh_list.resize(UHCI_NUMBER_OF_INTERRUPT_QHS);
+    for (size_t i = 0; i < m_interrupt_qh_list.size(); i++) {
+        m_interrupt_qh_list.at(i) = reinterpret_cast<QueueHead*>(m_qh_pool->vaddr().get() + (i * sizeof(QueueHead)));
+
+        auto& queue_head = m_interrupt_qh_list.at(i);
+        queue_head->paddr = static_cast<u32>(m_qh_pool->physical_page(0)->paddr().get() + (i * sizeof(QueueHead)));
+        queue_head->in_use = true;
+        queue_head->link_ptr = m_lowspeed_control_qh->paddr; // Link to the low-speed control queue head
+        queue_head->element_link_ptr = QueueHead::Terminate; // No elements attached to this queue head
+    }
+
+    // Now the Transfer Descriptor pool
+    auto td_pool_vmobject = ContiguousVMObject::create_with_size(2 * PAGE_SIZE);
+    m_td_pool = MemoryManager::the().allocate_kernel_region_with_vmobject(*td_pool_vmobject, 2 * PAGE_SIZE, "UHCI Transfer Descriptor Pool", Region::Access::Write);
+    memset(m_td_pool->vaddr().as_ptr(), 0, 2 * PAGE_SIZE);
+
+    // Set up the Isochronous Transfer Descriptor list
+    m_iso_td_list.resize(UHCI_NUMBER_OF_ISOCHRONOUS_TDS);
+    for (size_t i = 0; i < m_iso_td_list.size(); i++) {
+        auto placement_addr = reinterpret_cast<void*>(m_td_pool->vaddr().get() + (i * sizeof(Kernel::USB::TransferDescriptor)));
+        auto paddr = static_cast<u32>(m_td_pool->physical_page(0)->paddr().get() + (i * sizeof(Kernel::USB::TransferDescriptor)));
+
+        // Place a new Transfer Descriptor with a 1:1 in our region
+        // The pointer returned by `new()` lines up exactly with the value
+        // that we store in `paddr`, meaning our member functions directly
+        // access the raw descriptor (that we later send to the controller)
+        m_iso_td_list.at(i) = new (placement_addr) Kernel::USB::TransferDescriptor(paddr);
+        auto transfer_descriptor = m_iso_td_list.at(i);
+        transfer_descriptor->set_in_use(true); // Isochronous transfers are ALWAYS marked as in use (in case we somehow get allocated one...)
+        transfer_descriptor->set_isochronous();
+        transfer_descriptor->link_queue_head(m_interrupt_transfer_queue->paddr());
+        transfer_descriptor->print();
+    }
+
+    kprintf("Done!\n");
+
+    m_free_td_pool.resize(MAXIMUM_NUMBER_OF_TDS);
+    for (size_t i = 0; i < m_free_td_pool.size(); i++) {
+        auto placement_addr = reinterpret_cast<void*>(m_td_pool->vaddr().offset(PAGE_SIZE).get() + (i * sizeof(Kernel::USB::TransferDescriptor)));
+        auto paddr = static_cast<u32>(m_td_pool->physical_page(1)->paddr().get() + (i * sizeof(Kernel::USB::TransferDescriptor)));
+
+        // Place a new Transfer Descriptor with a 1:1 in our region
+        // The pointer returned by `new()` lines up exactly with the value
+        // that we store in `paddr`, meaning our member functions directly
+        // access the raw descriptor (that we later send to the controller)
+        m_free_td_pool.at(i) = new (placement_addr) Kernel::USB::TransferDescriptor(paddr);
+        //auto transfer_descriptor = m_free_td_pool.at(i);
+        //transfer_descriptor->print();
+    }
+
+#ifdef UHCI_DEBUG
+    klog() << "UHCI: Pool information:";
+    klog() << "\tqh_pool: " << PhysicalAddress(m_qh_pool->physical_page(0)->paddr()) << ", length: " << m_qh_pool->range().size();
+    klog() << "\ttd_pool: " << PhysicalAddress(m_td_pool->physical_page(0)->paddr()) << ", length: " << m_td_pool->range().size();
+#endif
+}
+
+void UHCIController::setup_schedule()
+{
+    //
+    // https://github.com/alkber/minix3-usbsubsystem/blob/master/usb/uhci-hcd.c
+    //
+    // This lad probably has the best explanation as to how this is actually done. I'll try and
+    // explain it here to so that there's no need for anyone to go hunting for this shit again, because
+    // the USB spec and Intel explain next to nothing.
+    // According to the USB spec (and the UHCI datasheet), 90% of the bandwidth should be used for
+    // Isochronous and """Interrupt""" related transfers, with the rest being used for control and bulk
+    // transfers.
+    // That is, most of the time, the schedule is going to be executing either an Isochronous transfer
+    // in our framelist, or an Interrupt transfer. The allocation in `create_structures` reflects this.
+    //
+    // Each frame has it's own Isochronous transfer Transfer Descriptor(s) that point to each other
+    // horizontally in the list. The end of these transfers then point to the Interrupt Queue Headers,
+    // in which we can attach Transfer Descriptors (related to Interrupt Transfers). These are attached
+    // to the Queue Head _vertically_. We need to ensure that these are executed every 8ms, so they are inserted
+    // at different points in the schedule (TODO: How do we do this?!?!). After the Interrupt Transfer Queue Heads,
+    // we attach the Control Queue Heads. We need two in total, one for Low Speed devices, and one for Full Speed
+    // USB devices. Finally, we attach the Bulk Transfer Queue Head.
+    // Not specified in the datasheet, however, is another Queue Head with an "inactive" Transfer Descriptor. This
+    // is to circumvent a bug in the silicon of the PIIX4's UHCI controller.
+    // https://github.com/openbsd/src/blob/master/sys/dev/usb/uhci.c#L390
+    //
+
+    m_interrupt_transfer_queue->link_next_queue_head(m_lowspeed_control_qh);
+    m_interrupt_transfer_queue->terminate_element_link_ptr();
+
+    m_lowspeed_control_qh->link_next_queue_head(m_fullspeed_control_qh);
+    m_lowspeed_control_qh->terminate_element_link_ptr();
+
+    m_fullspeed_control_qh->link_next_queue_head(m_bulk_qh);
+    m_fullspeed_control_qh->terminate_element_link_ptr();
+
+    m_bulk_qh->link_next_queue_head(m_dummy_qh);
+    m_bulk_qh->terminate_element_link_ptr();
+
+    auto piix4_td_hack = allocate_transfer_descriptor();
+    piix4_td_hack->terminate();
+    piix4_td_hack->set_max_len(0x7ff); // Null data packet
+    piix4_td_hack->set_device_address(0x7f);
+    piix4_td_hack->set_packet_id(PacketID::IN);
+    m_dummy_qh->terminate_with_stray_descriptor(piix4_td_hack);
+    m_dummy_qh->terminate_element_link_ptr();
+
+    u32* framelist = reinterpret_cast<u32*>(m_framelist->vaddr().as_ptr());
+    for (int frame = 0; frame < UHCI_NUMBER_OF_FRAMES; frame++) {
+        // Each frame pointer points to iso_td % NUM_ISO_TDS
+        framelist[frame] = m_iso_td_list.at(frame % UHCI_NUMBER_OF_ISOCHRONOUS_TDS)->paddr();
+        // klog() << PhysicalAddress(framelist[frame]);
+    }
+
+    m_interrupt_transfer_queue->print();
+    m_lowspeed_control_qh->print();
+    m_fullspeed_control_qh->print();
+    m_bulk_qh->print();
+    m_dummy_qh->print();
+}
+
+QueueHead* UHCIController::allocate_queue_head() const
+{
+    for (QueueHead* queue_head : m_free_qh_pool) {
+        if (!queue_head->in_use()) {
+            queue_head->set_in_use(true);
+#ifdef UHCI_DEBUG
+            klog() << "UHCI: Allocated a new Queue Head! Located @ " << VirtualAddress(queue_head) << "(" << PhysicalAddress(queue_head->paddr()) << ")";
+#endif
+            return queue_head;
+        }
+    }
+
+    ASSERT_NOT_REACHED(); // Let's just assert for now, this should never happen
+    return nullptr;       // Huh!? We're outta queue heads!
+}
+
+TransferDescriptor* UHCIController::allocate_transfer_descriptor() const
+{
+    for (TransferDescriptor* transfer_descriptor : m_free_td_pool) {
+        if (!transfer_descriptor->in_use()) {
+            transfer_descriptor->set_in_use(true);
+#ifdef UHCI_DEBUG
+            klog() << "UHCI: Allocated a new Transfer Descriptor! Located @ " << VirtualAddress(transfer_descriptor) << "(" << PhysicalAddress(transfer_descriptor->paddr()) << ")";
+#endif
+            return transfer_descriptor;
+        }
+    }
+
+    ASSERT_NOT_REACHED(); // Let's just assert for now, this should never happen
+    return nullptr;       // Huh?! We're outta TDs!!
+}
+
 void UHCIController::stop()
 {
     write_usbcmd(read_usbcmd() & ~UHCI_USBCMD_RUN);
@@ -134,6 +340,7 @@ void UHCIController::start()
 
 void UHCIController::handle_irq(const RegisterState&)
 {
+    dbg() << "UHCI: Interrupt happened!";
 }
 
 }
diff --git a/Kernel/Devices/USB/UHCIController.h b/Kernel/Devices/USB/UHCIController.h
index aa6715803c..7f6cf165be 100644
--- a/Kernel/Devices/USB/UHCIController.h
+++ b/Kernel/Devices/USB/UHCIController.h
@@ -1,5 +1,6 @@
 /*
  * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2020-2021, Jesse Buhagiar <jooster669@gmail.com>
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -26,14 +27,19 @@
 
 #pragma once
 
+#include <AK/NonnullOwnPtr.h>
+#include <Kernel/Devices/USB/UHCIDescriptorTypes.h>
 #include <Kernel/IO.h>
 #include <Kernel/PCI/Device.h>
+#include <Kernel/VM/ContiguousVMObject.h>
 
 namespace Kernel::USB {
 
 class UHCIController final : public PCI::Device {
+
 public:
     static void detect();
+    static UHCIController& the();
     virtual ~UHCIController() override;
 
     void reset();
@@ -49,8 +55,6 @@ private:
     u16 read_frnum() { return m_io_base.offset(0x6).in<u16>(); }
     u32 read_flbaseadd() { return m_io_base.offset(0x8).in<u32>(); }
     u8 read_sofmod() { return m_io_base.offset(0xc).in<u8>(); }
-    u16 read_portsc1() { return m_io_base.offset(0x10).in<u16>(); }
-    u16 read_portsc2() { return m_io_base.offset(0x12).in<u16>(); }
 
     void write_usbcmd(u16 value) { m_io_base.offset(0).out(value); }
     void write_usbsts(u16 value) { m_io_base.offset(0x2).out(value); }
@@ -58,13 +62,33 @@ private:
     void write_frnum(u16 value) { m_io_base.offset(0x6).out(value); }
     void write_flbaseadd(u32 value) { m_io_base.offset(0x8).out(value); }
     void write_sofmod(u8 value) { m_io_base.offset(0xc).out(value); }
-    void write_portsc1(u16 value) { m_io_base.offset(0x10).out(value); }
-    void write_portsc2(u16 value) { m_io_base.offset(0x12).out(value); }
 
     virtual void handle_irq(const RegisterState&) override;
 
+    void create_structures();
+    void setup_schedule();
+
+    QueueHead* allocate_queue_head() const;
+    TransferDescriptor* allocate_transfer_descriptor() const;
+
+private:
     IOAddress m_io_base;
-    PhysicalAddress m_framelist;
+
+    Vector<QueueHead*> m_free_qh_pool;
+    Vector<TransferDescriptor*> m_free_td_pool;
+    Vector<TransferDescriptor*> m_iso_td_list;
+    Vector<QueueHead*> m_interrupt_qh_list;
+
+    QueueHead* m_interrupt_transfer_queue;
+    QueueHead* m_lowspeed_control_qh;
+    QueueHead* m_fullspeed_control_qh;
+    QueueHead* m_bulk_qh;
+    QueueHead* m_dummy_qh; // Needed for PIIX4 hack
+
+    OwnPtr<Region> m_framelist;
+    OwnPtr<Region> m_qh_pool;
+    OwnPtr<Region> m_td_pool;
+    OwnPtr<Region> m_td_buffer_region;
 };
 
 }
diff --git a/Kernel/Devices/USB/UHCIDescriptorTypes.h b/Kernel/Devices/USB/UHCIDescriptorTypes.h
new file mode 100644
index 0000000000..f09a1dcafc
--- /dev/null
+++ b/Kernel/Devices/USB/UHCIDescriptorTypes.h
@@ -0,0 +1,286 @@
+/*
+ * Copyright (c) 2021, Jesse Buhagiar <jooster669@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <AK/OwnPtr.h>
+#include <AK/Types.h>
+
+namespace Kernel::USB {
+
+enum class PacketID : u8 {
+    IN = 0x69,
+    OUT = 0xe1,
+    SETUP = 0x2d
+};
+
+//
+// Transfer Descriptor
+//
+// Describes a single transfer event from, or to the Universal Serial Bus.
+// These are, generally, attached to Queue Heads, and then executed by the
+// USB Host Controller.
+// Must be 16-byte aligned
+//
+struct QueueHead;
+struct alignas(16) TransferDescriptor final {
+    enum class LinkPointerBits : u32 {
+        Terminate = 1,
+        QHSelect = 2,
+        DepthFlag = 4,
+    };
+
+    enum class StatusBits : u32 {
+        Reserved = (1 << 16),
+        BitStuffError = (1 << 17),
+        CRCTimeoutError = (1 << 18),
+        NAKReceived = (1 << 19),
+        BabbleDetected = (1 << 20),
+        DataBufferError = (1 << 21),
+        Stalled = (1 << 22),
+        Active = (1 << 23)
+    };
+
+    enum class ControlBits : u32 {
+        InterruptOnComplete = (1 << 24),
+        IsochronousSelect = (1 << 25),
+    };
+
+    TransferDescriptor() = delete;
+    TransferDescriptor(u32 paddr)
+        : m_paddr(paddr)
+    {
+    }
+    ~TransferDescriptor() = delete; // Prevent anything except placement new on this object
+
+    u32 link_ptr() const { return m_link_ptr; }
+    u32 paddr() const { return m_paddr; }
+    u32 status() const { return (m_control_status >> 16) & 0xff; }
+    u32 token() const { return m_token; }
+    u32 buffer_ptr() const { return m_buffer_ptr; }
+
+    bool in_use() const { return m_in_use; }
+    bool stalled() const { return m_control_status & static_cast<u32>(StatusBits::Stalled); }
+    bool last_in_chain() const { return m_link_ptr & static_cast<u32>(LinkPointerBits::Terminate); }
+    bool active() const { return m_link_ptr & static_cast<u32>(StatusBits::Active); }
+
+    void set_active()
+    {
+        u32 ctrl = m_control_status;
+        ctrl |= static_cast<u32>(StatusBits::Active);
+        m_control_status = ctrl;
+    }
+
+    void set_isochronous()
+    {
+        u32 ctrl = m_control_status;
+        ctrl |= static_cast<u32>(ControlBits::IsochronousSelect);
+        m_control_status = ctrl;
+    }
+
+    void set_control_status(u32 control_status) { m_control_status = control_status; }
+    void set_in_use(bool in_use) { m_in_use = in_use; }
+    void set_max_len(u16 max_len)
+    {
+        ASSERT(max_len < 0x500 || max_len == 0x7ff);
+        m_token |= (max_len << 21);
+    }
+
+    void set_device_address(u8 address)
+    {
+        ASSERT(address <= 0x7f);
+        m_token |= (address << 8);
+    }
+
+    void set_packet_id(PacketID pid) { m_token |= static_cast<u32>(pid); }
+    void link_queue_head(u32 qh_paddr)
+    {
+        m_link_ptr = qh_paddr;
+        m_link_ptr |= static_cast<u32>(LinkPointerBits::QHSelect);
+    }
+
+    void print()
+    {
+        // FIXME: Use dbg() or klog() when we have something working.
+        // We're using kprintf() for now because the output stands out from the rest of the text in the log
+        kprintf("UHCI: TD(%p) @ 0x%08x: link_ptr=0x%08x, status=0x%08x, token=0x%08x, buffer_ptr=0x%08x\n", this, m_paddr, m_link_ptr, m_control_status, m_token, m_buffer_ptr);
+
+        // Now let's print the flags!
+        kprintf("UHCI: TD(%p) @ 0x%08x: link_ptr=%s%s%s, status=%s%s%s%s%s%s%s\n",
+            this,
+            m_paddr,
+            (last_in_chain()) ? "T " : "",
+            (m_link_ptr & static_cast<u32>(LinkPointerBits::QHSelect)) ? "QH " : "",
+            (m_link_ptr & static_cast<u32>(LinkPointerBits::DepthFlag)) ? "Vf " : "",
+            (m_control_status & static_cast<u32>(StatusBits::BitStuffError)) ? "BITSTUFF " : "",
+            (m_control_status & static_cast<u32>(StatusBits::CRCTimeoutError)) ? "CRCTIMEOUT " : "",
+            (m_control_status & static_cast<u32>(StatusBits::NAKReceived)) ? "NAK " : "",
+            (m_control_status & static_cast<u32>(StatusBits::BabbleDetected)) ? "BABBLE " : "",
+            (m_control_status & static_cast<u32>(StatusBits::DataBufferError)) ? "DATAERR " : "",
+            (stalled()) ? "STALL " : "",
+            (active()) ? "ACTIVE " : "");
+    }
+
+    // FIXME: For the love of God, use AK SMART POINTERS PLEASE!!
+    TransferDescriptor* next_td() { return m_next_td; }
+    const TransferDescriptor* next_td() const { return m_next_td; }
+    void set_next_td(TransferDescriptor* td) { m_next_td = td; }
+
+    TransferDescriptor* prev_td() { return m_prev_td; }
+    const TransferDescriptor* prev_td() const { return m_prev_td; }
+    void set_previous_td(TransferDescriptor* td) { m_prev_td = td; }
+
+    void insert_next_transfer_descriptor(TransferDescriptor* td)
+    {
+        m_link_ptr = td->paddr();
+        td->set_previous_td(this);
+        set_next_td(td);
+
+        // Let's set some bits for the link ptr
+        m_link_ptr |= static_cast<u32>(LinkPointerBits::DepthFlag);
+    }
+
+    void terminate() { m_link_ptr |= static_cast<u32>(LinkPointerBits::Terminate); }
+
+    void set_buffer_address(u32 buffer) { m_buffer_ptr = buffer; }
+
+    // DEBUG FUNCTIONS!
+    void set_token(u32 token)
+    {
+        m_token = token;
+    }
+
+    void set_status(u32 status)
+    {
+        m_control_status = status;
+    }
+
+private:
+    u32 m_link_ptr;                // Points to another Queue Head or Transfer Descriptor
+    volatile u32 m_control_status; // Control and status bits
+    u32 m_token;                   // Contains all information required to fill in a USB Start Token
+    u32 m_buffer_ptr;              // Points to a data buffer for this transaction (i.e what we want to send or recv)
+
+    // These values will be ignored by the controller, but we can use them for configuration/bookkeeping
+    u32 m_paddr;                   // Physical address where this TransferDescriptor is located
+    TransferDescriptor* m_next_td; // Pointer to first TD
+    TransferDescriptor* m_prev_td; // Pointer to first TD
+    bool m_in_use;                 // Has this TD been allocated (and therefore in use)?
+};
+
+static_assert(sizeof(TransferDescriptor) == 32); // Transfer Descriptor is always 8 Dwords
+
+//
+// Queue Head
+//
+// Description here please!
+//
+struct alignas(16) QueueHead {
+    enum class LinkPointerBits : u32 {
+        Terminate = 1,
+        QHSelect = 2,
+    };
+
+    QueueHead() = delete;
+    QueueHead(u32 paddr)
+        : m_paddr(paddr)
+    {
+    }
+    ~QueueHead() = delete; // Prevent anything except placement new on this object
+
+    u32 link_ptr() const { return m_link_ptr; }
+    u32 element_link_ptr() const { return m_element_link_ptr; }
+    u32 paddr() const { return m_paddr; }
+    bool in_use() const { return m_in_use; }
+
+    void set_in_use(bool in_use) { m_in_use = in_use; }
+    void set_link_ptr(u32 val) { m_link_ptr = val; }
+
+    // FIXME: For the love of God, use AK SMART POINTERS PLEASE!!
+    QueueHead* next_qh() { return m_next_qh; }
+    const QueueHead* next_qh() const { return m_next_qh; }
+    void set_next_qh(QueueHead* qh) { m_next_qh = qh; }
+
+    QueueHead* prev_qh() { return m_prev_qh; }
+    const QueueHead* prev_qh() const { return m_prev_qh; }
+    void set_previous_qh(QueueHead* qh)
+    {
+        m_prev_qh = qh;
+    }
+
+    void link_next_queue_head(QueueHead* qh)
+    {
+        m_link_ptr = qh->paddr();
+        m_link_ptr |= static_cast<u32>(LinkPointerBits::QHSelect);
+        set_next_qh(qh);
+    }
+
+    void terminate_with_stray_descriptor(TransferDescriptor* td)
+    {
+        m_link_ptr = td->paddr();
+        m_link_ptr |= static_cast<u32>(LinkPointerBits::Terminate);
+    }
+
+    // TODO: Should we pass in an array or vector of TDs instead????
+    void attach_transfer_descriptor_chain(TransferDescriptor* td)
+    {
+        m_first_td = td;
+        m_element_link_ptr = td->paddr();
+    }
+
+    void terminate() { m_link_ptr |= static_cast<u32>(LinkPointerBits::Terminate); }
+
+    void terminate_element_link_ptr()
+    {
+        m_element_link_ptr = static_cast<u32>(LinkPointerBits::Terminate);
+    }
+
+    // Clean the chain of transfer descriptors
+    void clean_chain()
+    {
+        // TODO
+    }
+
+    void print()
+    {
+        kprintf("UHCI: QH(%p) @ 0x%08x: link_ptr=0x%08x, element_link_ptr=0x%08x\n", this, m_paddr, m_link_ptr, m_element_link_ptr);
+    }
+
+private:
+    u32 m_link_ptr { 0 };                  // Pointer to the next horizontal object that the controller will execute after this one
+    volatile u32 m_element_link_ptr { 0 }; // Pointer to the first data object in the queue (can be modified by hw)
+
+    // These values will be ignored by the controller, but we can use them for configuration/bookkeeping
+    // Any addresses besides `paddr` are assumed virtual and can be dereferenced
+    u32 m_paddr { 0 };                          // Physical address where this QueueHead is located
+    QueueHead* m_next_qh { nullptr };           // Next QH
+    QueueHead* m_prev_qh { nullptr };           // Previous QH
+    TransferDescriptor* m_first_td { nullptr }; // Pointer to first TD
+    bool m_in_use { false };                    // Is this QH currently in use?
+};
+
+static_assert(sizeof(QueueHead) == 32); // Queue Head is always 8 Dwords
+}