Dynamic Tree Model for USB 3.0-xHCI Host Verification Using SystemVerilog

Introduction

USB is an asymmetrical communication protocol with host, device and hub being 3 architectural components. The functionality of host controller is the most complex and hence more challenging verifying it. eXtensible Host Controller Interface (xHCI) is the USB 3.0 host controller’s hardware and driver software interface standard proposed by Intel. The scope of USB 3.0 standard includes physical layer, link layer, protocol layer and hub. Both the standard are complementary to each other. The USB3.0-xHCI host is complient to both the standards. USB 3.0-xHCI host includes 1) xHCD (software component of xHCI) 2) xHC (hardware components of xHCI) 3) root hub and 4) USB3.0 port logics. The host controller hardware (DUT) interfaces with eXtensible Host Controller Driver(xHCD) at system side and USB tree topology at port side. The verification environment requires system side agent modelling xHCD and port side agent modelling USB tree topology. The challenge in implementing the port side agent is modeling dynamic USB tree topology. The agent should have the ability to dynamically attach or detach device or hub models. The model should also support routing the USB packet from host port to target device and in the reverse direction as well. A conventional device model will have one up stream (US) serial port. A conventional hub model will have one US port and up to 4 down stream (DS) serial ports. A SystemVerilog conventional device/hub model may use “interface” (SystemVerilog key word) to encapsulate serial interface signals. It is possible to realize a specific USB tree topology by connecting device and hub interfaces using port mapping. There are 2 main issues with this approach. 1) dynamic device attachment and detachment becomes a challenge 2) All link transactions other than that of root hub link have no effect on host verification. Hence these transactions add significant overhead to simulation. In this paper we share architectural details and implementation snapshots of USB dynamic tree model using SystemVerilog, which addresses both the challenges mentioned above.

Organization

Section 2, 3 provide description about dynamic tree and more details about USB topology and packet routing. Section 4 provides host controller testbench overview and more details about port side agent. Section 5 is added for the reference about associative array in SystemVerilog. This feature is used in implementing dynamic tree. Section 6 is the core section of this paper. It pro-vides details about SystemVerilog solution to model dynamic USB tree topology. Section 7 pro-vides test setup, test scenarios and test results. Section 8 is conclusion section. Section 9 provides complete SystemVerilog code of dynamic tree model discussed in section 6. Section 10 provides complete SystemVerilog testcase including all scenarios described in section 7.

Dynamic Systems

Bus protocols like USB, PCI Express and Ethernet support hot plug options. One can add or remove the element from the network topology dynamically during the operation. The process of enumeration is used to detect the changes in the network and accordingly update database for proper network management and packet routing purpose. In USB 3.0 system xHCI specification covers the aspect of maintaining device status of active devices. The host controller needs to keep track of dynamically attached or detached devices. When a new device is attached, device initialization process starts. When a device is detached, corresponding slot is disabled using disable slot process. Typically the testbench is initially configured for the specific design requirement and remains intact through the completion of the simulation. In case of dynamic system the testbench compo-nents and their connectivity varies through the simulation as per the scenario. In the context of USB 3.0 system the verification environment should have the ability to add or remove de-vice/hub verification components dynamically during the simulation. Following sections describe an approach to achieve this requirement.

USB Topology

USB protocol supports tree topology with one host and multiple device and hub components. Host controller usually support multiple root hub ports to which either device or hub can be con-nected. In case of USB 3.0 the number of root hub ports can be extended up to 4. The hub is used to extend the number of ports beyond the number of root hub ports. Host contains only downstream (DS) ports. Hub contains one upstream (US) port and multiple DS ports. Device contains only one US port. USB topology is built by attaching US port of a component to available DS port. Each US – DS port link provides chip-chip and port-port connection.

 

Fig 1: Route String Example (Source: USB 3.0 specification)

Observations

  • Each device/hub in a topology has a unique route string
  • Packet can be routed through multi-level hub topology with route string

Sample Topology with route string

Figure 2 shows a sample USB tree topology with associated route strings for each element. Ele-ments A, C and D are hubs with each supporting 4 down stream ports. Remaining elements are devices. They can be formed by adding elements in sequence.

Figure 2: Example USB tree topology

The tree formation

While forming a tree it is important that elements are added in a valid sequence. In the above example the tree contains 6 elements. It is possible to form the tree by element A to F one by one. Element D with route string 0x00024 cannot be added prior to element C with route string 0x00004. With A added either B or C can be added next. Hence A->B->C->.. and A->C->B->…partial sequences are valid.

Sample valid sequence

  1. Add Hub A with route string 0x00000
  2. Add Device B with route string 0x000003
  3. Add Hub C with route string 0x00004
  4. Add Hub D with route string 0x00024
  5. Add Device E with route string 0x00034
  6. Add Device F with route string 0x00124

Another valid sequence to form the same tree

  1. Add Hub A with route string 0x00000
  2. Add Hub C with route string 0x00004
  3. Add Device B with route string 0x000003
  4. Add Device E with route string 0x00034
  5. Add Hub D with route string 0x00024
  6. Add device F with route string 0x00124

Example invalid sequence

  1. Add Hub A with route string 0x00000
  2. Add Device B with route string 0x000003
  3. Add Hub D with route string 0x00024 (D cannot precede C)
  4. Add Hub C with route string 0x00004
  5. Add Device E with route string 0x00034
  6. Add Device F with route string 0x00124

It is possible to form a given USB tree topology using device and hub elements if proper sequence is followed in adding each element.

The tree modification

The tree can be modified either by adding elements as explained in the the earlier section or by removing the elements. Removal of a device affects only specific device and associated hub port status. But if a hub is removed it affects all its DS connections. A removal of a hub may result in removal of multiple devices and hubs. In the example shown in Figure 2 if Hub (C) is removed then elements D, E and F are removed along with it.

Testbench Architecture

Overview

 

Figure 3: Host Controller Testbench

Figure 3 shows overview of host controller verification environment. System side agent contains xHCD model. xHCD functionality includes 1) creating transfer and command Transfer Request Blocks (TRBs) and arrange them in respective transfer rings, 2) Analyzing or consuming event TRBs produced by xHC 3) Maintaining device and input contexts. xHCD accommodates all data structures in a memory. xHC DMA accesses memory through AXI slave of system side agent. USB3.0-xHC provides CSR for software interface. It is responsible for transfering control and transfer rings produced by xHCD. It fetches TRBs of active ring sequentially from memory and passes to target port after USB packetization. It encapsulates incoming packet as event TRB and stores in respective event ring. xHCI supports up to 256 slots. To verify USB3.0-xHC features like slot initialization, enumeration and data transaction to devices beyond the number of root hub ports, dynamic USB tree model is required. This model will also help to verify complete host including USB3.0-xHCI and xHCD software. Additionally we have Test block containing scenarios for a specific test and scoreboard for end-end data checking. Focus of following sections is modelling dynamic USB tree topology as a host controller testbench component.

Host to Device communication model

 

Figure 4: USB 3.0 Communication Model (Source: USB 3.0 Specification)

Every link will have chip-chip and port-port connectivity. For the host controller the root hub port to immediate hub/device link only is of relevance. Remaining port specific connectivity be-tween any DS hub port and attached hub/device has no impact on host functionality. End-End and beyond layer for each node is logically connected to host. The above observation can be used to simplify the USB topology implementation required for USB host verification.

Identifying irrelevant logic for host verification

 

Figure 5: Identifying irrelevant links

In the above example there are 6 links L1 to L6. The relevance of chip-chip and port-port com-munication of each link is restricted to corresponding link. From host verification perspective only L1 link communication has relevance. But protocol level transactions for each node have relevance from host functionality perspective. Removal of link layer logic for the links other than L1 will have no impact on host stimulus. But the right connection between nodes is required to keep the tree topology intact. Eliminating these irrelevant links simplifies the environment.

Simplified Architecture

Figure 6: Architecture of port side agent

As observed earlier in a topology each node has a unique routing ID. Packets from host ulti-mately routed through multiple hub level to the target device using routing string. With the right routing logic it is possible to realize the behaviour of USB tree topology using the above archi-tecture. This architecture helps make the implementation simpler. P2 to P6 are protocol level connections in place of corresponding link layer connections.

The above architecture works provided it meets following requirements:
The logic should have ability to add or remove hub/device.
The logic should have ability to reject the connection to invalid route string request
The logic should have ability to route the packets to matching route string destination

Associative array in SystemVerilog

To form USB tree topology, it is required to add device or hub elements dynamically in proper sequence as explained in section “The tree formation”. To modify the tree it is required that we should be able to dynamically add/remove device/hub objects. We can consider following 3 Sys-temVerilog options for purpose of dynamic creation or deletion of an element.

Option1: Dynamic array (Refer to section 5.6 of IEEE Standard 1800-2009 SystemVerilog)
A dynamic array is any dimension of an unpacked array whose size can be set or changed at run time. The space for a dynamic array does not exist until the array is explicitly created at run time. The syntax to declare a dynamic array is as follows: data_type array_name [];
where data_type is the data type of the array elements.
Issues:

  • No control over element index
  • delete () method clears all element. Tree modification can not be implemented

Option2: Queue (Refer to section 5.14 of IEEE Standard 1800-2009 SystemVerilog) data_type queue_name [$];
Queue methods insert () and delete () can be used to add or remove an element. All queue ele-ments are automatically indexed. push_xxx() and pop_xxx() methods are used to add or remove elements from queue (Source: IEEE Standard for 1800-2009 SystemVerilog)

Option3: Associative array (Refer to section 5.9 of IEEE Standard 1800-2009 SystemVerilog) The associative array is dynamic. The syntax to declare an associative array is as follows:
data_type array_id [ index_type ];
where,
data_type: is the data type of the array elements. Can be any type allowed for fixed-size arrays.
array_id: is the name of the array being declared.
index_type: is the data-type to be used as an index or is *. If * is specified, then the array is indexed by any integral expression of arbitrary size. An index type restricts the indexing expressions to a particular type. It shall be illegal for index_type to declare a type. (Source: IEEE Standard for 1800-2009 SystemVerilog)

Selection of the dynamic array

Of 3 choices, option1: Dynamic array can be eliminated for the reasons listed as issues for the current problem. We need to make a choice between Option2: Queue and Option3: Associative array. For tree formation/modification the elements are added or removed. Each element is uniquely identified with a route string. The same information can be used to select the right element for addition or removal. In case of queue or associative array, index of the element is used to either add or remove. Usage of route string as index simplifies selection of array element for addi-tion/removal. Moreover the route strings added to the tree need not follow specific order. Asso-ciative array makes better choice since it allows addition/removal of elements based on array index. The indexes need not be incremental.

SystemVerilog Implementation

In this section we are going to elaborate the portion of the testbench used for dynamic USB tree modelling. We are going to assume the availability of following testbench components.

  • PIPE PHY model
  • LL (link layer) class with PIPE virtual port to connect to PHY model and Protocol Layer (PL) mailbox interface
  • Device/Hub classes supporting endpoint logic and PL mailbox interface

Available route string array

Initially only 0x00000 would be the available route string. If a 4 port hub is added then available route strings increase from 1 to 4. If a device is added in place of hub then the available route string count becomes zero. The count and value of available route string array changes as and when device/hub is added or removed.

Assigned route string array

The table of assigned route strings. This information is required to check whether requested route string is already present or not. In the SystemVerilog implementation “exists“ method can be used to find the assigned route strings.

 

Figure 7: Example Available & Assigned Strings

Adding a device

A method add_dev (bit [19:0] route_string) is used to dynamically add a device.

  • Check whether requested route string matches with one of the entries of available_route_string table. If not exit with error message else move to next step
  • Construct new device object with PL mailbox connections
  • Delete the requested route string from „available_route_string“ table.
  • Update the port status of parent hub

Removing a device

A method remove_dev (bit [19:0] route_string) is used to dynamically remove a device.

  • Check whether requested device with associated route string exists. If not exit with error message else move to next step
  • Delete the device with matching route string
  • Add the route string to “available_route_string“ table.
  • Update the port status of parent hub

Adding a hub

A method add_hub (bit [19:0] route_string) is used to dynamically add a hub.

  • Check whether requested route string matches with one of the entries of available_route_string table. If not exit with error message else move to next step
  • Construct new hub object with PL mailbox connections
  • Delete the requested route string from “available_route_string“ table.
  • Add route strings assoviated with new hub down stream ports to “available_route_string table“
  • Update the port status of parent hub

Removing a hub

A method remove_hub (bit [19:0] route_string) is used to dynamically remove a hub.

  • Check whether requested hub with associated route string exists. If not exit with error message else move to next step
  • Delete the hub with matching route string
  • Add the requested route string to “available_route_string“ table.
  • Delete all hubs/devices connected to the down stream ports of this hub and below
  • Delete all entries of “available_route_string“ associated with all removed hubs
  • Update the port status of parent hub

Routing requests

After the tree formation the requests from the host needs to be dispatched to the right node with matching routing string. Link layer logic provides the header and data through mailbox (mb_rx_pl) to the routing logic. The header packet contains “route string”. The routing logic extracts this string. It initiates the task of “init_flow” of device/hub having the matching route string.

Routing responses

Subsequent to dispatch of request to specific device/hub, the respective node may respond. This response should be sent to common link layer to be sent back to host. Common mailbox in the transmit direction (from dev/hub to link) can handle this. SystemVerilog mailbox has ability to handle simultanious puts from multiple sources. Hence no special logic is required to route the packets in the transmit direction.

Observations

  • With just a SV class of less than 250 lines of code it was possible to support flexible USB dynamic tree formation logic and routing logic.
  • Associative array and inbuilt methods “exists()” and “delete()” helped make the imple-mentation easier.
  • Right partition and clean interface between testbench components are critical
  • Elimination of link layer logic of links other than the one including root hub port helped simplify the overall architecture.
  • Usage of “assigned route string” and “available route strings” helped realize the tree structure keeping dynamic object creation mechanism simple.

Tests and Results

Test setup

We have used the test setup shown in the Figure 8 to verify the dynamic tree model. The entire setup is developed in SystemVerilog. We have used VCS to simulate. We wanted to prove the concept quickly. In the previous project we observed VCS to be more stable and supporting all the SV features that we wanted. Hence it was the natural choice to begin with. We have plans to extend the support to other simulators too.

Figure 8: Test Setup

Test scenarios and results

This section lists 4 sample scenarios to demonstrate the operation of dynamic tree model. Sys-temVerilog code for each scenario and corresponding log displays are provided for each scenario. Refer to Appendix-B for complete SystemVerilog testcase including all 4 scenarios. “BREQ_SET_ADDRESS” setup request is used to test the connectivity between host and de-vice/hub. BREQ_SET_ADDRESS is a setup command initiated from host. Each request follows following sequence

  1. SET_ADDRESS setup packet from host to target device/hub
  2. ACK packet from target device back to host for SETUP request
  3. STATUS packet from host to target device
  4. ACK packet from target device back to host for STATUS packet

The above transaction helps confirming the logical connectivity between host and target de-vice/hub since it involves flow of packet in either direction. Whenever tree is formed or modified disp_all () task is called to display changes in the tree ele-ments. This task lists all hubs and devices with corresponding route strings available at that moment.
Scenario1: Example tree formation and packet communication to each node Example tree shown in Figure 2 is formed using the sequence discussed in section “The tree formation”.

Portion of testcase

initial begin
…………………
$display (“————————————————————————“);
$display (“Scenario 1: Example tree formation and packet communication to each node”);
$display (“————————————————————————“);
add_component (HUB, 20’h00000);
add_component (DEV, 20’h00003);
add_component (HUB, 20’h00004);
add_component (HUB, 20’h00024);
add_component (DEV, 20’h00034);
add_component (DEV, 20’h00124);
init_setup (20’h00000, BREQ_SET_ADDRESS, 0);
init_setup (20’h00003, BREQ_SET_ADDRESS, 0);
init_setup (20’h00004, BREQ_SET_ADDRESS, 0);
init_setup (20’h00024, BREQ_SET_ADDRESS, 0);
init_setup (20’h00034, BREQ_SET_ADDRESS, 0);
init_setup (20’h00124, BREQ_SET_ADDRESS, 0);
`o_dev_agent.o_u3_hub.disp_all;
………………..
end

Portion of log file

————————————————————————
Scenario 1: Example tree formation and packet communication to each node
————————————————————————
60489000 \$unit ::\u3_hub::add_hub : Hub add with route_string 00000 is successful
60489000 \$unit ::\u3_host_port_pl::add_slot : Added slot with dev_addr 1, route_string = 0000
60489000 \$unit ::\u3_hub::add_dev : Device add with route_string 00003 is successful
60489000 \$unit ::\u3_host_port_pl::add_slot : Added slot with dev_addr 2, route_string = 0003
60489000 \$unit ::\u3_hub::add_hub : Hub add with route_string 00004 is successful
60489000 \$unit ::\u3_host_port_pl::add_slot : Added slot with dev_addr 3, route_string = 0004
60489000 \$unit ::\u3_hub::add_hub : Hub add with route_string 00024 is successful
60489000 \$unit ::\u3_host_port_pl::add_slot : Added slot with dev_addr 4, route_string = 0024
60489000 \$unit ::\u3_hub::add_dev : Device add with route_string 00034 is successful
60489000 \$unit ::\u3_host_port_pl::add_slot : Added slot with dev_addr 5, route_string = 0034
60489000 \$unit ::\u3_hub::add_dev : Device add with route_string 00124 is successful
60489000 \$unit ::\u3_host_port_pl::add_slot : Added slot with dev_addr 6, route_string = 0124
60489000 test_dev.init_setup: route_string = 00000, dev_addr = 01
60641000\$unit ::\u3_dev::exec_setup : INFO – SET ADDRESS command start
60913000 \$unit ::\u3_host_port_pl::host_pl : STATUS done
60913000 test_dev.init_setup: route_string = 00003, dev_addr = 02
61065000\$unit ::\u3_dev::exec_setup : INFO – SET ADDRESS command start
61337000 \$unit ::\u3_host_port_pl::host_pl : STATUS done
61337000 test_dev.init_setup: route_string = 00004, dev_addr = 03
61489000\$unit ::\u3_dev::exec_setup : INFO – SET ADDRESS command start
61761000 \$unit ::\u3_host_port_pl::host_pl : STATUS done
61761000 test_dev.init_setup: route_string = 00024, dev_addr = 04
61913000\$unit ::\u3_dev::exec_setup : INFO – SET ADDRESS command start
62185000 \$unit ::\u3_host_port_pl::host_pl : STATUS done
62185000 test_dev.init_setup: route_string = 00034, dev_addr = 05
62337000\$unit ::\u3_dev::exec_setup : INFO – SET ADDRESS command start
62609000 \$unit ::\u3_host_port_pl::host_pl : STATUS done
62609000 test_dev.init_setup: route_string = 00124, dev_addr = 06
62761000\$unit ::\u3_dev::exec_setup : INFO – SET ADDRESS command start
63033000 \$unit ::\u3_host_port_pl::host_pl : STATUS done
63033000 \$unit ::\u3_hub::disp_all : o_u3_hub_unit[0000000000000000]
63033000 \$unit ::\u3_hub::disp_all : o_u3_hub_unit[0000000000000004]
63033000 \$unit ::\u3_hub::disp_all : o_u3_hub_unit[0000000000000024]
63033000 \$unit ::\u3_hub::disp_all : o_u3_dev[0000000000000003]
63033000 \$unit ::\u3_hub::disp_all : o_u3_dev[0000000000000034]
63033000 \$unit ::\u3_hub::disp_all : o_u3_dev[0000000000000124]

Scenario2: Testing the response to illegal add request
This scenario demonstrates that illegal requests are not entertained. This is required to ensure the tree structure of the topology.

Portion of testcase

initial begin
………………..
$display (“————————————————————————“);
$display (“Scenario 2: Testing the response to illegal add request”);
$display (“————————————————————————“);
add_component (DEV, 20’h00114);
………………..
end

Portion of log file

————————————————————————
Scenario 2: Testing the response to illegal add request
————————————————————————
63033000 \$unit ::\u3_hub::add_dev : Error – Requested route string 00114 not available
63033000 \$unit ::\u3_host_port_pl::add_slot : Added slot with dev_addr 7, route_string = 0114

Scenario3: Removing a Device
In this scenario device with route string 20’h00034 is removed. To test whether this element is properly removed a transaction is initiated to this route string.

Portion of testcase

initial begin
………………..
$display (“————————————————————————“);
$display (“Scenario 3: Removing a device”);
$display (“————————————————————————“);
`remove_dev (20’h00034);
init_setup (20’h00024, BREQ_SET_ADDRESS, 0);
init_setup (20’h00034, BREQ_SET_ADDRESS, 0);
`o_dev_agent.o_u3_hub.disp_all;
………………..
end
————————————————————————
Scenario 3: Removing a device
————————————————————————
63033000 \$unit ::\u3_hub::remove_dev : Device remove with route_string 00034 is successful
63033000 test_dev.init_setup: route_string = 00024, dev_addr = 04
63185000\$unit ::\u3_dev::exec_setup : INFO – SET ADDRESS command start
63457000 \$unit ::\u3_host_port_pl::host_pl : STATUS done
63457000 test_dev.init_setup: route_string = 00034, dev_addr = 05
63609000 \$unit ::\u3_hub::run : Error – Requested route string 00034 not available
63609000 \$unit ::\u3_hub::disp_all : o_u3_hub_unit[0000000000000000]
63609000 \$unit ::\u3_hub::disp_all : o_u3_hub_unit[0000000000000004]
63609000 \$unit ::\u3_hub::disp_all : o_u3_hub_unit[0000000000000024]
63609000 \$unit ::\u3_hub::disp_all : o_u3_dev[0000000000000003]
63609000 \$unit ::\u3_hub::disp_all : o_u3_dev[0000000000000124]
64457000 \$unit ::\u3_host_port_pl::host_pl : ACK not received for SETUP; Aborting control flow
64457000 \$unit ::\u3_hub::disp_all : o_u3_hub_unit[0000000000000000]
64457000 \$unit ::\u3_hub::disp_all : o_u3_hub_unit[0000000000000004]
64457000 \$unit ::\u3_hub::disp_all : o_u3_hub_unit[0000000000000024]
64457000 \$unit ::\u3_hub::disp_all : o_u3_dev[0000000000000003]
64457000 \$unit ::\u3_hub::disp_all : o_u3_dev[0000000000000124]

Scenario4: Removing a Hub

Portion of testcase

initial begin
………………..
$display (“————————————————————————“);
$display (“Scenario 4: Removing a Hub”);
$display (“————————————————————————“);
`remove_hub (20’h00004);
init_setup (20’h00024, BREQ_SET_ADDRESS, 0);
init_setup (20’h00003, BREQ_SET_ADDRESS, 0);
`o_dev_agent.o_u3_hub.disp_all;
………………..
end

Portion of log file

————————————————————————
Scenario 4: Removing a Hub
————————————————————————
64457000 \$unit ::\u3_hub::remove_hub : Hub remove with route_string 00004 is successful
64457000 test_dev.init_setup: route_string = 00024, dev_addr = 04
64569000 \$unit ::\u3_hub::run : Error – Requested route string 00024 not available
64569000 \$unit ::\u3_hub::disp_all : o_u3_hub_unit[0000000000000000]
64569000 \$unit ::\u3_hub::disp_all : o_u3_dev[0000000000000003]
65457000 \$unit ::\u3_host_port_pl::host_pl : ACK not received for SETUP; Aborting control flow
65457000 test_dev.init_setup: route_string = 00003, dev_addr = 02
65569000\$unit ::\u3_dev::exec_setup : INFO – SET ADDRESS command start
65841000 \$unit ::\u3_host_port_pl::host_pl : STATUS done
65841000 \$unit ::\u3_hub::disp_all : o_u3_hub_unit[0000000000000000]
65841000 \$unit ::\u3_hub::disp_all : o_u3_dev[0000000000000003]

Conclusions

The SystemVerilog solution presented here can help realize any valid USB tree topology. The number of valid of tree topologies is very high. Random tree generation might help realize certain corner cases. We can randomize the tree formation by randomizing 1) number of tree elements, 2) selection of route strings from the table of “available route strings”. We can also randomly remove elements. This feature will help take this solution to the next level. This solution supports configuring the number of hub ports globally using HUB_PORT_NUM parameter. We could extend configurability beyond. By passing “number_of_ports” as an argu-ment to “add_hub ()” task each hub can be independently configured.

To implement simplified architecture supporting dynamic tree modelling as explained in section “Simplified architecture” it is necessary to have clean partition between link layer and protocol layer classes. We had to move Link Management Packet (LMP) related logic from protocol layer to link layer. This restructuring helped us to reuse the entire link layer at the host side (used in test setup). It means the complex testbench component developed for host controller testbech can be reused for device controller testbench as well. Similarly we found the use of packetiza-tion/depacketization class at multiple places.

There are various network systems containing multiple elements. Each network supports specific topology. Some of the standard topologies are star, tree, ring, daisy chain, etc. Some protocols support only static networks while others support dynamic topology. USB supports dynamic tree topology. It lets user add or remove element dynamically without disturbing connectivity with remaining elements. Static network can be considered as a special case of a dynamic network, where topology formation is done once and it is not modified. This solution may help modelling dynamic topologies other than USB tree topology.

Acknowledgements

My thanks to my friends/colleagues Aravinda Holla and Uma Mahesh who read every line of this paper and provided inputs especially during initial phases. Thanks to Dinesh Tyagi (CEO) for his support and encouragement. Without his suggestion I would not have started writing this paper. Finally my special thanks to Will Chen from Synopsys. His review comments were critical for shaping of this paper.

Appendix A: Dynamic tree model

//========================================================
// INNOVATIVE LOGIC Proprietary and Confidential
// Copyright (c) INNOVATIVE LOGIC 2010
// All Rights Reserved
//========================================================
class u3_hub extends hc_base;
u3_hub_unit o_u3_hub_unit[*];
u3_dev o_u3_dev[*];
u3_pl_pkt_c o_u3_pl_pkt_c;

mailbox mb_rx_pl[5];
mailbox mb_tx_req[4];
mailbox mb_tx_ep[16];
rd_wr_mailbox lc_rd_wr_mailbox;

int available_route_string_index;
bit [19:0] available_route_string [*];

/////////////////////////////////////////////////////
// Function new
/////////////////////////////////////////////////////
function new(mailbox in_mb_rx_pl[5],
mailbox in_mb_tx_req[4],
mailbox in_mb_tx_ep[16]);
int i;
o_u3_pl_pkt_c = new ();
mb_rx_pl = in_mb_rx_pl;
mb_tx_req = in_mb_tx_req;
mb_tx_ep = in_mb_tx_ep;
available_route_string[0] = 1;
endfunction
/////////////////////////////////////////////////////
// Method to add new device
/////////////////////////////////////////////////////
function void add_dev (bit [19:0] route_string);
if (!available_route_string.exists (route_string)) begin
$display ($time, ” %M: Error – Requested route string %h not available”, route_string);
end
else begin
o_u3_dev[route_string] = new (mb_tx_req, mb_tx_ep, lc_rd_wr_mailbox); //create new device instance
available_route_string.delete (route_string); //delete available_route_string table entry
init_hub_port (ADD, route_string); // Update the upstream u3_hub port status
$display (“Addition of device with route_string %h is successful”, route_string);
end
endfunction
/////////////////////////////////////////////////////
// Method to remove device
/////////////////////////////////////////////////////
function void remove_dev (bit [19:0] route_string);
if (!o_u3_dev.exists (route_string)) begin
$display ($time, ” %M: Error – Requested route string %h not available”, route_string);
end
else begin
o_u3_dev.delete (route_string); //Delete device instance
available_route_string[route_string] = 1; // Add entry in open rs table
init_hub_port (REMOVE, route_string); // Update the upstream u3_hub port status
end
endfunction
/////////////////////////////////////////////////////
// Method to add new HUB
/////////////////////////////////////////////////////
function void add_hub (bit [19:0] route_string);
bit [4:0] next_index;
bit [19:0] i;
bit [19:0] new_route_string;
if (!available_route_string.exists(route_string)) begin
$display ($time, ” %M: Error – Requested route string %h not available”, route_string);
end
else begin
o_u3_hub_unit[route_string] = new (); //create new u3_hub instance
available_route_string.delete (route_string); //delete available_route_string table entry
next_index = get_hub_depth (route_string)*4;
new_route_string = route_string;
for (i=1; i<=HUB_PORT_NUM; i++) begin
new_route_string = route_string | (i << next_index);
available_route_string[new_route_string] = 1;
end
init_hub_port (ADD, route_string);// Update the upstream u3_hub port status
$display (“Addition of HUB with route_string %h is successful”, route_string);
end
endfunction
/////////////////////////////////////////////////////
// Method to remove HUB
/////////////////////////////////////////////////////
function void remove_hub (bit [19:0] route_string);
bit [19:0] i;
bit [19:0] mask;
bit [4:0] cur_index;
if (!o_u3_hub_unit.exists (route_string)) begin
$display ($time, ” %M: Error – Requested u3_hub route string %h not available for removal”, route_string);
end
else begin
o_u3_hub_unit.delete (route_string); //Delete device instance
available_route_string[route_string] = 1; // Add entry in open rs table
init_hub_port (REMOVE, route_string); // Update the upstreame u3_hub port status
mask = 0;
cur_index = get_hub_depth (route_string) * 4;
for (i=0; i foreach (o_u3_dev[i]) begin
if ((i & mask) == route_string) o_u3_dev.delete(i);
end
foreach (o_u3_hub_unit[i]) begin
if ((i & mask) == route_string) o_u3_hub_unit.delete(i);
end
foreach (available_route_string[i]) begin
if ((i & mask) == route_string) available_route_string.delete(i);
end
end
endfunction
/////////////////////////////////////////////////////
// Method to get HUB depth
/////////////////////////////////////////////////////
function bit [2:0] get_hub_depth (bit [19:0] route_string);
if (route_string[3:0] == 0) get_hub_depth = 0;
else if (route_string[7:4] == 0) get_hub_depth = 1;
else if (route_string[11:8] == 0) get_hub_depth = 2;
else if (route_string[15:12] == 0) get_hub_depth = 3;
else if (route_string[19:16] == 0) get_hub_depth = 4;
else get_hub_depth = 5;
endfunction
/////////////////////////////////////////////////////
// Method to initialize u3_hub port where new device is attached
/////////////////////////////////////////////////////
function void init_hub_port (bit con_type, bit [19:0] route_string);
bit [19:0] parent_route_string;
bit [3:0] child_port;
get_parent_info (route_string, parent_route_string, child_port);
if (con_type == ADD) begin
o_u3_hub_unit[parent_route_string].o_u3_hub_port[child_port].CCS = 1;
o_u3_hub_unit[parent_route_string].o_u3_hub_port[child_port].PED = 1;
end
if (con_type == REMOVE) begin
o_u3_hub_unit[parent_route_string].o_u3_hub_port[child_port].CCS = 0;
o_u3_hub_unit[parent_route_string].o_u3_hub_port[child_port].PED = 0;
end
endfunction
/////////////////////////////////////////////////////
// Method to get parent u3_hub route string
/////////////////////////////////////////////////////
task get_parent_info (bit [19:0] route_string,
output bit [19:0] parent_route_string,
output bit [3:0] child_port);
bit [19:0] cur_route_string;
int i;
cur_route_string = route_string;
for (i=0; i<5 && (cur_route_string[19:16]==0); i++) begin
cur_route_string = cur_route_string << 4;
end
child_port = cur_route_string[19:16];
cur_route_string = cur_route_string << 4;
cur_route_string = cur_route_string >> (4 * (i+1));
parent_route_string = cur_route_string;
endtask
/////////////////////////////////////////////////////
// Task run
/////////////////////////////////////////////////////
task run;
bit [3:0][31:0] hdr;
bit [19:0] route_string;
bit [63:0] setup_command;
bit [31:0] cur_word;
int i;
forever begin
for (i=0; i<4; i++) begin
mb_rx_pl[i].get (cur_word);
hdr[i] = cur_word;
end
o_u3_pl_pkt_c.unpack (hdr);
route_string = o_u3_pl_pkt_c.RouteString;
mb_rx_pl[4].get (setup_command);
if (o_u3_dev.exists (route_string))
o_u3_dev[route_string].init_flow (hdr, setup_command);
else if (o_u3_hub_unit.exists(route_string))
o_u3_hub_unit[route_string].o_u3_dev.init_flow (hdr, setup_command);
else begin //`disp_log (LOG_ERR, “Requested route string not available”, 0, 0);
$display ($time, ” %M: Error – Requested route string %h not available”, route_string);
disp_all ();
end
end
endtask
/////////////////////////////////////////////////////
// Task display list of attached devices/hubs
/////////////////////////////////////////////////////
task disp_all;
foreach (o_u3_dev[i]) begin
$display ($time, ” %M: o_u3_dev[%h]”, i);
end
foreach (o_u3_hub_unit[i]) begin
$display ($time, ” %M: o_u3_hub_unit[%h]”, i);
end
endtask
endclass

Appendix B: Sample test

//======================================================
// INNOVATIVE LOGIC Proprietary and Confidential
// Copyright (c) INNOVATIVE LOGIC 2010
// All Rights Reserved
//======================================================
`include “def_testcase.sv”
module test_dynamic_tree (
);

parameter DEV = 0;
parameter HUB = 1;

import hc_pkg::*;

initial begin
@(`host_done_adv);
$display (“————————————————————————“);
$display (“Scenario 1: Example tree formation and packet communication to each node”);
$display (“————————————————————————“);
add_component (HUB, 20’h00000);
add_component (DEV, 20’h00003);
add_component (HUB, 20’h00004);
add_component (HUB, 20’h00024);
add_component (DEV, 20’h00034);
add_component (DEV, 20’h00124);
init_setup (20’h00000, BREQ_SET_ADDRESS, 0);
init_setup (20’h00003, BREQ_SET_ADDRESS, 0);
init_setup (20’h00004, BREQ_SET_ADDRESS, 0);
init_setup (20’h00024, BREQ_SET_ADDRESS, 0);
init_setup (20’h00034, BREQ_SET_ADDRESS, 0);
init_setup (20’h00124, BREQ_SET_ADDRESS, 0);
`o_dev_agent.o_u3_hub.disp_all;

$display (“————————————————————————“);
$display (“Scenario 2: Testing the response to illegal add request”);
$display (“————————————————————————“);
add_component (DEV, 20’h00114);

$display (“————————————————————————“);
$display (“Scenario 3: Removing a device”);
$display (“————————————————————————“);
`remove_dev (20’h00034);
init_setup (20’h00024, BREQ_SET_ADDRESS, 0);
init_setup (20’h00034, BREQ_SET_ADDRESS, 0);
`o_dev_agent.o_u3_hub.disp_all;

$display (“————————————————————————“);
$display (“Scenario 3: Removing a Hub”);
$display (“————————————————————————“);
`remove_hub (20’h00004);
init_setup (20’h00024, BREQ_SET_ADDRESS, 0);
init_setup (20’h00003, BREQ_SET_ADDRESS, 0);
`o_dev_agent.o_u3_hub.disp_all;
$finish;
end

function bit [6:0] add_component (bit hub, bit [19:0] route_string);
bit [6:0] dev_addr;
dev_addr = `o_u3_host_port_pl.cur_dev_addr;
if (hub) `add_hub (route_string);
else `add_dev (route_string);
`add_slot (route_string);
add_component = dev_addr;
endfunction

task init_setup (bit [19:0] route_string, bit [7:0] b_request, bit [7:0] desc_type);
bit [6:0] dev_addr;
`mb_req.put (REQ_SETUP);
dev_addr = `get_dev_addr (route_string);
$display ($time, ” %M: route_string = %h, dev_addr = %h”, route_string, dev_addr);
`o_req_setup.dev_addr = dev_addr;
`o_req_setup.epnum = 0;
`o_req_setup.b_request = b_request;
case (b_request)
BREQ_SET_ADDRESS : begin
`o_req_setup.w_value0 = 1;
`o_req_setup.w_value1 = 0;
end
BREQ_GET_DESC : begin
`o_req_setup.w_value0 = 0;
case (desc_type)
DESC_TYPE_DEV : `o_req_setup.w_value1 = 1;
DESC_TYPE_CONFIG : `o_req_setup.w_value1 = 0;
endcase
`o_req_setup.w_value1 = 1;
end
BREQ_SET_CONFIG : begin
`o_req_setup.w_value0 = 0;
`o_req_setup.w_value1 = 2;
end
endcase
`mb_req_setup.put (`o_req_setup);
@(`o_u3_host_port_pl.done_status);
endtask

endmodule

References

    1. eXtensible Host Controller Interface for Universal Serial Bus.
    2. Universal Serial Bus 3.0 Specification.
    3. IEEE Standard 1800-2009 SystemVerilog

Feedback

If you have any suggestion/feedback please email it to feedback@inno-logic.com