* Re: [PATCH v2] xhci: fix usb3 streams
2013-10-15 1:54 ` [PATCH v2] xhci: fix usb3 streams Gerd Hoffmann
@ 2013-10-15 6:13 ` Hans de Goede
2013-10-15 14:53 ` Alan Stern
2013-10-17 18:40 ` Sarah Sharp
2 siblings, 0 replies; 12+ messages in thread
From: Hans de Goede @ 2013-10-15 6:13 UTC (permalink / raw)
To: Gerd Hoffmann
Cc: Jan Kara, Andrew Morton, linux-kernel, linux-usb, Sarah Sharp
Hi Sarah,
On 10/15/2013 03:54 AM, Gerd Hoffmann wrote:
> Gerd, Hans, any objections to this updated patch? The warning is fixed
> with it.
No objections, looks good to me.
>
> The patch probably still needs to address the case where the ring
> expansion fails because we can't insert the new segments into the radix
> tree. The patch should probably allocate the segments, attempt to add
> them to the radix tree, and fail without modifying the link TRBs of the
> ring. I'd have to look more deeply into the code to see what exactly
> should be done there.
>
> I would like that issue fixed before I merge these patches, so if you
> want to take a stab at fixing it, please do.
>
> Sarah Sharp
Regards,
Hans
>
> 8<---------------------------------------------------------------->8
>
> xhci maintains a radix tree for each stream endpoint because it must
> be able to map a trb address to the stream ring. Each ring segment
> must be added to the ring for this to work. Currently xhci sticks
> only the first segment of each stream ring into the radix tree.
>
> Result is that things work initially, but as soon as the first segment
> is full xhci can't map the trb address from the completion event to the
> stream ring any more -> BOOM. You'll find this message in the logs:
>
> ERROR Transfer event for disabled endpoint or incorrect stream ring
>
> This patch adds a helper function to update the radix tree, and a
> function to remove ring segments from the tree. Both functions loop
> over the segment list and handles all segments instead of just the
> first.
>
> [Note: Sarah changed this patch to add radix_tree_maybe_preload() and
> radix_tree_preload_end() calls around the radix tree insert, since we
> can now insert entries in interrupt context. There are now two helper
> functions to make the code cleaner, and those functions are moved to
> make them static.]
>
> Signed-off-by: Gerd Hoffmann <kraxel@redhat.com>
> Signed-off-by: Hans de Goede <hdegoede@redhat.com>
> Signed-off-by: Sarah Sharp <sarah.a.sharp@linux.intel.com>
> ---
> drivers/usb/host/xhci-mem.c | 132 +++++++++++++++++++++++++++++---------------
> drivers/usb/host/xhci.h | 1 +
> 2 files changed, 90 insertions(+), 43 deletions(-)
>
> diff --git a/drivers/usb/host/xhci-mem.c b/drivers/usb/host/xhci-mem.c
> index 83bcd13..8b1ba5b 100644
> --- a/drivers/usb/host/xhci-mem.c
> +++ b/drivers/usb/host/xhci-mem.c
> @@ -149,14 +149,95 @@ static void xhci_link_rings(struct xhci_hcd *xhci, struct xhci_ring *ring,
> }
> }
>
> +/*
> + * We need a radix tree for mapping physical addresses of TRBs to which stream
> + * ID they belong to. We need to do this because the host controller won't tell
> + * us which stream ring the TRB came from. We could store the stream ID in an
> + * event data TRB, but that doesn't help us for the cancellation case, since the
> + * endpoint may stop before it reaches that event data TRB.
> + *
> + * The radix tree maps the upper portion of the TRB DMA address to a ring
> + * segment that has the same upper portion of DMA addresses. For example, say I
> + * have segments of size 1KB, that are always 64-byte aligned. A segment may
> + * start at 0x10c91000 and end at 0x10c913f0. If I use the upper 10 bits, the
> + * key to the stream ID is 0x43244. I can use the DMA address of the TRB to
> + * pass the radix tree a key to get the right stream ID:
> + *
> + * 0x10c90fff >> 10 = 0x43243
> + * 0x10c912c0 >> 10 = 0x43244
> + * 0x10c91400 >> 10 = 0x43245
> + *
> + * Obviously, only those TRBs with DMA addresses that are within the segment
> + * will make the radix tree return the stream ID for that ring.
> + *
> + * Caveats for the radix tree:
> + *
> + * The radix tree uses an unsigned long as a key pair. On 32-bit systems, an
> + * unsigned long will be 32-bits; on a 64-bit system an unsigned long will be
> + * 64-bits. Since we only request 32-bit DMA addresses, we can use that as the
> + * key on 32-bit or 64-bit systems (it would also be fine if we asked for 64-bit
> + * PCI DMA addresses on a 64-bit system). There might be a problem on 32-bit
> + * extended systems (where the DMA address can be bigger than 32-bits),
> + * if we allow the PCI dma mask to be bigger than 32-bits. So don't do that.
> + */
> +static int xhci_update_stream_mapping(struct xhci_ring *ring, gfp_t mem_flags)
> +{
> + struct xhci_segment *seg;
> + unsigned long key;
> + int ret;
> +
> + if (WARN_ON_ONCE(ring->trb_address_map == NULL))
> + return 0;
> +
> + seg = ring->first_seg;
> + do {
> + key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
> + /* Skip any segments that were already added. */
> + if (radix_tree_lookup(ring->trb_address_map, key))
> + continue;
> +
> + ret = radix_tree_maybe_preload(mem_flags);
> + if (ret)
> + return ret;
> + ret = radix_tree_insert(ring->trb_address_map,
> + key, ring);
> + radix_tree_preload_end();
> + if (ret)
> + return ret;
> + seg = seg->next;
> + } while (seg != ring->first_seg);
> +
> + return 0;
> +}
> +
> +static void xhci_remove_stream_mapping(struct xhci_ring *ring)
> +{
> + struct xhci_segment *seg;
> + unsigned long key;
> +
> + if (WARN_ON_ONCE(ring->trb_address_map == NULL))
> + return;
> +
> + seg = ring->first_seg;
> + do {
> + key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
> + if (radix_tree_lookup(ring->trb_address_map, key))
> + radix_tree_delete(ring->trb_address_map, key);
> + seg = seg->next;
> + } while (seg != ring->first_seg);
> +}
> +
> /* XXX: Do we need the hcd structure in all these functions? */
> void xhci_ring_free(struct xhci_hcd *xhci, struct xhci_ring *ring)
> {
> if (!ring)
> return;
>
> - if (ring->first_seg)
> + if (ring->first_seg) {
> + if (ring->type == TYPE_STREAM)
> + xhci_remove_stream_mapping(ring);
> xhci_free_segments_for_ring(xhci, ring->first_seg);
> + }
>
> kfree(ring);
> }
> @@ -353,6 +434,11 @@ int xhci_ring_expansion(struct xhci_hcd *xhci, struct xhci_ring *ring,
> "ring expansion succeed, now has %d segments",
> ring->num_segs);
>
> + if (ring->type == TYPE_STREAM) {
> + ret = xhci_update_stream_mapping(ring, flags);
> + WARN_ON(ret); /* FIXME */
> + }
> +
> return 0;
> }
>
> @@ -509,36 +595,6 @@ struct xhci_ring *xhci_stream_id_to_ring(
> * The number of stream contexts in the stream context array may be bigger than
> * the number of streams the driver wants to use. This is because the number of
> * stream context array entries must be a power of two.
> - *
> - * We need a radix tree for mapping physical addresses of TRBs to which stream
> - * ID they belong to. We need to do this because the host controller won't tell
> - * us which stream ring the TRB came from. We could store the stream ID in an
> - * event data TRB, but that doesn't help us for the cancellation case, since the
> - * endpoint may stop before it reaches that event data TRB.
> - *
> - * The radix tree maps the upper portion of the TRB DMA address to a ring
> - * segment that has the same upper portion of DMA addresses. For example, say I
> - * have segments of size 1KB, that are always 64-byte aligned. A segment may
> - * start at 0x10c91000 and end at 0x10c913f0. If I use the upper 10 bits, the
> - * key to the stream ID is 0x43244. I can use the DMA address of the TRB to
> - * pass the radix tree a key to get the right stream ID:
> - *
> - * 0x10c90fff >> 10 = 0x43243
> - * 0x10c912c0 >> 10 = 0x43244
> - * 0x10c91400 >> 10 = 0x43245
> - *
> - * Obviously, only those TRBs with DMA addresses that are within the segment
> - * will make the radix tree return the stream ID for that ring.
> - *
> - * Caveats for the radix tree:
> - *
> - * The radix tree uses an unsigned long as a key pair. On 32-bit systems, an
> - * unsigned long will be 32-bits; on a 64-bit system an unsigned long will be
> - * 64-bits. Since we only request 32-bit DMA addresses, we can use that as the
> - * key on 32-bit or 64-bit systems (it would also be fine if we asked for 64-bit
> - * PCI DMA addresses on a 64-bit system). There might be a problem on 32-bit
> - * extended systems (where the DMA address can be bigger than 32-bits),
> - * if we allow the PCI dma mask to be bigger than 32-bits. So don't do that.
> */
> struct xhci_stream_info *xhci_alloc_stream_info(struct xhci_hcd *xhci,
> unsigned int num_stream_ctxs,
> @@ -547,7 +603,6 @@ struct xhci_stream_info *xhci_alloc_stream_info(struct xhci_hcd *xhci,
> struct xhci_stream_info *stream_info;
> u32 cur_stream;
> struct xhci_ring *cur_ring;
> - unsigned long key;
> u64 addr;
> int ret;
>
> @@ -602,6 +657,7 @@ struct xhci_stream_info *xhci_alloc_stream_info(struct xhci_hcd *xhci,
> if (!cur_ring)
> goto cleanup_rings;
> cur_ring->stream_id = cur_stream;
> + cur_ring->trb_address_map = &stream_info->trb_address_map;
> /* Set deq ptr, cycle bit, and stream context type */
> addr = cur_ring->first_seg->dma |
> SCT_FOR_CTX(SCT_PRI_TR) |
> @@ -611,10 +667,7 @@ struct xhci_stream_info *xhci_alloc_stream_info(struct xhci_hcd *xhci,
> xhci_dbg(xhci, "Setting stream %d ring ptr to 0x%08llx\n",
> cur_stream, (unsigned long long) addr);
>
> - key = (unsigned long)
> - (cur_ring->first_seg->dma >> TRB_SEGMENT_SHIFT);
> - ret = radix_tree_insert(&stream_info->trb_address_map,
> - key, cur_ring);
> + ret = xhci_update_stream_mapping(cur_ring, mem_flags);
> if (ret) {
> xhci_ring_free(xhci, cur_ring);
> stream_info->stream_rings[cur_stream] = NULL;
> @@ -634,9 +687,6 @@ cleanup_rings:
> for (cur_stream = 1; cur_stream < num_streams; cur_stream++) {
> cur_ring = stream_info->stream_rings[cur_stream];
> if (cur_ring) {
> - addr = cur_ring->first_seg->dma;
> - radix_tree_delete(&stream_info->trb_address_map,
> - addr >> TRB_SEGMENT_SHIFT);
> xhci_ring_free(xhci, cur_ring);
> stream_info->stream_rings[cur_stream] = NULL;
> }
> @@ -697,7 +747,6 @@ void xhci_free_stream_info(struct xhci_hcd *xhci,
> {
> int cur_stream;
> struct xhci_ring *cur_ring;
> - dma_addr_t addr;
>
> if (!stream_info)
> return;
> @@ -706,9 +755,6 @@ void xhci_free_stream_info(struct xhci_hcd *xhci,
> cur_stream++) {
> cur_ring = stream_info->stream_rings[cur_stream];
> if (cur_ring) {
> - addr = cur_ring->first_seg->dma;
> - radix_tree_delete(&stream_info->trb_address_map,
> - addr >> TRB_SEGMENT_SHIFT);
> xhci_ring_free(xhci, cur_ring);
> stream_info->stream_rings[cur_stream] = NULL;
> }
> diff --git a/drivers/usb/host/xhci.h b/drivers/usb/host/xhci.h
> index 289fbfb..737dcc1 100644
> --- a/drivers/usb/host/xhci.h
> +++ b/drivers/usb/host/xhci.h
> @@ -1334,6 +1334,7 @@ struct xhci_ring {
> unsigned int num_trbs_free_temp;
> enum xhci_ring_type type;
> bool last_td_was_short;
> + struct radix_tree_root *trb_address_map;
> };
>
> struct xhci_erst_entry {
>
^ permalink raw reply [flat|nested] 12+ messages in thread* Re: [PATCH v2] xhci: fix usb3 streams
2013-10-15 1:54 ` [PATCH v2] xhci: fix usb3 streams Gerd Hoffmann
2013-10-15 6:13 ` Hans de Goede
@ 2013-10-15 14:53 ` Alan Stern
2013-10-16 23:43 ` Sarah Sharp
2013-10-17 18:40 ` Sarah Sharp
2 siblings, 1 reply; 12+ messages in thread
From: Alan Stern @ 2013-10-15 14:53 UTC (permalink / raw)
To: Sarah Sharp, Gerd Hoffmann
Cc: Hans de Goede, Jan Kara, Andrew Morton, Kernel development list,
USB list
On Mon, 14 Oct 2013, Gerd Hoffmann wrote:
> Gerd, Hans, any objections to this updated patch? The warning is fixed
> with it.
>
> The patch probably still needs to address the case where the ring
> expansion fails because we can't insert the new segments into the radix
> tree. The patch should probably allocate the segments, attempt to add
> them to the radix tree, and fail without modifying the link TRBs of the
> ring. I'd have to look more deeply into the code to see what exactly
> should be done there.
>
> I would like that issue fixed before I merge these patches, so if you
> want to take a stab at fixing it, please do.
>
> Sarah Sharp
Sarah, how did you manage to send an email with the "From:" line set to
Gerd's name and address?
> 8<---------------------------------------------------------------->8
>
> xhci maintains a radix tree for each stream endpoint because it must
> be able to map a trb address to the stream ring. Each ring segment
> must be added to the ring for this to work. Currently xhci sticks
> only the first segment of each stream ring into the radix tree.
>
> Result is that things work initially, but as soon as the first segment
> is full xhci can't map the trb address from the completion event to the
> stream ring any more -> BOOM. You'll find this message in the logs:
>
> ERROR Transfer event for disabled endpoint or incorrect stream ring
>
> This patch adds a helper function to update the radix tree, and a
> function to remove ring segments from the tree. Both functions loop
> over the segment list and handles all segments instead of just the
> first.
There may be a simpler approach to this problem.
When using a new ring segment, keep the first TRB entry in reserve.
Don't put a normal TRB in there, instead leave it as a no-op entry
containing a pointer to the stream ring. (Make the prior Link TRB
point to the second entry in the new segment instead of the first.)
Then you won't have to add to or remove anything from the radix tree.
Alan Stern
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH v2] xhci: fix usb3 streams
2013-10-15 14:53 ` Alan Stern
@ 2013-10-16 23:43 ` Sarah Sharp
2013-10-17 14:30 ` Alan Stern
0 siblings, 1 reply; 12+ messages in thread
From: Sarah Sharp @ 2013-10-16 23:43 UTC (permalink / raw)
To: Alan Stern
Cc: Gerd Hoffmann, Hans de Goede, Jan Kara, Andrew Morton,
Kernel development list, USB list
On Tue, Oct 15, 2013 at 10:53:57AM -0400, Alan Stern wrote:
> On Mon, 14 Oct 2013, Gerd Hoffmann wrote:
>
> > Gerd, Hans, any objections to this updated patch? The warning is fixed
> > with it.
> >
> > The patch probably still needs to address the case where the ring
> > expansion fails because we can't insert the new segments into the radix
> > tree. The patch should probably allocate the segments, attempt to add
> > them to the radix tree, and fail without modifying the link TRBs of the
> > ring. I'd have to look more deeply into the code to see what exactly
> > should be done there.
> >
> > I would like that issue fixed before I merge these patches, so if you
> > want to take a stab at fixing it, please do.
> >
> > Sarah Sharp
>
> Sarah, how did you manage to send an email with the "From:" line set to
> Gerd's name and address?
I sent it using git format-patch and mutt, and accidentally left Gerd's
>From line intact. Looking at the headers, it seems like the default
Intel exchange servers simply passed the email through. Header forging,
what fun!
> > 8<---------------------------------------------------------------->8
> >
> > xhci maintains a radix tree for each stream endpoint because it must
> > be able to map a trb address to the stream ring. Each ring segment
> > must be added to the ring for this to work. Currently xhci sticks
> > only the first segment of each stream ring into the radix tree.
> >
> > Result is that things work initially, but as soon as the first segment
> > is full xhci can't map the trb address from the completion event to the
> > stream ring any more -> BOOM. You'll find this message in the logs:
> >
> > ERROR Transfer event for disabled endpoint or incorrect stream ring
> >
> > This patch adds a helper function to update the radix tree, and a
> > function to remove ring segments from the tree. Both functions loop
> > over the segment list and handles all segments instead of just the
> > first.
>
> There may be a simpler approach to this problem.
>
> When using a new ring segment, keep the first TRB entry in reserve.
> Don't put a normal TRB in there, instead leave it as a no-op entry
> containing a pointer to the stream ring. (Make the prior Link TRB
> point to the second entry in the new segment instead of the first.)
>
> Then you won't have to add to or remove anything from the radix tree.
I don't understand how this would help. Are you advocating a different
way of mapping TRB DMA addresses to stream rings that would allow us to
ditch the radix tree all together?
Ok, so with your solution, we have a virtual stream ring pointer as the
first TRB of the segment. We get an event with the DMA address of a TRB
in one of many stream rings on an endpoint. From that, I think we can
infer the DMA address of the first TRB on the segment, due to the
alignment requirements and ring size.
And then what do we do with that? We don't have the virtual address of
that first TRB, so the xHCI driver can't read the ring pointer from it.
I'm confused as to what the next steps would be to solve this.
Sarah Sharp
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH v2] xhci: fix usb3 streams
2013-10-16 23:43 ` Sarah Sharp
@ 2013-10-17 14:30 ` Alan Stern
0 siblings, 0 replies; 12+ messages in thread
From: Alan Stern @ 2013-10-17 14:30 UTC (permalink / raw)
To: Sarah Sharp
Cc: Gerd Hoffmann, Hans de Goede, Jan Kara, Andrew Morton,
Kernel development list, USB list
On Wed, 16 Oct 2013, Sarah Sharp wrote:
> > > xhci maintains a radix tree for each stream endpoint because it must
> > > be able to map a trb address to the stream ring. Each ring segment
> > > must be added to the ring for this to work. Currently xhci sticks
> > > only the first segment of each stream ring into the radix tree.
> > There may be a simpler approach to this problem.
> >
> > When using a new ring segment, keep the first TRB entry in reserve.
> > Don't put a normal TRB in there, instead leave it as a no-op entry
> > containing a pointer to the stream ring. (Make the prior Link TRB
> > point to the second entry in the new segment instead of the first.)
> >
> > Then you won't have to add to or remove anything from the radix tree.
>
> I don't understand how this would help. Are you advocating a different
> way of mapping TRB DMA addresses to stream rings that would allow us to
> ditch the radix tree all together?
>
> Ok, so with your solution, we have a virtual stream ring pointer as the
> first TRB of the segment. We get an event with the DMA address of a TRB
> in one of many stream rings on an endpoint. From that, I think we can
> infer the DMA address of the first TRB on the segment, due to the
> alignment requirements and ring size.
>
> And then what do we do with that? We don't have the virtual address of
> that first TRB, so the xHCI driver can't read the ring pointer from it.
> I'm confused as to what the next steps would be to solve this.
My mistake; I misunderstood the original description of the problem.
I didn't realize that "map a trb address" referred to the TRB's DMA
address.
BTW, ohci-hcd faces the same problem (of mapping DMA addresses to
kernel addresses). It solves the problem with a hash table rather than
a radix tree.
Alan Stern
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH v2] xhci: fix usb3 streams
2013-10-15 1:54 ` [PATCH v2] xhci: fix usb3 streams Gerd Hoffmann
2013-10-15 6:13 ` Hans de Goede
2013-10-15 14:53 ` Alan Stern
@ 2013-10-17 18:40 ` Sarah Sharp
2013-10-17 19:44 ` [PATCH] xhci: Remove segments from radix tree on failed insert Sarah Sharp
2 siblings, 1 reply; 12+ messages in thread
From: Sarah Sharp @ 2013-10-17 18:40 UTC (permalink / raw)
To: Gerd Hoffmann, Hans de Goede
Cc: Jan Kara, Andrew Morton, linux-kernel, linux-usb
The more I look at this patch, the more I hate it for the failure cases
it doesn't cover.
What happens if the radix_tree_insert fails in the middle of adding a
set of ring segments? We leave those segments that were inserted in the
radix tree, which is a problem, since we could allocate those segments
out of the DMA pool later for a different stream ID.
That's OK for the initial stream ring allocation, since the xhci_ring
itself will get freed. It's not ok for ring expansion through, since
the xhci_ring remains in tact, and we simply fail the URB submission.
I'm working on a patch to fix this, but may not get it done today.
Sarah Sharp
On Mon, Oct 14, 2013 at 06:54:24PM -0700, Gerd Hoffmann wrote:
> Gerd, Hans, any objections to this updated patch? The warning is fixed
> with it.
>
> The patch probably still needs to address the case where the ring
> expansion fails because we can't insert the new segments into the radix
> tree. The patch should probably allocate the segments, attempt to add
> them to the radix tree, and fail without modifying the link TRBs of the
> ring. I'd have to look more deeply into the code to see what exactly
> should be done there.
>
> I would like that issue fixed before I merge these patches, so if you
> want to take a stab at fixing it, please do.
>
> Sarah Sharp
>
> 8<---------------------------------------------------------------->8
>
> xhci maintains a radix tree for each stream endpoint because it must
> be able to map a trb address to the stream ring. Each ring segment
> must be added to the ring for this to work. Currently xhci sticks
> only the first segment of each stream ring into the radix tree.
>
> Result is that things work initially, but as soon as the first segment
> is full xhci can't map the trb address from the completion event to the
> stream ring any more -> BOOM. You'll find this message in the logs:
>
> ERROR Transfer event for disabled endpoint or incorrect stream ring
>
> This patch adds a helper function to update the radix tree, and a
> function to remove ring segments from the tree. Both functions loop
> over the segment list and handles all segments instead of just the
> first.
>
> [Note: Sarah changed this patch to add radix_tree_maybe_preload() and
> radix_tree_preload_end() calls around the radix tree insert, since we
> can now insert entries in interrupt context. There are now two helper
> functions to make the code cleaner, and those functions are moved to
> make them static.]
>
> Signed-off-by: Gerd Hoffmann <kraxel@redhat.com>
> Signed-off-by: Hans de Goede <hdegoede@redhat.com>
> Signed-off-by: Sarah Sharp <sarah.a.sharp@linux.intel.com>
> ---
> drivers/usb/host/xhci-mem.c | 132 +++++++++++++++++++++++++++++---------------
> drivers/usb/host/xhci.h | 1 +
> 2 files changed, 90 insertions(+), 43 deletions(-)
>
> diff --git a/drivers/usb/host/xhci-mem.c b/drivers/usb/host/xhci-mem.c
> index 83bcd13..8b1ba5b 100644
> --- a/drivers/usb/host/xhci-mem.c
> +++ b/drivers/usb/host/xhci-mem.c
> @@ -149,14 +149,95 @@ static void xhci_link_rings(struct xhci_hcd *xhci, struct xhci_ring *ring,
> }
> }
>
> +/*
> + * We need a radix tree for mapping physical addresses of TRBs to which stream
> + * ID they belong to. We need to do this because the host controller won't tell
> + * us which stream ring the TRB came from. We could store the stream ID in an
> + * event data TRB, but that doesn't help us for the cancellation case, since the
> + * endpoint may stop before it reaches that event data TRB.
> + *
> + * The radix tree maps the upper portion of the TRB DMA address to a ring
> + * segment that has the same upper portion of DMA addresses. For example, say I
> + * have segments of size 1KB, that are always 64-byte aligned. A segment may
> + * start at 0x10c91000 and end at 0x10c913f0. If I use the upper 10 bits, the
> + * key to the stream ID is 0x43244. I can use the DMA address of the TRB to
> + * pass the radix tree a key to get the right stream ID:
> + *
> + * 0x10c90fff >> 10 = 0x43243
> + * 0x10c912c0 >> 10 = 0x43244
> + * 0x10c91400 >> 10 = 0x43245
> + *
> + * Obviously, only those TRBs with DMA addresses that are within the segment
> + * will make the radix tree return the stream ID for that ring.
> + *
> + * Caveats for the radix tree:
> + *
> + * The radix tree uses an unsigned long as a key pair. On 32-bit systems, an
> + * unsigned long will be 32-bits; on a 64-bit system an unsigned long will be
> + * 64-bits. Since we only request 32-bit DMA addresses, we can use that as the
> + * key on 32-bit or 64-bit systems (it would also be fine if we asked for 64-bit
> + * PCI DMA addresses on a 64-bit system). There might be a problem on 32-bit
> + * extended systems (where the DMA address can be bigger than 32-bits),
> + * if we allow the PCI dma mask to be bigger than 32-bits. So don't do that.
> + */
> +static int xhci_update_stream_mapping(struct xhci_ring *ring, gfp_t mem_flags)
> +{
> + struct xhci_segment *seg;
> + unsigned long key;
> + int ret;
> +
> + if (WARN_ON_ONCE(ring->trb_address_map == NULL))
> + return 0;
> +
> + seg = ring->first_seg;
> + do {
> + key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
> + /* Skip any segments that were already added. */
> + if (radix_tree_lookup(ring->trb_address_map, key))
> + continue;
> +
> + ret = radix_tree_maybe_preload(mem_flags);
> + if (ret)
> + return ret;
> + ret = radix_tree_insert(ring->trb_address_map,
> + key, ring);
> + radix_tree_preload_end();
> + if (ret)
> + return ret;
> + seg = seg->next;
> + } while (seg != ring->first_seg);
> +
> + return 0;
> +}
> +
> +static void xhci_remove_stream_mapping(struct xhci_ring *ring)
> +{
> + struct xhci_segment *seg;
> + unsigned long key;
> +
> + if (WARN_ON_ONCE(ring->trb_address_map == NULL))
> + return;
> +
> + seg = ring->first_seg;
> + do {
> + key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
> + if (radix_tree_lookup(ring->trb_address_map, key))
> + radix_tree_delete(ring->trb_address_map, key);
> + seg = seg->next;
> + } while (seg != ring->first_seg);
> +}
> +
> /* XXX: Do we need the hcd structure in all these functions? */
> void xhci_ring_free(struct xhci_hcd *xhci, struct xhci_ring *ring)
> {
> if (!ring)
> return;
>
> - if (ring->first_seg)
> + if (ring->first_seg) {
> + if (ring->type == TYPE_STREAM)
> + xhci_remove_stream_mapping(ring);
> xhci_free_segments_for_ring(xhci, ring->first_seg);
> + }
>
> kfree(ring);
> }
> @@ -353,6 +434,11 @@ int xhci_ring_expansion(struct xhci_hcd *xhci, struct xhci_ring *ring,
> "ring expansion succeed, now has %d segments",
> ring->num_segs);
>
> + if (ring->type == TYPE_STREAM) {
> + ret = xhci_update_stream_mapping(ring, flags);
> + WARN_ON(ret); /* FIXME */
> + }
> +
> return 0;
> }
>
> @@ -509,36 +595,6 @@ struct xhci_ring *xhci_stream_id_to_ring(
> * The number of stream contexts in the stream context array may be bigger than
> * the number of streams the driver wants to use. This is because the number of
> * stream context array entries must be a power of two.
> - *
> - * We need a radix tree for mapping physical addresses of TRBs to which stream
> - * ID they belong to. We need to do this because the host controller won't tell
> - * us which stream ring the TRB came from. We could store the stream ID in an
> - * event data TRB, but that doesn't help us for the cancellation case, since the
> - * endpoint may stop before it reaches that event data TRB.
> - *
> - * The radix tree maps the upper portion of the TRB DMA address to a ring
> - * segment that has the same upper portion of DMA addresses. For example, say I
> - * have segments of size 1KB, that are always 64-byte aligned. A segment may
> - * start at 0x10c91000 and end at 0x10c913f0. If I use the upper 10 bits, the
> - * key to the stream ID is 0x43244. I can use the DMA address of the TRB to
> - * pass the radix tree a key to get the right stream ID:
> - *
> - * 0x10c90fff >> 10 = 0x43243
> - * 0x10c912c0 >> 10 = 0x43244
> - * 0x10c91400 >> 10 = 0x43245
> - *
> - * Obviously, only those TRBs with DMA addresses that are within the segment
> - * will make the radix tree return the stream ID for that ring.
> - *
> - * Caveats for the radix tree:
> - *
> - * The radix tree uses an unsigned long as a key pair. On 32-bit systems, an
> - * unsigned long will be 32-bits; on a 64-bit system an unsigned long will be
> - * 64-bits. Since we only request 32-bit DMA addresses, we can use that as the
> - * key on 32-bit or 64-bit systems (it would also be fine if we asked for 64-bit
> - * PCI DMA addresses on a 64-bit system). There might be a problem on 32-bit
> - * extended systems (where the DMA address can be bigger than 32-bits),
> - * if we allow the PCI dma mask to be bigger than 32-bits. So don't do that.
> */
> struct xhci_stream_info *xhci_alloc_stream_info(struct xhci_hcd *xhci,
> unsigned int num_stream_ctxs,
> @@ -547,7 +603,6 @@ struct xhci_stream_info *xhci_alloc_stream_info(struct xhci_hcd *xhci,
> struct xhci_stream_info *stream_info;
> u32 cur_stream;
> struct xhci_ring *cur_ring;
> - unsigned long key;
> u64 addr;
> int ret;
>
> @@ -602,6 +657,7 @@ struct xhci_stream_info *xhci_alloc_stream_info(struct xhci_hcd *xhci,
> if (!cur_ring)
> goto cleanup_rings;
> cur_ring->stream_id = cur_stream;
> + cur_ring->trb_address_map = &stream_info->trb_address_map;
> /* Set deq ptr, cycle bit, and stream context type */
> addr = cur_ring->first_seg->dma |
> SCT_FOR_CTX(SCT_PRI_TR) |
> @@ -611,10 +667,7 @@ struct xhci_stream_info *xhci_alloc_stream_info(struct xhci_hcd *xhci,
> xhci_dbg(xhci, "Setting stream %d ring ptr to 0x%08llx\n",
> cur_stream, (unsigned long long) addr);
>
> - key = (unsigned long)
> - (cur_ring->first_seg->dma >> TRB_SEGMENT_SHIFT);
> - ret = radix_tree_insert(&stream_info->trb_address_map,
> - key, cur_ring);
> + ret = xhci_update_stream_mapping(cur_ring, mem_flags);
> if (ret) {
> xhci_ring_free(xhci, cur_ring);
> stream_info->stream_rings[cur_stream] = NULL;
> @@ -634,9 +687,6 @@ cleanup_rings:
> for (cur_stream = 1; cur_stream < num_streams; cur_stream++) {
> cur_ring = stream_info->stream_rings[cur_stream];
> if (cur_ring) {
> - addr = cur_ring->first_seg->dma;
> - radix_tree_delete(&stream_info->trb_address_map,
> - addr >> TRB_SEGMENT_SHIFT);
> xhci_ring_free(xhci, cur_ring);
> stream_info->stream_rings[cur_stream] = NULL;
> }
> @@ -697,7 +747,6 @@ void xhci_free_stream_info(struct xhci_hcd *xhci,
> {
> int cur_stream;
> struct xhci_ring *cur_ring;
> - dma_addr_t addr;
>
> if (!stream_info)
> return;
> @@ -706,9 +755,6 @@ void xhci_free_stream_info(struct xhci_hcd *xhci,
> cur_stream++) {
> cur_ring = stream_info->stream_rings[cur_stream];
> if (cur_ring) {
> - addr = cur_ring->first_seg->dma;
> - radix_tree_delete(&stream_info->trb_address_map,
> - addr >> TRB_SEGMENT_SHIFT);
> xhci_ring_free(xhci, cur_ring);
> stream_info->stream_rings[cur_stream] = NULL;
> }
> diff --git a/drivers/usb/host/xhci.h b/drivers/usb/host/xhci.h
> index 289fbfb..737dcc1 100644
> --- a/drivers/usb/host/xhci.h
> +++ b/drivers/usb/host/xhci.h
> @@ -1334,6 +1334,7 @@ struct xhci_ring {
> unsigned int num_trbs_free_temp;
> enum xhci_ring_type type;
> bool last_td_was_short;
> + struct radix_tree_root *trb_address_map;
> };
>
> struct xhci_erst_entry {
> --
> 1.8.3.3
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-usb" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH] xhci: Remove segments from radix tree on failed insert.
2013-10-17 18:40 ` Sarah Sharp
@ 2013-10-17 19:44 ` Sarah Sharp
2013-10-17 21:12 ` Hans de Goede
0 siblings, 1 reply; 12+ messages in thread
From: Sarah Sharp @ 2013-10-17 19:44 UTC (permalink / raw)
To: Gerd Hoffmann, Hans de Goede
Cc: Jan Kara, Andrew Morton, linux-kernel, linux-usb
If we're expanding a stream ring, we want to make sure we can add those
ring segments to the radix tree that maps segments to ring pointers.
Try the radix tree insert after the new ring segments have been allocated
(the last segment in the new ring chunk will point to the first newly
allocated segment), but before the new ring segments are linked into the
old ring.
If insert fails on any one segment, remove each segment from the radix
tree, deallocate the new segments, and return. Otherwise, link the new
segments into the tree.
Signed-off-by: Sarah Sharp <sarah.a.sharp@linux.intel.com>
---
Something like this. It's ugly, but it compiles. I haven't tested it.
Hans, can you review and test this?
Sarah Sharp
drivers/usb/host/xhci-mem.c | 106 +++++++++++++++++++++++++++++++++-----------
1 file changed, 80 insertions(+), 26 deletions(-)
diff --git a/drivers/usb/host/xhci-mem.c b/drivers/usb/host/xhci-mem.c
index a455c56..6ce8d31 100644
--- a/drivers/usb/host/xhci-mem.c
+++ b/drivers/usb/host/xhci-mem.c
@@ -180,53 +180,98 @@ static void xhci_link_rings(struct xhci_hcd *xhci, struct xhci_ring *ring,
* extended systems (where the DMA address can be bigger than 32-bits),
* if we allow the PCI dma mask to be bigger than 32-bits. So don't do that.
*/
-static int xhci_update_stream_mapping(struct xhci_ring *ring, gfp_t mem_flags)
+static int xhci_insert_segment_mapping(struct radix_tree_root *trb_address_map,
+ struct xhci_ring *ring,
+ struct xhci_segment *seg,
+ gfp_t mem_flags)
{
- struct xhci_segment *seg;
unsigned long key;
int ret;
- if (WARN_ON_ONCE(ring->trb_address_map == NULL))
+ key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
+ /* Skip any segments that were already added. */
+ if (radix_tree_lookup(trb_address_map, key))
return 0;
- seg = ring->first_seg;
- do {
- key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
- /* Skip any segments that were already added. */
- if (radix_tree_lookup(ring->trb_address_map, key))
- continue;
+ ret = radix_tree_maybe_preload(mem_flags);
+ if (ret)
+ return ret;
+ ret = radix_tree_insert(trb_address_map,
+ key, ring);
+ radix_tree_preload_end();
+ return ret;
+}
- ret = radix_tree_maybe_preload(mem_flags);
- if (ret)
- return ret;
- ret = radix_tree_insert(ring->trb_address_map,
- key, ring);
- radix_tree_preload_end();
+static void xhci_remove_segment_mapping(struct radix_tree_root *trb_address_map,
+ struct xhci_segment *seg)
+{
+ unsigned long key;
+
+ key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
+ if (radix_tree_lookup(trb_address_map, key))
+ radix_tree_delete(trb_address_map, key);
+}
+
+static int xhci_update_stream_segment_mapping(
+ struct radix_tree_root *trb_address_map,
+ struct xhci_ring *ring,
+ struct xhci_segment *first_seg,
+ struct xhci_segment *last_seg,
+ gfp_t mem_flags)
+{
+ struct xhci_segment *seg;
+ struct xhci_segment *failed_seg;
+ int ret;
+
+ if (WARN_ON_ONCE(trb_address_map == NULL))
+ return 0;
+
+ seg = first_seg;
+ do {
+ ret = xhci_insert_segment_mapping(trb_address_map,
+ ring, seg, mem_flags);
if (ret)
- return ret;
+ goto remove_streams;
+ if (seg == last_seg)
+ return 0;
seg = seg->next;
- } while (seg != ring->first_seg);
+ } while (seg != first_seg);
return 0;
+
+remove_streams:
+ failed_seg = seg;
+ seg = first_seg;
+ do {
+ xhci_remove_segment_mapping(trb_address_map, seg);
+ if (seg == failed_seg)
+ return ret;
+ seg = seg->next;
+ } while (seg != first_seg);
+
+ return ret;
}
static void xhci_remove_stream_mapping(struct xhci_ring *ring)
{
struct xhci_segment *seg;
- unsigned long key;
if (WARN_ON_ONCE(ring->trb_address_map == NULL))
return;
seg = ring->first_seg;
do {
- key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
- if (radix_tree_lookup(ring->trb_address_map, key))
- radix_tree_delete(ring->trb_address_map, key);
+ xhci_remove_segment_mapping(ring->trb_address_map, seg);
seg = seg->next;
} while (seg != ring->first_seg);
}
+static int xhci_update_stream_mapping(struct xhci_ring *ring, gfp_t mem_flags)
+{
+ return xhci_update_stream_segment_mapping(ring->trb_address_map, ring,
+ ring->first_seg, ring->last_seg, mem_flags);
+}
+
/* XXX: Do we need the hcd structure in all these functions? */
void xhci_ring_free(struct xhci_hcd *xhci, struct xhci_ring *ring)
{
@@ -429,16 +474,25 @@ int xhci_ring_expansion(struct xhci_hcd *xhci, struct xhci_ring *ring,
if (ret)
return -ENOMEM;
+ ret = xhci_update_stream_segment_mapping(ring->trb_address_map, ring,
+ first, last, flags);
+ if (ret) {
+ struct xhci_segment *next;
+ do {
+ next = first->next;
+ xhci_segment_free(xhci, first);
+ if (first == last)
+ break;
+ first = next;
+ } while (true);
+ return ret;
+ }
+
xhci_link_rings(xhci, ring, first, last, num_segs);
xhci_dbg_trace(xhci, trace_xhci_dbg_ring_expansion,
"ring expansion succeed, now has %d segments",
ring->num_segs);
- if (ring->type == TYPE_STREAM) {
- ret = xhci_update_stream_mapping(ring, flags);
- WARN_ON(ret); /* FIXME */
- }
-
return 0;
}
--
1.8.3.3
^ permalink raw reply related [flat|nested] 12+ messages in thread* Re: [PATCH] xhci: Remove segments from radix tree on failed insert.
2013-10-17 19:44 ` [PATCH] xhci: Remove segments from radix tree on failed insert Sarah Sharp
@ 2013-10-17 21:12 ` Hans de Goede
0 siblings, 0 replies; 12+ messages in thread
From: Hans de Goede @ 2013-10-17 21:12 UTC (permalink / raw)
To: Sarah Sharp, Gerd Hoffmann
Cc: Jan Kara, Andrew Morton, linux-kernel, linux-usb
Hi,
On 10/17/2013 09:44 PM, Sarah Sharp wrote:
> If we're expanding a stream ring, we want to make sure we can add those
> ring segments to the radix tree that maps segments to ring pointers.
> Try the radix tree insert after the new ring segments have been allocated
> (the last segment in the new ring chunk will point to the first newly
> allocated segment), but before the new ring segments are linked into the
> old ring.
>
> If insert fails on any one segment, remove each segment from the radix
> tree, deallocate the new segments, and return. Otherwise, link the new
> segments into the tree.
>
> Signed-off-by: Sarah Sharp <sarah.a.sharp@linux.intel.com>
> ---
>
> Something like this.
Thanks for working on this.
> It's ugly, but it compiles. I haven't tested it.
> Hans, can you review and test this?
Reviewed, I've one small nitpick, see inline comments, other then that it looks
good, and I don't find it all that ugly :)
I've also run various tests and it seems to work as advertised (I've not
managed to trigger the error path though AFAIK).
Acked-by: Hans de Goede <hdegoede@redhat.com>
>
> Sarah Sharp
>
> drivers/usb/host/xhci-mem.c | 106 +++++++++++++++++++++++++++++++++-----------
> 1 file changed, 80 insertions(+), 26 deletions(-)
>
> diff --git a/drivers/usb/host/xhci-mem.c b/drivers/usb/host/xhci-mem.c
> index a455c56..6ce8d31 100644
> --- a/drivers/usb/host/xhci-mem.c
> +++ b/drivers/usb/host/xhci-mem.c
> @@ -180,53 +180,98 @@ static void xhci_link_rings(struct xhci_hcd *xhci, struct xhci_ring *ring,
> * extended systems (where the DMA address can be bigger than 32-bits),
> * if we allow the PCI dma mask to be bigger than 32-bits. So don't do that.
> */
> -static int xhci_update_stream_mapping(struct xhci_ring *ring, gfp_t mem_flags)
> +static int xhci_insert_segment_mapping(struct radix_tree_root *trb_address_map,
> + struct xhci_ring *ring,
> + struct xhci_segment *seg,
> + gfp_t mem_flags)
> {
> - struct xhci_segment *seg;
> unsigned long key;
> int ret;
>
> - if (WARN_ON_ONCE(ring->trb_address_map == NULL))
> + key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
> + /* Skip any segments that were already added. */
> + if (radix_tree_lookup(trb_address_map, key))
> return 0;
>
> - seg = ring->first_seg;
> - do {
> - key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
> - /* Skip any segments that were already added. */
> - if (radix_tree_lookup(ring->trb_address_map, key))
> - continue;
> + ret = radix_tree_maybe_preload(mem_flags);
> + if (ret)
> + return ret;
> + ret = radix_tree_insert(trb_address_map,
> + key, ring);
> + radix_tree_preload_end();
> + return ret;
> +}
>
> - ret = radix_tree_maybe_preload(mem_flags);
> - if (ret)
> - return ret;
> - ret = radix_tree_insert(ring->trb_address_map,
> - key, ring);
> - radix_tree_preload_end();
> +static void xhci_remove_segment_mapping(struct radix_tree_root *trb_address_map,
> + struct xhci_segment *seg)
> +{
> + unsigned long key;
> +
> + key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
> + if (radix_tree_lookup(trb_address_map, key))
> + radix_tree_delete(trb_address_map, key);
> +}
> +
> +static int xhci_update_stream_segment_mapping(
> + struct radix_tree_root *trb_address_map,
> + struct xhci_ring *ring,
> + struct xhci_segment *first_seg,
> + struct xhci_segment *last_seg,
> + gfp_t mem_flags)
> +{
> + struct xhci_segment *seg;
> + struct xhci_segment *failed_seg;
> + int ret;
> +
> + if (WARN_ON_ONCE(trb_address_map == NULL))
> + return 0;
> +
> + seg = first_seg;
> + do {
> + ret = xhci_insert_segment_mapping(trb_address_map,
> + ring, seg, mem_flags);
> if (ret)
> - return ret;
> + goto remove_streams;
> + if (seg == last_seg)
> + return 0;
> seg = seg->next;
> - } while (seg != ring->first_seg);
> + } while (seg != first_seg);
The while here tests for looping round, but that should never
happen, IMHO using do {} while (true); here would be more clear,
and also consistent with how the tear-down is done in the
error case in xhci_ring_expansion.
>
> return 0;
> +
> +remove_streams:
> + failed_seg = seg;
> + seg = first_seg;
> + do {
> + xhci_remove_segment_mapping(trb_address_map, seg);
> + if (seg == failed_seg)
> + return ret;
> + seg = seg->next;
> + } while (seg != first_seg);
And I would also prefer "} while (true};" here for the same reasons.
> +
> + return ret;
> }
>
> static void xhci_remove_stream_mapping(struct xhci_ring *ring)
> {
> struct xhci_segment *seg;
> - unsigned long key;
>
> if (WARN_ON_ONCE(ring->trb_address_map == NULL))
> return;
>
> seg = ring->first_seg;
> do {
> - key = (unsigned long)(seg->dma >> TRB_SEGMENT_SHIFT);
> - if (radix_tree_lookup(ring->trb_address_map, key))
> - radix_tree_delete(ring->trb_address_map, key);
> + xhci_remove_segment_mapping(ring->trb_address_map, seg);
> seg = seg->next;
> } while (seg != ring->first_seg);
> }
>
> +static int xhci_update_stream_mapping(struct xhci_ring *ring, gfp_t mem_flags)
> +{
> + return xhci_update_stream_segment_mapping(ring->trb_address_map, ring,
> + ring->first_seg, ring->last_seg, mem_flags);
> +}
> +
> /* XXX: Do we need the hcd structure in all these functions? */
> void xhci_ring_free(struct xhci_hcd *xhci, struct xhci_ring *ring)
> {
> @@ -429,16 +474,25 @@ int xhci_ring_expansion(struct xhci_hcd *xhci, struct xhci_ring *ring,
> if (ret)
> return -ENOMEM;
>
> + ret = xhci_update_stream_segment_mapping(ring->trb_address_map, ring,
> + first, last, flags);
> + if (ret) {
> + struct xhci_segment *next;
> + do {
> + next = first->next;
> + xhci_segment_free(xhci, first);
> + if (first == last)
> + break;
> + first = next;
> + } while (true);
> + return ret;
> + }
> +
> xhci_link_rings(xhci, ring, first, last, num_segs);
> xhci_dbg_trace(xhci, trace_xhci_dbg_ring_expansion,
> "ring expansion succeed, now has %d segments",
> ring->num_segs);
>
> - if (ring->type == TYPE_STREAM) {
> - ret = xhci_update_stream_mapping(ring, flags);
> - WARN_ON(ret); /* FIXME */
> - }
> -
> return 0;
> }
>
>
Regards,
Hans
^ permalink raw reply [flat|nested] 12+ messages in thread