From: Peter Xu <peterx@redhat.com> To: "Eugenio Pérez" <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-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@lists.linux-foundation.org, Parav Pandit <parav@mellanox.com> Subject: Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc Date: Tue, 23 Nov 2021 14:56:52 +0800 [thread overview] Message-ID: <YZyQtF0SIPcVZI+v@xz-m1.local> (raw) In-Reply-To: <20211029183525.1776416-24-eperezma@redhat.com> Hi, Eugenio, Sorry for the super late response. On Fri, Oct 29, 2021 at 08:35:22PM +0200, Eugenio Pérez wrote: [...] > +int iova_tree_alloc(IOVATree *tree, DMAMap *map, hwaddr iova_begin, > + hwaddr iova_last) > +{ > + struct IOVATreeAllocArgs args = { > + .new_size = map->size, > + .iova_begin = iova_begin, > + .iova_last = iova_last, > + }; > + > + if (iova_begin == 0) { > + /* Some devices does not like addr 0 */ > + iova_begin += qemu_real_host_page_size; > + } Any explanation of why zero is not welcomed? It would be great if we can move this out of iova-tree.c, because that doesn't look like a good place to, e.g. reference qemu_real_host_page_size, anyways. The caller can simply pass in qemu_real_host_page_size as iova_begin when needed (and I highly doubt it'll be a must for all iova-tree users..) > + > + assert(iova_begin < iova_last); > + > + /* > + * Find a valid hole for the mapping > + * > + * Assuming low iova_begin, so no need to do a binary search to > + * locate the first node. > + * > + * TODO: We can improve the search speed if we save the beginning and the > + * end of holes, so we don't iterate over the previous saved ones. > + * > + * TODO: Replace all this with g_tree_node_first/next/last when available > + * (from glib since 2.68). To do it with g_tree_foreach complicates the > + * code a lot. > + * > + */ > + g_tree_foreach(tree->tree, iova_tree_alloc_traverse, &args); > + if (!iova_tree_alloc_map_in_hole(&args)) { > + /* > + * 2nd try: Last iteration left args->right as the last DMAMap. But > + * (right, end) hole needs to be checked too > + */ > + iova_tree_alloc_args_iterate(&args, NULL); > + if (!iova_tree_alloc_map_in_hole(&args)) { > + return IOVA_ERR_NOMEM; > + } > + } > + > + map->iova = MAX(iova_begin, > + args.hole_left ? > + args.hole_left->iova + args.hole_left->size + 1 : 0); > + return iova_tree_insert(tree, map); > +} Re the algorithm - I totally agree Jason's version is much better. 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 Pérez" <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-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@lists.linux-foundation.org, Parav Pandit <parav@mellanox.com> Subject: Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc Date: Tue, 23 Nov 2021 14:56:52 +0800 [thread overview] Message-ID: <YZyQtF0SIPcVZI+v@xz-m1.local> (raw) In-Reply-To: <20211029183525.1776416-24-eperezma@redhat.com> Hi, Eugenio, Sorry for the super late response. On Fri, Oct 29, 2021 at 08:35:22PM +0200, Eugenio Pérez wrote: [...] > +int iova_tree_alloc(IOVATree *tree, DMAMap *map, hwaddr iova_begin, > + hwaddr iova_last) > +{ > + struct IOVATreeAllocArgs args = { > + .new_size = map->size, > + .iova_begin = iova_begin, > + .iova_last = iova_last, > + }; > + > + if (iova_begin == 0) { > + /* Some devices does not like addr 0 */ > + iova_begin += qemu_real_host_page_size; > + } Any explanation of why zero is not welcomed? It would be great if we can move this out of iova-tree.c, because that doesn't look like a good place to, e.g. reference qemu_real_host_page_size, anyways. The caller can simply pass in qemu_real_host_page_size as iova_begin when needed (and I highly doubt it'll be a must for all iova-tree users..) > + > + assert(iova_begin < iova_last); > + > + /* > + * Find a valid hole for the mapping > + * > + * Assuming low iova_begin, so no need to do a binary search to > + * locate the first node. > + * > + * TODO: We can improve the search speed if we save the beginning and the > + * end of holes, so we don't iterate over the previous saved ones. > + * > + * TODO: Replace all this with g_tree_node_first/next/last when available > + * (from glib since 2.68). To do it with g_tree_foreach complicates the > + * code a lot. > + * > + */ > + g_tree_foreach(tree->tree, iova_tree_alloc_traverse, &args); > + if (!iova_tree_alloc_map_in_hole(&args)) { > + /* > + * 2nd try: Last iteration left args->right as the last DMAMap. But > + * (right, end) hole needs to be checked too > + */ > + iova_tree_alloc_args_iterate(&args, NULL); > + if (!iova_tree_alloc_map_in_hole(&args)) { > + return IOVA_ERR_NOMEM; > + } > + } > + > + map->iova = MAX(iova_begin, > + args.hole_left ? > + args.hole_left->iova + args.hole_left->size + 1 : 0); > + return iova_tree_insert(tree, map); > +} Re the algorithm - I totally agree Jason's version is much better. Thanks, -- Peter Xu
next prev parent reply other threads:[~2021-11-23 6:57 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 [this message] 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 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=YZyQtF0SIPcVZI+v@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.