From: Peter Xu <peterx@redhat.com> To: Eugenio Perez Martin <eperezma@redhat.com> Cc: Laurent Vivier <lvivier@redhat.com>, Eduardo Habkost <ehabkost@redhat.com>, "Michael S. Tsirkin" <mst@redhat.com>, Richard Henderson <richard.henderson@linaro.org>, qemu-level <qemu-devel@nongnu.org>, Markus Armbruster <armbru@redhat.com>, Stefan Hajnoczi <stefanha@redhat.com>, Xiao W Wang <xiao.w.wang@intel.com>, Harpreet Singh Anand <hanand@xilinx.com>, Eli Cohen <eli@mellanox.com>, Paolo Bonzini <pbonzini@redhat.com>, Eric Blake <eblake@redhat.com>, virtualization <virtualization@lists.linux-foundation.org>, Parav Pandit <parav@mellanox.com> Subject: Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc Date: Thu, 27 Jan 2022 19:25:22 +0800 [thread overview] Message-ID: <YfKBIuTzsoOF9Mj5@xz-m1.local> (raw) In-Reply-To: <CAJaqyWd52cXWHnLsgo=kP2Z7=VG6YKtxFGhTe7OamfYcZxhz6w@mail.gmail.com> On Thu, Jan 27, 2022 at 11:09:44AM +0100, Eugenio Perez Martin wrote: > > > +/** > > > + * Try to accomodate a map of size ret->size in a hole between > > > + * max(end(hole_left), iova_start). > > > > I think this functions need the most comments, and above sentence is more or > > less not sounding correct... My try... > > > > /* > > * Try to find an unallocated IOVA range between LEFT and RIGHT elements. > > * > > * There're three cases: > > * > > * (1) When LEFT==NULL, RIGHT must be non-NULL and it means we're iterating at > > * the 1st element. > > * > > * (2) When RIGHT==NULL, LEFT must be non-NULL and it means we're iterating at > > * the last element. > > * > > * (3) When both LEFT and RIGHT are non-NULL, this is the most common case, > > * we'll try to find a hole between LEFT and RIGHT mapping. > > */ > > > > This is also called with left == NULL and right == NULL in the first > allocation with an empty tree. This allows iova_tree_alloc to have the > same code path both if the three is empty or not. > > But I can add the use cases in the doc for sure. Ah, right. > > > > + * > > > + * @args Arguments to allocation > > > + */ > > > +static bool iova_tree_alloc_map_in_hole(const struct IOVATreeAllocArgs *args) > > > +{ > > > + const DMAMap *left = args->hole_left, *right = args->hole_right; > > > + uint64_t hole_start, hole_last; > > > + > > > + if (right && right->iova + right->size < args->iova_begin) { > > > + return false; > > > + } > > > + > > > + if (left && left->iova > args->iova_last) { > > > + return false; > > > + } > > > + > > > + hole_start = MAX(left ? left->iova + left->size + 1 : 0, args->iova_begin); > > > + hole_last = MIN(right ? right->iova : HWADDR_MAX, args->iova_last); > > > > I assume these values should be always inclusive, hence > > > > s/right->iova/right->iova + 1/ > > > > ? > > > > Right, it is confusing the way it's written. But I think it should be > right->iova - 1 in any case to make it the hole last element, isn't > it? I was thinking "-1" but I failed to make it coherent with the thought when typing.. Heh. > > Would it work better to rename variable hole_last to hole_end? If not, > we have a special case of the second allocation when iova_begin == 0: > - We successfully allocate a DMAMap of size N. By the way the > algorithm works, it starts at 0, so [0, N] is allocated. If we're always talking about inclusive ranges, shouldn't it be [0, N-1]? > - We try to allocate a second one of size M. At the first iteration, > "right" is the previously allocated DMAMap. > Using the -1 trick we get hole_end == HWADDR_MAX. I'm not sure I get the point, but both naming look fine to me. As long as we use inclusive ranges, then hole_end/last will be limited to HWADDR_MAX. > > > +static gboolean iova_tree_alloc_traverse(gpointer key, gpointer value, > > > + gpointer pargs) > > > +{ > > > + struct IOVATreeAllocArgs *args = pargs; > > > + DMAMap *node = value; > > > + > > > + assert(key == value); > > > + > > > + iova_tree_alloc_args_iterate(args, node); > > > + if (args->hole_left && args->hole_left->iova > args->iova_last) { > > > > IMHO this check is redundant and can be dropped, as it's already done in > > iova_tree_alloc_map_in_hole(). > > > > Assuming we add "iova_found" to iova_tree_alloc_map_in_hole to > IOVATreeAllocArgs as you propose, it returns true if we are able to > allocate a DMAMap entry, so no more iterations are needed. But if it > returns false, it simply means that DMAMap cannot be allocated between > left (or iova_begin) and right (iova_end). It doesn't tell if you can > keep iterating or not. In other words, false == keep iterating if you > can. > > This other check signals the end of the available hole, and to avoid > iterating beyond iova_last in the (unlikely?) case we have more nodes > to iterate beyond that. > > I'll try to make it more explicit. Makes sense. Comment works. Thanks, -- Peter Xu _______________________________________________ Virtualization mailing list Virtualization@lists.linux-foundation.org https://lists.linuxfoundation.org/mailman/listinfo/virtualization
WARNING: multiple messages have this Message-ID (diff)
From: Peter Xu <peterx@redhat.com> To: Eugenio Perez Martin <eperezma@redhat.com> Cc: Laurent Vivier <lvivier@redhat.com>, Eduardo Habkost <ehabkost@redhat.com>, "Michael S. Tsirkin" <mst@redhat.com>, Jason Wang <jasowang@redhat.com>, Juan Quintela <quintela@redhat.com>, Richard Henderson <richard.henderson@linaro.org>, qemu-level <qemu-devel@nongnu.org>, Markus Armbruster <armbru@redhat.com>, Stefan Hajnoczi <stefanha@redhat.com>, Xiao W Wang <xiao.w.wang@intel.com>, Harpreet Singh Anand <hanand@xilinx.com>, Eli Cohen <eli@mellanox.com>, Paolo Bonzini <pbonzini@redhat.com>, Stefano Garzarella <sgarzare@redhat.com>, Eric Blake <eblake@redhat.com>, virtualization <virtualization@lists.linux-foundation.org>, Parav Pandit <parav@mellanox.com> Subject: Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc Date: Thu, 27 Jan 2022 19:25:22 +0800 [thread overview] Message-ID: <YfKBIuTzsoOF9Mj5@xz-m1.local> (raw) In-Reply-To: <CAJaqyWd52cXWHnLsgo=kP2Z7=VG6YKtxFGhTe7OamfYcZxhz6w@mail.gmail.com> On Thu, Jan 27, 2022 at 11:09:44AM +0100, Eugenio Perez Martin wrote: > > > +/** > > > + * Try to accomodate a map of size ret->size in a hole between > > > + * max(end(hole_left), iova_start). > > > > I think this functions need the most comments, and above sentence is more or > > less not sounding correct... My try... > > > > /* > > * Try to find an unallocated IOVA range between LEFT and RIGHT elements. > > * > > * There're three cases: > > * > > * (1) When LEFT==NULL, RIGHT must be non-NULL and it means we're iterating at > > * the 1st element. > > * > > * (2) When RIGHT==NULL, LEFT must be non-NULL and it means we're iterating at > > * the last element. > > * > > * (3) When both LEFT and RIGHT are non-NULL, this is the most common case, > > * we'll try to find a hole between LEFT and RIGHT mapping. > > */ > > > > This is also called with left == NULL and right == NULL in the first > allocation with an empty tree. This allows iova_tree_alloc to have the > same code path both if the three is empty or not. > > But I can add the use cases in the doc for sure. Ah, right. > > > > + * > > > + * @args Arguments to allocation > > > + */ > > > +static bool iova_tree_alloc_map_in_hole(const struct IOVATreeAllocArgs *args) > > > +{ > > > + const DMAMap *left = args->hole_left, *right = args->hole_right; > > > + uint64_t hole_start, hole_last; > > > + > > > + if (right && right->iova + right->size < args->iova_begin) { > > > + return false; > > > + } > > > + > > > + if (left && left->iova > args->iova_last) { > > > + return false; > > > + } > > > + > > > + hole_start = MAX(left ? left->iova + left->size + 1 : 0, args->iova_begin); > > > + hole_last = MIN(right ? right->iova : HWADDR_MAX, args->iova_last); > > > > I assume these values should be always inclusive, hence > > > > s/right->iova/right->iova + 1/ > > > > ? > > > > Right, it is confusing the way it's written. But I think it should be > right->iova - 1 in any case to make it the hole last element, isn't > it? I was thinking "-1" but I failed to make it coherent with the thought when typing.. Heh. > > Would it work better to rename variable hole_last to hole_end? If not, > we have a special case of the second allocation when iova_begin == 0: > - We successfully allocate a DMAMap of size N. By the way the > algorithm works, it starts at 0, so [0, N] is allocated. If we're always talking about inclusive ranges, shouldn't it be [0, N-1]? > - We try to allocate a second one of size M. At the first iteration, > "right" is the previously allocated DMAMap. > Using the -1 trick we get hole_end == HWADDR_MAX. I'm not sure I get the point, but both naming look fine to me. As long as we use inclusive ranges, then hole_end/last will be limited to HWADDR_MAX. > > > +static gboolean iova_tree_alloc_traverse(gpointer key, gpointer value, > > > + gpointer pargs) > > > +{ > > > + struct IOVATreeAllocArgs *args = pargs; > > > + DMAMap *node = value; > > > + > > > + assert(key == value); > > > + > > > + iova_tree_alloc_args_iterate(args, node); > > > + if (args->hole_left && args->hole_left->iova > args->iova_last) { > > > > IMHO this check is redundant and can be dropped, as it's already done in > > iova_tree_alloc_map_in_hole(). > > > > Assuming we add "iova_found" to iova_tree_alloc_map_in_hole to > IOVATreeAllocArgs as you propose, it returns true if we are able to > allocate a DMAMap entry, so no more iterations are needed. But if it > returns false, it simply means that DMAMap cannot be allocated between > left (or iova_begin) and right (iova_end). It doesn't tell if you can > keep iterating or not. In other words, false == keep iterating if you > can. > > This other check signals the end of the available hole, and to avoid > iterating beyond iova_last in the (unlikely?) case we have more nodes > to iterate beyond that. > > I'll try to make it more explicit. Makes sense. Comment works. Thanks, -- Peter Xu
next prev parent reply other threads:[~2022-01-27 11:25 UTC|newest] Thread overview: 82+ messages / expand[flat|nested] mbox.gz Atom feed top 2021-10-29 18:34 [RFC PATCH v5 00/26] vDPA shadow virtqueue Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 01/26] util: Make some iova_tree parameters const Eugenio Pérez 2021-10-31 18:59 ` Juan Quintela 2021-10-31 18:59 ` Juan Quintela 2021-11-01 8:20 ` Eugenio Perez Martin 2021-10-29 18:35 ` [RFC PATCH v5 02/26] vhost: Fix last queue index of devices with no cvq Eugenio Pérez 2021-11-02 7:25 ` Juan Quintela 2021-11-02 7:25 ` Juan Quintela 2021-11-02 7:32 ` Michael S. Tsirkin 2021-11-02 7:32 ` Michael S. Tsirkin 2021-11-02 7:39 ` Juan Quintela 2021-11-02 7:39 ` Juan Quintela 2021-11-02 8:34 ` Eugenio Perez Martin 2021-11-02 7:40 ` Juan Quintela 2021-11-02 7:40 ` Juan Quintela 2021-10-29 18:35 ` [RFC PATCH v5 03/26] virtio: Add VIRTIO_F_QUEUE_STATE Eugenio Pérez 2021-11-02 4:57 ` Jason Wang 2021-11-02 4:57 ` Jason Wang 2021-10-29 18:35 ` [RFC PATCH v5 04/26] virtio-net: Honor VIRTIO_CONFIG_S_DEVICE_STOPPED Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 05/26] vhost: Add x-vhost-set-shadow-vq qmp Eugenio Pérez 2021-11-02 7:36 ` Juan Quintela 2021-11-02 7:36 ` Juan Quintela 2021-11-02 8:29 ` Eugenio Perez Martin 2021-10-29 18:35 ` [RFC PATCH v5 06/26] vhost: Add VhostShadowVirtqueue Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 07/26] vdpa: Save kick_fd in vhost-vdpa Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 08/26] vdpa: Add vhost_svq_get_dev_kick_notifier Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 09/26] vdpa: Add vhost_svq_set_svq_kick_fd Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 10/26] vhost: Add Shadow VirtQueue kick forwarding capabilities Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 11/26] vhost: Handle host notifiers in SVQ Eugenio Pérez 2021-11-02 7:54 ` Jason Wang 2021-11-02 7:54 ` Jason Wang 2021-11-02 8:46 ` Eugenio Perez Martin [not found] ` <CACGkMEvOxUMo1WA4tUfDhw+FOJVW87JJGPw=U3JvUSQTU_ogWQ@mail.gmail.com> [not found] ` <CAJaqyWd4DQwRSL5StCft+3-uq12TW5x1o4DN_YW97D0JzOr2XQ@mail.gmail.com> 2021-11-04 2:31 ` Jason Wang 2021-11-04 2:31 ` Jason Wang 2021-10-29 18:35 ` [RFC PATCH v5 12/26] vhost: Route guest->host notification through shadow virtqueue Eugenio Pérez 2021-11-02 5:36 ` Jason Wang 2021-11-02 5:36 ` Jason Wang 2021-11-02 7:35 ` Eugenio Perez Martin 2021-10-29 18:35 ` [RFC PATCH v5 13/26] Add vhost_svq_get_svq_call_notifier Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 14/26] Add vhost_svq_set_guest_call_notifier Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 15/26] vdpa: Save call_fd in vhost-vdpa Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 16/26] vhost-vdpa: Take into account SVQ in vhost_vdpa_set_vring_call Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 17/26] vhost: Route host->guest notification through shadow virtqueue Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 18/26] virtio: Add vhost_shadow_vq_get_vring_addr Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 19/26] vdpa: ack VIRTIO_F_QUEUE_STATE if device supports it Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 20/26] vhost: Add vhost_svq_valid_device_features to shadow vq Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 21/26] vhost: Add vhost_svq_valid_guest_features " Eugenio Pérez 2021-11-02 5:25 ` Jason Wang 2021-11-02 5:25 ` Jason Wang 2021-11-02 8:09 ` Eugenio Perez Martin 2021-11-03 3:18 ` Jason Wang 2021-11-03 3:18 ` Jason Wang 2021-11-03 7:43 ` Eugenio Perez Martin 2021-11-04 2:34 ` Jason Wang 2021-11-04 2:34 ` Jason Wang 2021-10-29 18:35 ` [RFC PATCH v5 22/26] vhost: Shadow virtqueue buffers forwarding Eugenio Pérez 2021-11-02 7:59 ` Jason Wang 2021-11-02 7:59 ` Jason Wang 2021-11-02 10:22 ` Eugenio Perez Martin 2021-10-29 18:35 ` [RFC PATCH v5 23/26] util: Add iova_tree_alloc Eugenio Pérez 2021-11-02 6:35 ` Jason Wang 2021-11-02 6:35 ` Jason Wang 2021-11-02 8:28 ` Eugenio Perez Martin 2021-11-03 3:10 ` Jason Wang 2021-11-03 3:10 ` Jason Wang 2021-11-03 7:41 ` Eugenio Perez Martin 2021-11-23 6:56 ` Peter Xu 2021-11-23 6:56 ` Peter Xu 2021-11-23 7:08 ` Eugenio Perez Martin 2022-01-27 8:57 ` Peter Xu 2022-01-27 8:57 ` Peter Xu 2022-01-27 10:09 ` Eugenio Perez Martin 2022-01-27 11:25 ` Peter Xu [this message] 2022-01-27 11:25 ` Peter Xu 2022-01-27 11:45 ` Eugenio Perez Martin 2021-10-29 18:35 ` [RFC PATCH v5 24/26] vhost: Add VhostIOVATree Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 25/26] vhost: Use a tree to store memory mappings Eugenio Pérez 2021-10-29 18:35 ` [RFC PATCH v5 26/26] vdpa: Add custom IOTLB translations to SVQ Eugenio Pérez 2021-11-01 9:06 ` [RFC PATCH v5 00/26] vDPA shadow virtqueue Eugenio Perez Martin 2021-11-02 4:25 ` Jason Wang 2021-11-02 4:25 ` Jason Wang 2021-11-02 11:21 ` Eugenio Perez Martin
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=YfKBIuTzsoOF9Mj5@xz-m1.local \ --to=peterx@redhat.com \ --cc=armbru@redhat.com \ --cc=eblake@redhat.com \ --cc=ehabkost@redhat.com \ --cc=eli@mellanox.com \ --cc=eperezma@redhat.com \ --cc=hanand@xilinx.com \ --cc=lvivier@redhat.com \ --cc=mst@redhat.com \ --cc=parav@mellanox.com \ --cc=pbonzini@redhat.com \ --cc=qemu-devel@nongnu.org \ --cc=richard.henderson@linaro.org \ --cc=stefanha@redhat.com \ --cc=virtualization@lists.linux-foundation.org \ --cc=xiao.w.wang@intel.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.