[PATCH 0/4] usb: xhci: improve trb_in_td()

[PATCH 0/4] usb: xhci: improve trb_in_td()

[Niklas Neronin]

Function td_in_trd() checks whether a DMA address is within the TDs
boundaries. This patch set aims to simplify and improve trb_in_td().

Additionally, the rework will enable trb_in_td() (with renaming and minor
modifications) to also check whether a DMA address is in a ring queue.
This will be utilized in the upcoming handle_tx_event() rework.

Example of a Ring Structure:
The example segment ring is composed of three segments (A, B, C), each
containing three TRBs (1, 2, 3). Any segment can serve as the start or
end segment, and any TRB within the start segment can be the start TRB,
and vice versa.

      +---+   +---+   +---+
C --> | A |-->| B |-->| C |--> A
      +---+   +---+   +---+
        |       |       |
      +---+   +---+   +---+
      | 1 |   | 1 |   | 1 |
      | 2 |   | 2 |   | 2 |
      | 3 |   | 3 |   | 3 |
      +---+   +---+   +---+

Niklas Neronin (4):
  usb: xhci: refactor trb_in_td() to be static
  usb: xhci: move debug capabilities from trb_in_td() to
    handle_tx_event()
  usb: xhci: rework and simplify trb_in_td()
  usb: xhci: modify trb_in_td() to be more modular

 drivers/usb/host/xhci-ring.c | 143 ++++++++++++++++++-----------------
 drivers/usb/host/xhci.h      |   2 -
 2 files changed, 72 insertions(+), 73 deletions(-)

-- 
2.47.2

[PATCH 1/4] usb: xhci: refactor trb_in_td() to be static

[Niklas Neronin]

Relocate trb_in_td() and marks it as static, as it's exclusively utilized
in xhci-ring.c. This adjustment lays the groundwork for future rework of
the function.

The function's logic remains unchanged; only its access specifier is
altered to static and a redundant "else" is removed on line 325
(due to checkpatch.pl complaining).

Signed-off-by: Niklas Neronin <niklas.neronin@linux.intel.com>
---
 drivers/usb/host/xhci-ring.c | 122 +++++++++++++++++------------------
 drivers/usb/host/xhci.h      |   2 -
 2 files changed, 61 insertions(+), 63 deletions(-)

diff --git a/drivers/usb/host/xhci-ring.c b/drivers/usb/host/xhci-ring.c
index 965bffce301e..467a3abf8f53 100644
--- a/drivers/usb/host/xhci-ring.c
+++ b/drivers/usb/host/xhci-ring.c
@@ -277,6 +277,67 @@ static void inc_enq(struct xhci_hcd *xhci, struct xhci_ring *ring,
 	}
 }
 
+/*
+ * If the suspect DMA address is a TRB in this TD, this function returns that
+ * TRB's segment. Otherwise it returns 0.
+ */
+static struct xhci_segment *trb_in_td(struct xhci_hcd *xhci, struct xhci_td *td,
+				      dma_addr_t suspect_dma, bool debug)
+{
+	dma_addr_t start_dma;
+	dma_addr_t end_seg_dma;
+	dma_addr_t end_trb_dma;
+	struct xhci_segment *cur_seg;
+
+	start_dma = xhci_trb_virt_to_dma(td->start_seg, td->start_trb);
+	cur_seg = td->start_seg;
+
+	do {
+		if (start_dma == 0)
+			return NULL;
+		/* We may get an event for a Link TRB in the middle of a TD */
+		end_seg_dma = xhci_trb_virt_to_dma(cur_seg,
+				&cur_seg->trbs[TRBS_PER_SEGMENT - 1]);
+		/* If the end TRB isn't in this segment, this is set to 0 */
+		end_trb_dma = xhci_trb_virt_to_dma(cur_seg, td->end_trb);
+
+		if (debug)
+			xhci_warn(xhci,
+				"Looking for event-dma %016llx trb-start %016llx trb-end %016llx seg-start %016llx seg-end %016llx\n",
+				(unsigned long long)suspect_dma,
+				(unsigned long long)start_dma,
+				(unsigned long long)end_trb_dma,
+				(unsigned long long)cur_seg->dma,
+				(unsigned long long)end_seg_dma);
+
+		if (end_trb_dma > 0) {
+			/* The end TRB is in this segment, so suspect should be here */
+			if (start_dma <= end_trb_dma) {
+				if (suspect_dma >= start_dma && suspect_dma <= end_trb_dma)
+					return cur_seg;
+			} else {
+				/* Case for one segment with
+				 * a TD wrapped around to the top
+				 */
+				if ((suspect_dma >= start_dma &&
+							suspect_dma <= end_seg_dma) ||
+						(suspect_dma >= cur_seg->dma &&
+						 suspect_dma <= end_trb_dma))
+					return cur_seg;
+			}
+			return NULL;
+		}
+		/* Might still be somewhere in this segment */
+		if (suspect_dma >= start_dma && suspect_dma <= end_seg_dma)
+			return cur_seg;
+
+		cur_seg = cur_seg->next;
+		start_dma = xhci_trb_virt_to_dma(cur_seg, &cur_seg->trbs[0]);
+	} while (cur_seg != td->start_seg);
+
+	return NULL;
+}
+
 /*
  * Return number of free normal TRBs from enqueue to dequeue pointer on ring.
  * Not counting an assumed link TRB at end of each TRBS_PER_SEGMENT sized segment.
@@ -2116,67 +2177,6 @@ static void handle_port_status(struct xhci_hcd *xhci, union xhci_trb *event)
 	spin_lock(&xhci->lock);
 }
 
-/*
- * If the suspect DMA address is a TRB in this TD, this function returns that
- * TRB's segment. Otherwise it returns 0.
- */
-struct xhci_segment *trb_in_td(struct xhci_hcd *xhci, struct xhci_td *td, dma_addr_t suspect_dma,
-			       bool debug)
-{
-	dma_addr_t start_dma;
-	dma_addr_t end_seg_dma;
-	dma_addr_t end_trb_dma;
-	struct xhci_segment *cur_seg;
-
-	start_dma = xhci_trb_virt_to_dma(td->start_seg, td->start_trb);
-	cur_seg = td->start_seg;
-
-	do {
-		if (start_dma == 0)
-			return NULL;
-		/* We may get an event for a Link TRB in the middle of a TD */
-		end_seg_dma = xhci_trb_virt_to_dma(cur_seg,
-				&cur_seg->trbs[TRBS_PER_SEGMENT - 1]);
-		/* If the end TRB isn't in this segment, this is set to 0 */
-		end_trb_dma = xhci_trb_virt_to_dma(cur_seg, td->end_trb);
-
-		if (debug)
-			xhci_warn(xhci,
-				"Looking for event-dma %016llx trb-start %016llx trb-end %016llx seg-start %016llx seg-end %016llx\n",
-				(unsigned long long)suspect_dma,
-				(unsigned long long)start_dma,
-				(unsigned long long)end_trb_dma,
-				(unsigned long long)cur_seg->dma,
-				(unsigned long long)end_seg_dma);
-
-		if (end_trb_dma > 0) {
-			/* The end TRB is in this segment, so suspect should be here */
-			if (start_dma <= end_trb_dma) {
-				if (suspect_dma >= start_dma && suspect_dma <= end_trb_dma)
-					return cur_seg;
-			} else {
-				/* Case for one segment with
-				 * a TD wrapped around to the top
-				 */
-				if ((suspect_dma >= start_dma &&
-							suspect_dma <= end_seg_dma) ||
-						(suspect_dma >= cur_seg->dma &&
-						 suspect_dma <= end_trb_dma))
-					return cur_seg;
-			}
-			return NULL;
-		} else {
-			/* Might still be somewhere in this segment */
-			if (suspect_dma >= start_dma && suspect_dma <= end_seg_dma)
-				return cur_seg;
-		}
-		cur_seg = cur_seg->next;
-		start_dma = xhci_trb_virt_to_dma(cur_seg, &cur_seg->trbs[0]);
-	} while (cur_seg != td->start_seg);
-
-	return NULL;
-}
-
 static void xhci_clear_hub_tt_buffer(struct xhci_hcd *xhci, struct xhci_td *td,
 		struct xhci_virt_ep *ep)
 {
diff --git a/drivers/usb/host/xhci.h b/drivers/usb/host/xhci.h
index 8c164340a2c3..d66ad9bd7432 100644
--- a/drivers/usb/host/xhci.h
+++ b/drivers/usb/host/xhci.h
@@ -1884,8 +1884,6 @@ int xhci_set_interrupter_moderation(struct xhci_interrupter *ir,
 
 /* xHCI ring, segment, TRB, and TD functions */
 dma_addr_t xhci_trb_virt_to_dma(struct xhci_segment *seg, union xhci_trb *trb);
-struct xhci_segment *trb_in_td(struct xhci_hcd *xhci, struct xhci_td *td,
-			       dma_addr_t suspect_dma, bool debug);
 int xhci_is_vendor_info_code(struct xhci_hcd *xhci, unsigned int trb_comp_code);
 void xhci_ring_cmd_db(struct xhci_hcd *xhci);
 int xhci_queue_slot_control(struct xhci_hcd *xhci, struct xhci_command *cmd,
-- 
2.47.2

[PATCH 2/4] usb: xhci: move debug capabilities from trb_in_td() to handle_tx_event()

[Niklas Neronin]

Function trb_in_td() currently includes debug capabilities that are
triggered when its debug argument is set to true. The only consumer of
these debug capabilities is handle_tx_event(), which calls trb_in_td()
twice, once for its primary functionality and a second time solely for
debugging purposes if the first call returns 'NULL'.

This approach is inefficient and can lead to confusion, as trb_in_td()
executes the same code with identical arguments twice, differing only in
the debug output during the second execution.

To enhance clarity and efficiency, move the debug capabilities out of
trb_in_td() and integrates them directly into handle_tx_event().
This change reduces the argument count of trb_in_td() and ensures that
debug steps are executed only when necessary, streamlining the function's
operation.

Signed-off-by: Niklas Neronin <niklas.neronin@linux.intel.com>
---
 drivers/usb/host/xhci-ring.c | 40 +++++++++++++++++-------------------
 1 file changed, 19 insertions(+), 21 deletions(-)

diff --git a/drivers/usb/host/xhci-ring.c b/drivers/usb/host/xhci-ring.c
index 467a3abf8f53..a69972cc400c 100644
--- a/drivers/usb/host/xhci-ring.c
+++ b/drivers/usb/host/xhci-ring.c
@@ -281,8 +281,7 @@ static void inc_enq(struct xhci_hcd *xhci, struct xhci_ring *ring,
  * If the suspect DMA address is a TRB in this TD, this function returns that
  * TRB's segment. Otherwise it returns 0.
  */
-static struct xhci_segment *trb_in_td(struct xhci_hcd *xhci, struct xhci_td *td,
-				      dma_addr_t suspect_dma, bool debug)
+static struct xhci_segment *trb_in_td(struct xhci_td *td, dma_addr_t suspect_dma)
 {
 	dma_addr_t start_dma;
 	dma_addr_t end_seg_dma;
@@ -301,15 +300,6 @@ static struct xhci_segment *trb_in_td(struct xhci_hcd *xhci, struct xhci_td *td,
 		/* If the end TRB isn't in this segment, this is set to 0 */
 		end_trb_dma = xhci_trb_virt_to_dma(cur_seg, td->end_trb);
 
-		if (debug)
-			xhci_warn(xhci,
-				"Looking for event-dma %016llx trb-start %016llx trb-end %016llx seg-start %016llx seg-end %016llx\n",
-				(unsigned long long)suspect_dma,
-				(unsigned long long)start_dma,
-				(unsigned long long)end_trb_dma,
-				(unsigned long long)cur_seg->dma,
-				(unsigned long long)end_seg_dma);
-
 		if (end_trb_dma > 0) {
 			/* The end TRB is in this segment, so suspect should be here */
 			if (start_dma <= end_trb_dma) {
@@ -1075,7 +1065,7 @@ static int xhci_invalidate_cancelled_tds(struct xhci_virt_ep *ep)
 					 td->urb->stream_id);
 		hw_deq &= ~0xf;
 
-		if (td->cancel_status == TD_HALTED || trb_in_td(xhci, td, hw_deq, false)) {
+		if (td->cancel_status == TD_HALTED || trb_in_td(td, hw_deq)) {
 			switch (td->cancel_status) {
 			case TD_CLEARED: /* TD is already no-op */
 			case TD_CLEARING_CACHE: /* set TR deq command already queued */
@@ -1165,7 +1155,7 @@ static struct xhci_td *find_halted_td(struct xhci_virt_ep *ep)
 		hw_deq = xhci_get_hw_deq(ep->xhci, ep->vdev, ep->ep_index, 0);
 		hw_deq &= ~0xf;
 		td = list_first_entry(&ep->ring->td_list, struct xhci_td, td_list);
-		if (trb_in_td(ep->xhci, td, hw_deq, false))
+		if (trb_in_td(td, hw_deq))
 			return td;
 	}
 	return NULL;
@@ -2832,7 +2822,7 @@ static int handle_tx_event(struct xhci_hcd *xhci,
 	 */
 	td = list_first_entry_or_null(&ep_ring->td_list, struct xhci_td, td_list);
 
-	if (td && td->error_mid_td && !trb_in_td(xhci, td, ep_trb_dma, false)) {
+	if (td && td->error_mid_td && !trb_in_td(td, ep_trb_dma)) {
 		xhci_dbg(xhci, "Missing TD completion event after mid TD error\n");
 		xhci_dequeue_td(xhci, td, ep_ring, td->status);
 	}
@@ -2860,7 +2850,7 @@ static int handle_tx_event(struct xhci_hcd *xhci,
 				      td_list);
 
 		/* Is this a TRB in the currently executing TD? */
-		ep_seg = trb_in_td(xhci, td, ep_trb_dma, false);
+		ep_seg = trb_in_td(td, ep_trb_dma);
 
 		if (!ep_seg) {
 
@@ -2899,12 +2889,7 @@ static int handle_tx_event(struct xhci_hcd *xhci,
 			}
 
 			/* HC is busted, give up! */
-			xhci_err(xhci,
-				 "ERROR Transfer event TRB DMA ptr not part of current TD ep_index %d comp_code %u\n",
-				 ep_index, trb_comp_code);
-			trb_in_td(xhci, td, ep_trb_dma, true);
-
-			return -ESHUTDOWN;
+			goto debug_finding_td;
 		}
 
 		if (ep->skip) {
@@ -2957,6 +2942,19 @@ static int handle_tx_event(struct xhci_hcd *xhci,
 
 	return 0;
 
+debug_finding_td:
+	xhci_err(xhci, "Transfer event %u ep %d dma %016llx not part of current TD start %016llx end %016llx\n",
+		 trb_comp_code, ep_index, (unsigned long long)ep_trb_dma,
+		 (unsigned long long)xhci_trb_virt_to_dma(td->start_seg, td->start_trb),
+		 (unsigned long long)xhci_trb_virt_to_dma(td->end_seg, td->end_trb));
+
+	xhci_for_each_ring_seg(ep_ring->first_seg, ep_seg) {
+		xhci_warn(xhci, "Ring seg %u trb start %016llx end %016llx\n", ep_seg->num,
+			  (unsigned long long)ep_seg->dma,
+			  (unsigned long long)(ep_seg->dma + TRB_SEGMENT_SIZE));
+	}
+	return -ESHUTDOWN;
+
 err_out:
 	xhci_err(xhci, "@%016llx %08x %08x %08x %08x\n",
 		 (unsigned long long) xhci_trb_virt_to_dma(
-- 
2.47.2

Re: [PATCH 2/4] usb: xhci: move debug capabilities from trb_in_td() to handle_tx_event()

[Michał Pecio]

> +debug_finding_td:
> +	xhci_err(xhci, "Transfer event %u ep %d dma %016llx not part of current TD start %016llx end %016llx\n",
> +		 trb_comp_code, ep_index, (unsigned long long)ep_trb_dma,
> +		 (unsigned long long)xhci_trb_virt_to_dma(td->start_seg, td->start_trb),
> +		 (unsigned long long)xhci_trb_virt_to_dma(td->end_seg, td->end_trb)); +
> +	xhci_for_each_ring_seg(ep_ring->first_seg, ep_seg) {
> +		xhci_warn(xhci, "Ring seg %u trb start %016llx end %016llx\n", ep_seg->num,
> +			  (unsigned long long)ep_seg->dma,
> +			  (unsigned long long)(ep_seg->dma + TRB_SEGMENT_SIZE));
> +	}
> +	return -ESHUTDOWN;

Cleaning up trb_in_td() is obviously the right thing to do, but one
thing I always disliked about this message is how long and verbose it
is. Not sure if dumping all ring segments is useful here, seg->dma can
generally be deduced by looking at the DMA pointers involved.

As far as improvements go, IMO it would be much more useful to decode
those pointers into seg-number/trb-index pairs. I wrote a PoC and the
result is quite encouraging, I may submit it if there is interest.

Regards,
Michal

Re: [PATCH 2/4] usb: xhci: move debug capabilities from trb_in_td() to handle_tx_event()

[Neronin, Niklas]

On 05/03/2025 10.46, Michał Pecio wrote:
>> +debug_finding_td:
>> +	xhci_err(xhci, "Transfer event %u ep %d dma %016llx not part of current TD start %016llx end %016llx\n",
>> +		 trb_comp_code, ep_index, (unsigned long long)ep_trb_dma,
>> +		 (unsigned long long)xhci_trb_virt_to_dma(td->start_seg, td->start_trb),
>> +		 (unsigned long long)xhci_trb_virt_to_dma(td->end_seg, td->end_trb)); +
>> +	xhci_for_each_ring_seg(ep_ring->first_seg, ep_seg) {
>> +		xhci_warn(xhci, "Ring seg %u trb start %016llx end %016llx\n", ep_seg->num,
>> +			  (unsigned long long)ep_seg->dma,
>> +			  (unsigned long long)(ep_seg->dma + TRB_SEGMENT_SIZE));
>> +	}
>> +	return -ESHUTDOWN;
> 
> Cleaning up trb_in_td() is obviously the right thing to do, but one
> thing I always disliked about this message is how long and verbose it
> is. Not sure if dumping all ring segments is useful here, seg->dma can
> generally be deduced by looking at the DMA pointers involved.
> 
> As far as improvements go, IMO it would be much more useful to decode
> those pointers into seg-number/trb-index pairs. I wrote a PoC and the
> result is quite encouraging, I may submit it if there is interest.
> 

Agreed, printing the segment number and TRB index is a better approach.
This is my plan for the future, but in my opinion, the format for common
values should be consistent. Therefore, the change to segment number and
index should be implemented simultaneously across all xHCI driver prints,
except for some specific places. Thus, it's not changed in this patch set.

I plan to make this change after the rework of trb_in_td(). Currently,
I am testing a new trb_in_td() version suggested by Mathias, which would
make the number/index change even more logical.

Regards,
Niklas

[PATCH 3/4] usb: xhci: rework and simplify trb_in_td()

[Niklas Neronin]

Function trb_in_td() searches for a DMA address within a segment ring,
starting from 'start_seg'. If the DMA address is found within a segment
and is positioned between 'start_trb' and 'end_trb', the function returns
the segment. If not, it returns 'NULL'. See ring example at the end.

The original implementation is overly complex and suboptimal.

Key enhancements include:

- Utilize 'end_seg' pointer as counterpart to 'start_seg', narrowing the
  search scope from start to end segment, improving efficiency.

- Prioritizing the most frequent scenario where the start and end
  segments are identical, and 'start_trb' precedes end_trb', by
  checking this case first for quicker resolution.

- Clarifying the handling of TD wrap-around cases, where a TD spans
  back to the start segment, making start and end segments equal,
  but with 'end_trb' preceding 'start_trb', for better readability
  and maintainability.

============================= Example ====================================

Segment ring, consisting of 3 segments (A,B,C) each containing 3 TRBs
(1,2,3). Any segment can be start/end seg, and any TRB inside start seg
can be start TRB, vise versa.

      +---+   +---+   +---+
C --> | A |-->| B |-->| C |--> A
      +---+   +---+   +---+
        |       |       |
      +---+   +---+   +---+
      | 1 |   | 1 |   | 1 |
      | 2 |   | 2 |   | 2 |
      | 3 |   | 3 |   | 3 |
      +---+   +---+   +---+

Signed-off-by: Niklas Neronin <niklas.neronin@linux.intel.com>
---
 drivers/usb/host/xhci-ring.c | 72 +++++++++++++++++-------------------
 1 file changed, 33 insertions(+), 39 deletions(-)

diff --git a/drivers/usb/host/xhci-ring.c b/drivers/usb/host/xhci-ring.c
index a69972cc400c..23337c9d34c1 100644
--- a/drivers/usb/host/xhci-ring.c
+++ b/drivers/usb/host/xhci-ring.c
@@ -281,51 +281,45 @@ static void inc_enq(struct xhci_hcd *xhci, struct xhci_ring *ring,
  * If the suspect DMA address is a TRB in this TD, this function returns that
  * TRB's segment. Otherwise it returns 0.
  */
-static struct xhci_segment *trb_in_td(struct xhci_td *td, dma_addr_t suspect_dma)
+static struct xhci_segment *trb_in_td(struct xhci_td *td, dma_addr_t dma)
 {
-	dma_addr_t start_dma;
-	dma_addr_t end_seg_dma;
-	dma_addr_t end_trb_dma;
-	struct xhci_segment *cur_seg;
+	struct xhci_segment *seg = td->start_seg;
 
-	start_dma = xhci_trb_virt_to_dma(td->start_seg, td->start_trb);
-	cur_seg = td->start_seg;
-
-	do {
-		if (start_dma == 0)
-			return NULL;
-		/* We may get an event for a Link TRB in the middle of a TD */
-		end_seg_dma = xhci_trb_virt_to_dma(cur_seg,
-				&cur_seg->trbs[TRBS_PER_SEGMENT - 1]);
-		/* If the end TRB isn't in this segment, this is set to 0 */
-		end_trb_dma = xhci_trb_virt_to_dma(cur_seg, td->end_trb);
-
-		if (end_trb_dma > 0) {
-			/* The end TRB is in this segment, so suspect should be here */
-			if (start_dma <= end_trb_dma) {
-				if (suspect_dma >= start_dma && suspect_dma <= end_trb_dma)
-					return cur_seg;
-			} else {
-				/* Case for one segment with
-				 * a TD wrapped around to the top
-				 */
-				if ((suspect_dma >= start_dma &&
-							suspect_dma <= end_seg_dma) ||
-						(suspect_dma >= cur_seg->dma &&
-						 suspect_dma <= end_trb_dma))
-					return cur_seg;
-			}
+	if (td->start_seg == td->end_seg) {
+		if (td->start_trb <= td->end_trb) {
+			if (xhci_trb_virt_to_dma(td->start_seg, td->start_trb) <= dma &&
+			    dma <= xhci_trb_virt_to_dma(td->end_seg, td->end_trb))
+				return seg;
 			return NULL;
 		}
-		/* Might still be somewhere in this segment */
-		if (suspect_dma >= start_dma && suspect_dma <= end_seg_dma)
-			return cur_seg;
 
-		cur_seg = cur_seg->next;
-		start_dma = xhci_trb_virt_to_dma(cur_seg, &cur_seg->trbs[0]);
-	} while (cur_seg != td->start_seg);
+		/* Edge case, the TD wrapped around to the start segment. */
+		if (xhci_trb_virt_to_dma(td->end_seg, td->end_trb) < dma &&
+		    dma < xhci_trb_virt_to_dma(td->start_seg, td->start_trb))
+			return NULL;
+		if (seg->dma <= dma && dma <= (seg->dma + TRB_SEGMENT_SIZE))
+			return seg;
+		seg = seg->next;
+	}
 
-	return NULL;
+	/* Loop through segment which don't contain the DMA address. */
+	while (dma < seg->dma || (seg->dma + TRB_SEGMENT_SIZE) <= dma) {
+		if (seg == td->end_seg)
+			return NULL;
+
+		seg = seg->next;
+		if (seg == td->start_seg)
+			return NULL;
+	}
+
+	if (seg == td->start_seg) {
+		if (dma < xhci_trb_virt_to_dma(td->start_seg, td->start_trb))
+			return NULL;
+	} else if (seg == td->end_seg) {
+		if (xhci_trb_virt_to_dma(td->end_seg, td->end_trb) < dma)
+			return NULL;
+	}
+	return seg;
 }
 
 /*
-- 
2.47.2

Re: [PATCH 3/4] usb: xhci: rework and simplify trb_in_td()

[Michał Pecio]

Hi,

> +		/* Edge case, the TD wrapped around to the start segment. */
> +		if (xhci_trb_virt_to_dma(td->end_seg, td->end_trb) < dma &&
> +		    dma < xhci_trb_virt_to_dma(td->start_seg, td->start_trb))
> +			return NULL;
> +		if (seg->dma <= dma && dma <= (seg->dma + TRB_SEGMENT_SIZE))

It should be strict inequality for the upper bound here.

Note that this wraparound case souldn't be happening (the driver avoids
moving enqueue into deq_seg to simplify ring expansion) so no amount of
testing will catch problems here, until maybe something changes one day.

> +			return seg;
> +		seg = seg->next;
> +	}

The situation is tricky now, because we are either in start_seg and
end_seg is elsewhere or in start_seg->next and wraparound. But it looks
like the loop below will work OK for either case.

> +	/* Loop through segment which don't contain the DMA address. */
> +	while (dma < seg->dma || (seg->dma + TRB_SEGMENT_SIZE) <= dma) {

This condition looks like it could use the in_range() macro.

> +		if (seg == td->end_seg)
> +			return NULL;
> +
> +		seg = seg->next;
> +		if (seg == td->start_seg)
> +			return NULL;

I suppose this only happens if end_seg is not on the ring, fair enough.

> +	}

Maybe a comment here? Something like:

* At this point seg contains the dma and either:
* a. start_seg != end_seg and seg can be anywhere
* b. start_seg == end_seg in wraparound case and seg != start_seg

> +	if (seg == td->start_seg) {
> +		if (dma < xhci_trb_virt_to_dma(td->start_seg, td->start_trb))
> +			return NULL;
> +	} else if (seg == td->end_seg) {
> +		if (xhci_trb_virt_to_dma(td->end_seg, td->end_trb) < dma)
> +			return NULL;
> +	}
> +	return seg;

This should be corrent, but it's not something immediately obvious.

Not sure if this new implementation is really simpler than the old one.
I wonder if it wouldn't make sense to reorder this after the API change
(patch 4/4) to allow emergency revert if something unexpected shows up.

As for efficiency, those virt_to_dma translations aren't exactly free
and there are two. Maybe it could be faster to translate dma to virt
once and then compare. Sometimes also sizeof(*) < sizeof(dma_addr_t).

Regards,
Michal

Re: [PATCH 3/4] usb: xhci: rework and simplify trb_in_td()

[Mathias Nyman]

On 19.2.2025 10.56, Michał Pecio wrote:
> Hi,
> 
>> +		/* Edge case, the TD wrapped around to the start segment. */
>> +		if (xhci_trb_virt_to_dma(td->end_seg, td->end_trb) < dma &&
>> +		    dma < xhci_trb_virt_to_dma(td->start_seg, td->start_trb))
>> +			return NULL;
>> +		if (seg->dma <= dma && dma <= (seg->dma + TRB_SEGMENT_SIZE))
> 
> It should be strict inequality for the upper bound here.
> 
> Note that this wraparound case souldn't be happening (the driver avoids
> moving enqueue into deq_seg to simplify ring expansion) so no amount of
> testing will catch problems here, until maybe something changes one day.
> 
>> +			return seg;
>> +		seg = seg->next;
>> +	}
> 
> The situation is tricky now, because we are either in start_seg and
> end_seg is elsewhere or in start_seg->next and wraparound. But it looks
> like the loop below will work OK for either case.
> 
>> +	/* Loop through segment which don't contain the DMA address. */
>> +	while (dma < seg->dma || (seg->dma + TRB_SEGMENT_SIZE) <= dma) {
> 
> This condition looks like it could use the in_range() macro.
> 
>> +		if (seg == td->end_seg)
>> +			return NULL;
>> +
>> +		seg = seg->next;
>> +		if (seg == td->start_seg)
>> +			return NULL;
> 
> I suppose this only happens if end_seg is not on the ring, fair enough.
> 
>> +	}
> 
> Maybe a comment here? Something like:

> 
> * At this point seg contains the dma and either:
> * a. start_seg != end_seg and seg can be anywhere
> * b. start_seg == end_seg in wraparound case and seg != start_seg

Agreed, a comment here would help.

> 
>> +	if (seg == td->start_seg) {
>> +		if (dma < xhci_trb_virt_to_dma(td->start_seg, td->start_trb))
>> +			return NULL;
>> +	} else if (seg == td->end_seg) {
>> +		if (xhci_trb_virt_to_dma(td->end_seg, td->end_trb) < dma)
>> +			return NULL;
>> +	}
>> +	return seg;
> 
> This should be corrent, but it's not something immediately obvious.
> 
> Not sure if this new implementation is really simpler than the old one.
> I wonder if it wouldn't make sense to reorder this after the API change
> (patch 4/4) to allow emergency revert if something unexpected shows up.

Had to draw several cases on paper to go through this new version.
But I might just be used to the old one

> 
> As for efficiency, those virt_to_dma translations aren't exactly free
> and there are two. Maybe it could be faster to translate dma to virt
> once and then compare. Sometimes also sizeof(*) < sizeof(dma_addr_t).

Agreed

dma_addr_t start_dma = xhci_trb_virt_to_dma(td->start_seg, td->start_trb);
dma_addr_t end_dma = xhci_trb_virt_to_dma(td->end_seg, td->end_trb);

comparisons will then be a lot easier to read with start_dma and end_dma

-Mathias

[PATCH 5/4 RFC] An alternative dma_in_range() implementation

[Michał Pecio]

Here's my attempt at it, the patch goes on top of the whole series. It
compiles and passes basic testing (some URBs completed, some unlinked,
no errors or other malfunction apparent).

The idea is to translate dma to trb* ASAP and work with that, because
all data structures use trb* so the code gets shorter and less verbose.
This approach is also easy to adapt to changes in handle_tx_event(),
for example it could trivially return trb* instead of seg* or take trb*
(with or without accompanying seg*) and return bool or even seg*.

I tried to make the common case (start_seg == end_seg) fast, both for
hit and miss. 5 comparisons if the range wraps around, 4 if it doesn't.

diff --git a/drivers/usb/host/xhci-ring.c b/drivers/usb/host/xhci-ring.c
index 600842425f6d..b18e7fd7d01e 100644
--- a/drivers/usb/host/xhci-ring.c
+++ b/drivers/usb/host/xhci-ring.c
@@ -300,42 +300,36 @@ static struct xhci_segment *dma_in_range(struct xhci_segment *start_seg, union x
 					 dma_addr_t dma)
 {
 	struct xhci_segment *seg = start_seg;
+	union xhci_trb *trb;
 
-	if (start_seg == end_seg) {
-		if (start_trb <= end_trb) {
-			if (xhci_trb_virt_to_dma(start_seg, start_trb) <= dma &&
-			    dma <= xhci_trb_virt_to_dma(end_seg, end_trb))
-				return seg;
-			return NULL;
+	/* check if dma is a TRB in start_seg */
+	if (in_range(dma, seg->dma, TRB_SEGMENT_SIZE)) {
+		trb = seg->trbs + (dma - seg->dma) / sizeof(*trb);
+
+		if (trb >= start_trb)
+			/* check if the range covers it and we are done */
+			return (end_seg != seg || trb <= end_trb) ? seg : NULL;
+
+		/* check if the range circles back to the beginning of start_seg */
+		return (end_seg == seg && end_trb < start_trb && trb <= end_trb) ? seg : NULL;
+	}
+
+	/* stop if the range doesn't pass through any other segment */
+	if (end_seg == seg && (end_trb >= start_trb || seg->next == seg))
+		return NULL;
+
+	/* search remaining segments knowing that start_trb isn't there */
+	do {
+		seg = seg->next;
+
+		if (in_range(dma, seg->dma, TRB_SEGMENT_SIZE)) {
+			trb = seg->trbs + (dma - seg->dma) / sizeof(*trb);
+
+			return (seg != end_seg || trb <= end_trb) ? seg : NULL;
 		}
+	} while (seg != end_seg && seg != start_seg);
 
-		/* Edge case, the TD wrapped around to the start segment. */
-		if (xhci_trb_virt_to_dma(end_seg, end_trb) < dma &&
-		    dma < xhci_trb_virt_to_dma(start_seg, start_trb))
-			return NULL;
-		if (seg->dma <= dma && dma <= (seg->dma + TRB_SEGMENT_SIZE))
-			return seg;
-		seg = seg->next;
-	}
-
-	/* Loop through segment which don't contain the DMA address. */
-	while (dma < seg->dma || (seg->dma + TRB_SEGMENT_SIZE) <= dma) {
-		if (seg == end_seg)
-			return NULL;
-
-		seg = seg->next;
-		if (seg == start_seg)
-			return NULL;
-	}
-
-	if (seg == start_seg) {
-		if (dma < xhci_trb_virt_to_dma(start_seg, start_trb))
-			return NULL;
-	} else if (seg == end_seg) {
-		if (xhci_trb_virt_to_dma(end_seg, end_trb) < dma)
-			return NULL;
-	}
-	return seg;
+	return NULL;
 }
 
 static struct xhci_segment *trb_in_td(struct xhci_td *td, dma_addr_t dma)

Re: [PATCH 5/4 RFC] An alternative dma_in_range() implementation

[Neronin, Niklas]

On 20/02/2025 14.14, Michał Pecio wrote:
> Here's my attempt at it, the patch goes on top of the whole series. It
> compiles and passes basic testing (some URBs completed, some unlinked,
> no errors or other malfunction apparent).
> 
> The idea is to translate dma to trb* ASAP and work with that, because
> all data structures use trb* so the code gets shorter and less verbose.
> This approach is also easy to adapt to changes in handle_tx_event(),
> for example it could trivially return trb* instead of seg* or take trb*
> (with or without accompanying seg*) and return bool or even seg*.
> 
> I tried to make the common case (start_seg == end_seg) fast, both for
> hit and miss. 5 comparisons if the range wraps around, 4 if it doesn't.
> 

Thanks, I have a similar version. If it's alright with you, I'll try to
combine your version and mine into one and add it to trb_in_td-v2.

Thanks,
Niklas

> diff --git a/drivers/usb/host/xhci-ring.c b/drivers/usb/host/xhci-ring.c
> index 600842425f6d..b18e7fd7d01e 100644
> --- a/drivers/usb/host/xhci-ring.c
> +++ b/drivers/usb/host/xhci-ring.c
> @@ -300,42 +300,36 @@ static struct xhci_segment *dma_in_range(struct xhci_segment *start_seg, union x
>  					 dma_addr_t dma)
>  {
>  	struct xhci_segment *seg = start_seg;
> +	union xhci_trb *trb;
>  
> -	if (start_seg == end_seg) {
> -		if (start_trb <= end_trb) {
> -			if (xhci_trb_virt_to_dma(start_seg, start_trb) <= dma &&
> -			    dma <= xhci_trb_virt_to_dma(end_seg, end_trb))
> -				return seg;
> -			return NULL;
> +	/* check if dma is a TRB in start_seg */
> +	if (in_range(dma, seg->dma, TRB_SEGMENT_SIZE)) {
> +		trb = seg->trbs + (dma - seg->dma) / sizeof(*trb);
> +
> +		if (trb >= start_trb)
> +			/* check if the range covers it and we are done */
> +			return (end_seg != seg || trb <= end_trb) ? seg : NULL;
> +
> +		/* check if the range circles back to the beginning of start_seg */
> +		return (end_seg == seg && end_trb < start_trb && trb <= end_trb) ? seg : NULL;
> +	}
> +
> +	/* stop if the range doesn't pass through any other segment */
> +	if (end_seg == seg && (end_trb >= start_trb || seg->next == seg))
> +		return NULL;
> +
> +	/* search remaining segments knowing that start_trb isn't there */
> +	do {
> +		seg = seg->next;
> +
> +		if (in_range(dma, seg->dma, TRB_SEGMENT_SIZE)) {
> +			trb = seg->trbs + (dma - seg->dma) / sizeof(*trb);
> +
> +			return (seg != end_seg || trb <= end_trb) ? seg : NULL;
>  		}
> +	} while (seg != end_seg && seg != start_seg);
>  
> -		/* Edge case, the TD wrapped around to the start segment. */
> -		if (xhci_trb_virt_to_dma(end_seg, end_trb) < dma &&
> -		    dma < xhci_trb_virt_to_dma(start_seg, start_trb))
> -			return NULL;
> -		if (seg->dma <= dma && dma <= (seg->dma + TRB_SEGMENT_SIZE))
> -			return seg;
> -		seg = seg->next;
> -	}
> -
> -	/* Loop through segment which don't contain the DMA address. */
> -	while (dma < seg->dma || (seg->dma + TRB_SEGMENT_SIZE) <= dma) {
> -		if (seg == end_seg)
> -			return NULL;
> -
> -		seg = seg->next;
> -		if (seg == start_seg)
> -			return NULL;
> -	}
> -
> -	if (seg == start_seg) {
> -		if (dma < xhci_trb_virt_to_dma(start_seg, start_trb))
> -			return NULL;
> -	} else if (seg == end_seg) {
> -		if (xhci_trb_virt_to_dma(end_seg, end_trb) < dma)
> -			return NULL;
> -	}
> -	return seg;
> +	return NULL;
>  }
>  
>  static struct xhci_segment *trb_in_td(struct xhci_td *td, dma_addr_t dma)

Re: [PATCH 3/4] usb: xhci: rework and simplify trb_in_td()

[Neronin, Niklas]

On 19/02/2025 10.56, Michał Pecio wrote:
> Hi,
> 
>> +		/* Edge case, the TD wrapped around to the start segment. */
>> +		if (xhci_trb_virt_to_dma(td->end_seg, td->end_trb) < dma &&
>> +		    dma < xhci_trb_virt_to_dma(td->start_seg, td->start_trb))
>> +			return NULL;
>> +		if (seg->dma <= dma && dma <= (seg->dma + TRB_SEGMENT_SIZE))
> 
> It should be strict inequality for the upper bound here.

Thanks, you are correct. I'll change this to in_range64() and the bellow to !in_range64().

> 
>> +	/* Loop through segment which don't contain the DMA address. */
>> +	while (dma < seg->dma || (seg->dma + TRB_SEGMENT_SIZE) <= dma) {
> 
> Maybe a comment here? Something like:
> 
> * At this point seg contains the dma and either:
> * a. start_seg != end_seg and seg can be anywhere
> * b. start_seg == end_seg in wraparound case and seg != start_seg

Sure, I'll add some comments.

> 
>> +	if (seg == td->start_seg) {
>> +		if (dma < xhci_trb_virt_to_dma(td->start_seg, td->start_trb))
>> +			return NULL;
>> +	} else if (seg == td->end_seg) {
>> +		if (xhci_trb_virt_to_dma(td->end_seg, td->end_trb) < dma)
>> +			return NULL;
>> +	}
>> +	return seg;
> 
> This should be corrent, but it's not something immediately obvious.
> 
> Not sure if this new implementation is really simpler than the old one.
> I wonder if it wouldn't make sense to reorder this after the API change
> (patch 4/4) to allow emergency revert if something unexpected shows up.

I'll try this, the only issue is that the new API defines the range from;
 'start_trb' in 'start_seg' to 'end_trb' in 'end_seg'.
But the current version does not use 'end_seg'. So, if check checkpatch.pl
does not complain about unused 'end_seg' variable I will swap patch 4 and 5 places.

> 
> As for efficiency, those virt_to_dma translations aren't exactly free
> and there are two. Maybe it could be faster to translate dma to virt
> once and then compare.

I tried introducing xhci_dma_to_trb_virt() in this patch set, but decided against it.
In my opinion it is very minor optimization and I would rather introduce this function
in a separate patch set. I reworked trb_in_td() with this change in mind.

> Sometimes also sizeof(*) < sizeof(dma_addr_t).

This is an interesting idea. I just created a reverse xhci_virt_trb_to_dma(), i.e. xhci_dma_to_virt_trb().
I'll explore this idea. Thanks.

> 
> Regards,
> Michal

[PATCH 4/4] usb: xhci: modify trb_in_td() to be more modular

[Niklas Neronin]

Lay the ground work for future handle_tx_event() rework, which will
require a function which checks if a DMA address is in queueu.

To its core, trb_in_td() checks if a TRB falls within the specified start
and end TRB/segment range, a common requirement. For instance, a ring has
pointers to the queues first and last TRB/segment, which means that with
slight modifications and renaming trb_in_td() could work for other
structures not only TDs.

Modify trb_in_td() to accept pointer to start and end TRB/segment, and
introduce a new function that takes a 'xhci_td' struct pointer, forwarding
its elements to dma_in_range(), previously trb_in_td().

Signed-off-by: Niklas Neronin <niklas.neronin@linux.intel.com>
---
 drivers/usb/host/xhci-ring.c | 41 ++++++++++++++++++++++--------------
 1 file changed, 25 insertions(+), 16 deletions(-)

diff --git a/drivers/usb/host/xhci-ring.c b/drivers/usb/host/xhci-ring.c
index 23337c9d34c1..34699038b7f2 100644
--- a/drivers/usb/host/xhci-ring.c
+++ b/drivers/usb/host/xhci-ring.c
@@ -278,24 +278,28 @@ static void inc_enq(struct xhci_hcd *xhci, struct xhci_ring *ring,
 }
 
 /*
- * If the suspect DMA address is a TRB in this TD, this function returns that
- * TRB's segment. Otherwise it returns 0.
+ * Check if the DMA address of a TRB falls within the specified range.
+ * The range is defined by 'start_trb' in 'start_seg' and 'end_trb' in 'end_seg'.
+ * If the TRB's DMA address is within this range, return the segment containing the TRB.
+ * Otherwise, return 'NULL'.
  */
-static struct xhci_segment *trb_in_td(struct xhci_td *td, dma_addr_t dma)
+static struct xhci_segment *dma_in_range(struct xhci_segment *start_seg, union xhci_trb *start_trb,
+					 struct xhci_segment *end_seg, union xhci_trb *end_trb,
+					 dma_addr_t dma)
 {
-	struct xhci_segment *seg = td->start_seg;
+	struct xhci_segment *seg = start_seg;
 
-	if (td->start_seg == td->end_seg) {
-		if (td->start_trb <= td->end_trb) {
-			if (xhci_trb_virt_to_dma(td->start_seg, td->start_trb) <= dma &&
-			    dma <= xhci_trb_virt_to_dma(td->end_seg, td->end_trb))
+	if (start_seg == end_seg) {
+		if (start_trb <= end_trb) {
+			if (xhci_trb_virt_to_dma(start_seg, start_trb) <= dma &&
+			    dma <= xhci_trb_virt_to_dma(end_seg, end_trb))
 				return seg;
 			return NULL;
 		}
 
 		/* Edge case, the TD wrapped around to the start segment. */
-		if (xhci_trb_virt_to_dma(td->end_seg, td->end_trb) < dma &&
-		    dma < xhci_trb_virt_to_dma(td->start_seg, td->start_trb))
+		if (xhci_trb_virt_to_dma(end_seg, end_trb) < dma &&
+		    dma < xhci_trb_virt_to_dma(start_seg, start_trb))
 			return NULL;
 		if (seg->dma <= dma && dma <= (seg->dma + TRB_SEGMENT_SIZE))
 			return seg;
@@ -304,24 +308,29 @@ static struct xhci_segment *trb_in_td(struct xhci_td *td, dma_addr_t dma)
 
 	/* Loop through segment which don't contain the DMA address. */
 	while (dma < seg->dma || (seg->dma + TRB_SEGMENT_SIZE) <= dma) {
-		if (seg == td->end_seg)
+		if (seg == end_seg)
 			return NULL;
 
 		seg = seg->next;
-		if (seg == td->start_seg)
+		if (seg == start_seg)
 			return NULL;
 	}
 
-	if (seg == td->start_seg) {
-		if (dma < xhci_trb_virt_to_dma(td->start_seg, td->start_trb))
+	if (seg == start_seg) {
+		if (dma < xhci_trb_virt_to_dma(start_seg, start_trb))
 			return NULL;
-	} else if (seg == td->end_seg) {
-		if (xhci_trb_virt_to_dma(td->end_seg, td->end_trb) < dma)
+	} else if (seg == end_seg) {
+		if (xhci_trb_virt_to_dma(end_seg, end_trb) < dma)
 			return NULL;
 	}
 	return seg;
 }
 
+static struct xhci_segment *trb_in_td(struct xhci_td *td, dma_addr_t dma)
+{
+	return dma_in_range(td->start_seg, td->start_trb, td->end_seg, td->end_trb, dma);
+}
+
 /*
  * Return number of free normal TRBs from enqueue to dequeue pointer on ring.
  * Not counting an assumed link TRB at end of each TRBS_PER_SEGMENT sized segment.
-- 
2.47.2