Re: [PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
On Fri, Jun 29, 2018 at 05:25:56PM +0200, Vitaly Kuznetsov wrote: > Roman Kagan writes: > > > On Fri, Jun 29, 2018 at 03:10:14PM +0200, Vitaly Kuznetsov wrote: > >> Roman Kagan writes: > >> > >> > On Fri, Jun 29, 2018 at 01:37:44PM +0200, Vitaly Kuznetsov wrote: > >> >> The problem we're trying to solve here is: with PV TLB flush and IPI we > >> >> need to walk through the supplied list of VP_INDEXes and get VCPU > >> >> ids. Usually they match. But in case they don't [...] > >> > > >> > Why wouldn't they *in practice*? Only if the userspace wanted to be > >> > funny and assigned VP_INDEXes randomly? I'm not sure we need to > >> > optimize for this case. > >> > >> Can someone please remind me why we allow userspace to change it in the > >> first place? > > > > I can ;) > > > > We used not to, and reported KVM's vcpu index as the VP_INDEX. However, > > later we realized that VP_INDEX needed to be persistent across > > migrations and otherwise also known to userspace. Relying on the kernel > > to always initialize its indices in the same order was unacceptable, and > > we came up with no better way of synchronizing VP_INDEX between the > > userspace and the kernel than to let the former to set it explicitly. > > > > However, this is basically a future-proofing feature; in practice, both > > QEMU and KVM initialize their indices in the same order. > > > Thanks! > > But in the theoretical case when these indices start to differ after > migration, users will notice a slowdown which will be hard to explain, > right? That's exactly why I suggested a warning on VP_INDEX != vcpu index in kvm_hv_set_msr. > Does it justify the need for vp_idx_to_vcpu_idx? I'd personally prefer being pointed at a scenario where this becomes relevant first. Roman.
Re: [PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
Roman Kagan writes: > On Fri, Jun 29, 2018 at 03:10:14PM +0200, Vitaly Kuznetsov wrote: >> Roman Kagan writes: >> >> > On Fri, Jun 29, 2018 at 01:37:44PM +0200, Vitaly Kuznetsov wrote: >> >> The problem we're trying to solve here is: with PV TLB flush and IPI we >> >> need to walk through the supplied list of VP_INDEXes and get VCPU >> >> ids. Usually they match. But in case they don't [...] >> > >> > Why wouldn't they *in practice*? Only if the userspace wanted to be >> > funny and assigned VP_INDEXes randomly? I'm not sure we need to >> > optimize for this case. >> >> Can someone please remind me why we allow userspace to change it in the >> first place? > > I can ;) > > We used not to, and reported KVM's vcpu index as the VP_INDEX. However, > later we realized that VP_INDEX needed to be persistent across > migrations and otherwise also known to userspace. Relying on the kernel > to always initialize its indices in the same order was unacceptable, and > we came up with no better way of synchronizing VP_INDEX between the > userspace and the kernel than to let the former to set it explicitly. > > However, this is basically a future-proofing feature; in practice, both > QEMU and KVM initialize their indices in the same order. Thanks! But in the theoretical case when these indices start to differ after migration, users will notice a slowdown which will be hard to explain, right? Does it justify the need for vp_idx_to_vcpu_idx? In any case I sent v3 with vp_idx_to_vcpu_idx dropped for now, hope Radim is OK with us de-coupling these discussions. -- Vitaly
Re: [PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
On Fri, Jun 29, 2018 at 03:10:14PM +0200, Vitaly Kuznetsov wrote: > Roman Kagan writes: > > > On Fri, Jun 29, 2018 at 01:37:44PM +0200, Vitaly Kuznetsov wrote: > >> The problem we're trying to solve here is: with PV TLB flush and IPI we > >> need to walk through the supplied list of VP_INDEXes and get VCPU > >> ids. Usually they match. But in case they don't [...] > > > > Why wouldn't they *in practice*? Only if the userspace wanted to be > > funny and assigned VP_INDEXes randomly? I'm not sure we need to > > optimize for this case. > > Can someone please remind me why we allow userspace to change it in the > first place? I can ;) We used not to, and reported KVM's vcpu index as the VP_INDEX. However, later we realized that VP_INDEX needed to be persistent across migrations and otherwise also known to userspace. Relying on the kernel to always initialize its indices in the same order was unacceptable, and we came up with no better way of synchronizing VP_INDEX between the userspace and the kernel than to let the former to set it explicitly. However, this is basically a future-proofing feature; in practice, both QEMU and KVM initialize their indices in the same order. Roman.
Re: [PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
Roman Kagan writes: > On Fri, Jun 29, 2018 at 01:37:44PM +0200, Vitaly Kuznetsov wrote: >> The problem we're trying to solve here is: with PV TLB flush and IPI we >> need to walk through the supplied list of VP_INDEXes and get VCPU >> ids. Usually they match. But in case they don't [...] > > Why wouldn't they *in practice*? Only if the userspace wanted to be > funny and assigned VP_INDEXes randomly? I'm not sure we need to > optimize for this case. Can someone please remind me why we allow userspace to change it in the first place? > > Note that the userspace can actually do nasty things with these > VP_INDEXes, like, say, have them non-unique. We need to be resilent to > it, but don't need to optimize for it. > > I think I'd rather have a warning in kvm_hv_set_msr if the VP_INDEX > being assigned is not equal to the vcpu index, and start worrying about > optimization only if this warning starts being triggered by real > hypervisor applications. > > Anyway I don't see an urgent need to bloat this patchset with optimizing > this translation; it can be done separately, if needed. Sure, I can use get_vcpu_by_vpidx() in the patchset pretending that is's always fast and if we find a valid case where it is not - we'll just optimize it later. Sounds sane to me. -- Vitaly
Re: [PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
On Fri, Jun 29, 2018 at 01:37:44PM +0200, Vitaly Kuznetsov wrote: > The problem we're trying to solve here is: with PV TLB flush and IPI we > need to walk through the supplied list of VP_INDEXes and get VCPU > ids. Usually they match. But in case they don't [...] Why wouldn't they *in practice*? Only if the userspace wanted to be funny and assigned VP_INDEXes randomly? I'm not sure we need to optimize for this case. Note that the userspace can actually do nasty things with these VP_INDEXes, like, say, have them non-unique. We need to be resilent to it, but don't need to optimize for it. I think I'd rather have a warning in kvm_hv_set_msr if the VP_INDEX being assigned is not equal to the vcpu index, and start worrying about optimization only if this warning starts being triggered by real hypervisor applications. Anyway I don't see an urgent need to bloat this patchset with optimizing this translation; it can be done separately, if needed. Roman.
Re: [PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
Roman Kagan writes:
> On Fri, Jun 29, 2018 at 12:26:23PM +0200, Vitaly Kuznetsov wrote:
>> Roman Kagan writes:
>>
>> > On Thu, Jun 28, 2018 at 03:53:10PM +0200, Vitaly Kuznetsov wrote:
>> >> While it is easy to get VP index from vCPU index the reverse task is hard.
>> >> Basically, to solve it we have to walk all vCPUs checking if their VP
>> >> index
>> >> matches. For hypercalls like HvFlushVirtualAddress{List,Space}* and the
>> >> upcoming HvSendSyntheticClusterIpi* where a single CPU may be specified in
>> >> the whole set this is obviously sub-optimal.
>> >>
>> >> As VP index can be set to anything <= U32_MAX by userspace using plain
>> >> [0..MAX_VP_INDEX] array is not a viable option. Use condensed sorted
>> >> array with logarithmic search complexity instead. Use RCU to make read
>> >> access as fast as possible and maintain atomicity of updates.
>> >
>> > Quoting TLFS 5.0C section 7.8.1:
>> >
>> >> Virtual processors are identified by using an index (VP index). The
>> >> maximum number of virtual processors per partition supported by the
>> >> current implementation of the hypervisor can be obtained through CPUID
>> >> leaf 0x4005. A virtual processor index must be less than the
>> >> maximum number of virtual processors per partition.
>> >
>> > so this is a dense index, and VP_INDEX >= KVM_MAX_VCPUS is invalid. I
>> > think we're better off enforcing this in kvm_hv_set_msr and keep the
>> > translation simple. If the algorithm in get_vcpu_by_vpidx is not good
>> > enough (and yes it can be made to return NULL early on vpidx >=
>> > KVM_MAX_VCPUS instead of taking the slow path) then a simple index array
>> > of KVM_MAX_VCPUS entries should certainly do.
>>
>> Sure, we can use pre-allocated [0..KVM_MAX_VCPUS] array instead and put
>> limits on what userspace can assign VP_INDEX to. Howver, while thinking
>> about it I decided to go with the more complex condensed array approach
>> because the tendency is for KVM_MAX_VCPUS to grow and we will be
>> pre-allocating more and more memory for no particular reason (so I think
>> even 'struct kvm_vcpu *vcpus[KVM_MAX_VCPUS]' in 'struct kvm' will need
>> to be converted to something else eventually).
>
> We're talking of kilobytes here. I guess this is going to be the least
> of the scalability problems.
Yes, kilobytes but per-VM.
>
>> Anyway, I'm flexible and if you think we should go this way now I'll do
>> this in v3. We can re-think this when we later decide to raise
>> KVM_MAX_VCPUS significantly.
>
> Although there's no strict requirement for that I think every sensible
> userspace will allocate VP_INDEX linearly resulting in it being equal to
> KVM's vcpu index. So we've yet to see a case where get_vcpu_by_vpidx
> doesn't take the fast path. If it ever starts appearing in the profiles
> we may consider optimiziing it but ATM I don't even think introducing
> the translation array is justified.
It was Radim who suggested it in the first place :-)
The problem we're trying to solve here is: with PV TLB flush and IPI we
need to walk through the supplied list of VP_INDEXes and get VCPU
ids. Usually they match. But in case they don't we'll fall back to full
scan for every VP_INDEX in the supplied list. Now let's say we have 128
CPUs. We'll need to perform up to 128 * 128 extra comparisons on every
hypercall. Not good. So instead of using get_vcpu_by_vpidx() I opted for
walking the whole VCPU list and checking if VPU's VP_INDEX is in the
supplied set. This way we end up with 128 comparisons in the example
above (worst case scenarion). However, we lose in simple scenarios like
only 1 VP_INDEX was specified in the set: we'll still need to walk the
whole list. So having the translation array (one way or another) is IMO
justified.
--
Vitaly
Re: [PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
On Fri, Jun 29, 2018 at 12:26:23PM +0200, Vitaly Kuznetsov wrote:
> Roman Kagan writes:
>
> > On Thu, Jun 28, 2018 at 03:53:10PM +0200, Vitaly Kuznetsov wrote:
> >> While it is easy to get VP index from vCPU index the reverse task is hard.
> >> Basically, to solve it we have to walk all vCPUs checking if their VP index
> >> matches. For hypercalls like HvFlushVirtualAddress{List,Space}* and the
> >> upcoming HvSendSyntheticClusterIpi* where a single CPU may be specified in
> >> the whole set this is obviously sub-optimal.
> >>
> >> As VP index can be set to anything <= U32_MAX by userspace using plain
> >> [0..MAX_VP_INDEX] array is not a viable option. Use condensed sorted
> >> array with logarithmic search complexity instead. Use RCU to make read
> >> access as fast as possible and maintain atomicity of updates.
> >
> > Quoting TLFS 5.0C section 7.8.1:
> >
> >> Virtual processors are identified by using an index (VP index). The
> >> maximum number of virtual processors per partition supported by the
> >> current implementation of the hypervisor can be obtained through CPUID
> >> leaf 0x4005. A virtual processor index must be less than the
> >> maximum number of virtual processors per partition.
> >
> > so this is a dense index, and VP_INDEX >= KVM_MAX_VCPUS is invalid. I
> > think we're better off enforcing this in kvm_hv_set_msr and keep the
> > translation simple. If the algorithm in get_vcpu_by_vpidx is not good
> > enough (and yes it can be made to return NULL early on vpidx >=
> > KVM_MAX_VCPUS instead of taking the slow path) then a simple index array
> > of KVM_MAX_VCPUS entries should certainly do.
>
> Sure, we can use pre-allocated [0..KVM_MAX_VCPUS] array instead and put
> limits on what userspace can assign VP_INDEX to. Howver, while thinking
> about it I decided to go with the more complex condensed array approach
> because the tendency is for KVM_MAX_VCPUS to grow and we will be
> pre-allocating more and more memory for no particular reason (so I think
> even 'struct kvm_vcpu *vcpus[KVM_MAX_VCPUS]' in 'struct kvm' will need
> to be converted to something else eventually).
We're talking of kilobytes here. I guess this is going to be the least
of the scalability problems.
> Anyway, I'm flexible and if you think we should go this way now I'll do
> this in v3. We can re-think this when we later decide to raise
> KVM_MAX_VCPUS significantly.
Although there's no strict requirement for that I think every sensible
userspace will allocate VP_INDEX linearly resulting in it being equal to
KVM's vcpu index. So we've yet to see a case where get_vcpu_by_vpidx
doesn't take the fast path. If it ever starts appearing in the profiles
we may consider optimiziing it but ATM I don't even think introducing
the translation array is justified.
Roman.
Re: [PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
Roman Kagan writes:
> On Thu, Jun 28, 2018 at 03:53:10PM +0200, Vitaly Kuznetsov wrote:
>> While it is easy to get VP index from vCPU index the reverse task is hard.
>> Basically, to solve it we have to walk all vCPUs checking if their VP index
>> matches. For hypercalls like HvFlushVirtualAddress{List,Space}* and the
>> upcoming HvSendSyntheticClusterIpi* where a single CPU may be specified in
>> the whole set this is obviously sub-optimal.
>>
>> As VP index can be set to anything <= U32_MAX by userspace using plain
>> [0..MAX_VP_INDEX] array is not a viable option. Use condensed sorted
>> array with logarithmic search complexity instead. Use RCU to make read
>> access as fast as possible and maintain atomicity of updates.
>
> Quoting TLFS 5.0C section 7.8.1:
>
>> Virtual processors are identified by using an index (VP index). The
>> maximum number of virtual processors per partition supported by the
>> current implementation of the hypervisor can be obtained through CPUID
>> leaf 0x4005. A virtual processor index must be less than the
>> maximum number of virtual processors per partition.
>
> so this is a dense index, and VP_INDEX >= KVM_MAX_VCPUS is invalid. I
> think we're better off enforcing this in kvm_hv_set_msr and keep the
> translation simple. If the algorithm in get_vcpu_by_vpidx is not good
> enough (and yes it can be made to return NULL early on vpidx >=
> KVM_MAX_VCPUS instead of taking the slow path) then a simple index array
> of KVM_MAX_VCPUS entries should certainly do.
Sure, we can use pre-allocated [0..KVM_MAX_VCPUS] array instead and put
limits on what userspace can assign VP_INDEX to. Howver, while thinking
about it I decided to go with the more complex condensed array approach
because the tendency is for KVM_MAX_VCPUS to grow and we will be
pre-allocating more and more memory for no particular reason (so I think
even 'struct kvm_vcpu *vcpus[KVM_MAX_VCPUS]' in 'struct kvm' will need
to be converted to something else eventually).
Anyway, I'm flexible and if you think we should go this way now I'll do
this in v3. We can re-think this when we later decide to raise
KVM_MAX_VCPUS significantly.
--
Vitaly
Re: [PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
On Thu, Jun 28, 2018 at 03:53:10PM +0200, Vitaly Kuznetsov wrote:
> While it is easy to get VP index from vCPU index the reverse task is hard.
> Basically, to solve it we have to walk all vCPUs checking if their VP index
> matches. For hypercalls like HvFlushVirtualAddress{List,Space}* and the
> upcoming HvSendSyntheticClusterIpi* where a single CPU may be specified in
> the whole set this is obviously sub-optimal.
>
> As VP index can be set to anything <= U32_MAX by userspace using plain
> [0..MAX_VP_INDEX] array is not a viable option. Use condensed sorted
> array with logarithmic search complexity instead. Use RCU to make read
> access as fast as possible and maintain atomicity of updates.
Quoting TLFS 5.0C section 7.8.1:
> Virtual processors are identified by using an index (VP index). The
> maximum number of virtual processors per partition supported by the
> current implementation of the hypervisor can be obtained through CPUID
> leaf 0x4005. A virtual processor index must be less than the
> maximum number of virtual processors per partition.
so this is a dense index, and VP_INDEX >= KVM_MAX_VCPUS is invalid. I
think we're better off enforcing this in kvm_hv_set_msr and keep the
translation simple. If the algorithm in get_vcpu_by_vpidx is not good
enough (and yes it can be made to return NULL early on vpidx >=
KVM_MAX_VCPUS instead of taking the slow path) then a simple index array
of KVM_MAX_VCPUS entries should certainly do.
Roman.
Re: [PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
Hi Vitaly, Thank you for the patch! Perhaps something to improve: [auto build test WARNING on kvm/linux-next] [also build test WARNING on v4.18-rc2 next-20180628] [if your patch is applied to the wrong git tree, please drop us a note to help improve the system] url: https://github.com/0day-ci/linux/commits/Vitaly-Kuznetsov/KVM-x86-hyperv-PV-IPI-support-for-Windows-guests/20180629-011544 base: https://git.kernel.org/pub/scm/virt/kvm/kvm.git linux-next coccinelle warnings: (new ones prefixed by >>) >> arch/x86/kvm/hyperv.c:174:2-3: Unneeded semicolon Please review and possibly fold the followup patch. --- 0-DAY kernel test infrastructureOpen Source Technology Center https://lists.01.org/pipermail/kbuild-all Intel Corporation
Re: [PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
Hi Vitaly,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on kvm/linux-next]
[also build test WARNING on v4.18-rc2 next-20180628]
[if your patch is applied to the wrong git tree, please drop us a note to help
improve the system]
url:
https://github.com/0day-ci/linux/commits/Vitaly-Kuznetsov/KVM-x86-hyperv-PV-IPI-support-for-Windows-guests/20180629-011544
base: https://git.kernel.org/pub/scm/virt/kvm/kvm.git linux-next
reproduce:
# apt-get install sparse
make ARCH=x86_64 allmodconfig
make C=1 CF=-D__CHECK_ENDIAN__
sparse warnings: (new ones prefixed by >>)
>> arch/x86/kvm/hyperv.c:156:15: sparse: incompatible types in comparison
>> expression (different address spaces)
arch/x86/kvm/hyperv.c:195:15: sparse: incompatible types in comparison
expression (different address spaces)
vim +156 arch/x86/kvm/hyperv.c
136
137 static u32 vp_idx_to_vcpu_idx(struct kvm *kvm, u32 vp_idx)
138 {
139 struct kvm_hv *hv = &kvm->arch.hyperv;
140 u32 vcpu_idx = U32_MAX, tmp_vp_idx;
141 int l_index = 0, r_index, tmp_index;
142 struct vp_idx_map *map;
143
144 /*
145 * Make an educated guess: vp_idx is initialized to ==
vcpu_idx, it
146 * stays this way unless changed by userspace.
147 */
148 if (vp_idx < KVM_MAX_VCPUS) {
149 struct kvm_vcpu *vcpu = kvm_get_vcpu(kvm, vp_idx);
150
151 if (vcpu && vcpu_to_hv_vcpu(vcpu)->vp_index == vp_idx)
152 return vp_idx;
153 }
154
155 rcu_read_lock();
> 156 map = rcu_dereference(hv->vp_idx_map);
157 if (!map)
158 goto unlock;
159
160 r_index = map->len - 1;
161
162 while (r_index >= l_index) {
163 tmp_index = (r_index + l_index)/2;
164 tmp_vp_idx = map->vp_idx_elem[tmp_index].vp_idx;
165
166 if (tmp_vp_idx == vp_idx) {
167 vcpu_idx = map->vp_idx_elem[tmp_index].vcpu_idx;
168 break;
169 } else if (tmp_vp_idx < vp_idx) {
170 l_index = tmp_index + 1;
171 } else /* (tmp_vp_idx > vp_idx) */ {
172 r_index = tmp_index - 1;
173 }
174 };
175
176 unlock:
177 rcu_read_unlock();
178
179 return vcpu_idx;
180 }
181
---
0-DAY kernel test infrastructureOpen Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
[PATCH v2 2/5] KVM: x86: hyperv: introduce vp_index_to_vcpu_idx mapping
While it is easy to get VP index from vCPU index the reverse task is hard.
Basically, to solve it we have to walk all vCPUs checking if their VP index
matches. For hypercalls like HvFlushVirtualAddress{List,Space}* and the
upcoming HvSendSyntheticClusterIpi* where a single CPU may be specified in
the whole set this is obviously sub-optimal.
As VP index can be set to anything <= U32_MAX by userspace using plain
[0..MAX_VP_INDEX] array is not a viable option. Use condensed sorted
array with logarithmic search complexity instead. Use RCU to make read
access as fast as possible and maintain atomicity of updates.
Give vp_idx == U32_MAX a special 'remove only' meaning to keep
vp_idx_to_vcpu_idx()/vp_idx_update() interfaces simple.
Signed-off-by: Vitaly Kuznetsov
---
arch/x86/include/asm/kvm_host.h | 12 +++
arch/x86/kvm/hyperv.c | 190
2 files changed, 187 insertions(+), 15 deletions(-)
diff --git a/arch/x86/include/asm/kvm_host.h b/arch/x86/include/asm/kvm_host.h
index c13cd28d9d1b..2dfcdcaaa696 100644
--- a/arch/x86/include/asm/kvm_host.h
+++ b/arch/x86/include/asm/kvm_host.h
@@ -747,6 +747,16 @@ struct kvm_apic_map {
struct kvm_lapic *phys_map[];
};
+/* Mapping from VP number to vCPU idx */
+struct vp_idx_map {
+ struct rcu_head rcu;
+ int len;
+ struct {
+ u32 vp_idx;
+ u32 vcpu_idx;
+ } vp_idx_elem[];
+};
+
/* Hyper-V emulation context */
struct kvm_hv {
struct mutex hv_lock;
@@ -765,6 +775,8 @@ struct kvm_hv {
u64 hv_reenlightenment_control;
u64 hv_tsc_emulation_control;
u64 hv_tsc_emulation_status;
+
+ struct vp_idx_map *vp_idx_map;
};
enum kvm_irqchip_mode {
diff --git a/arch/x86/kvm/hyperv.c b/arch/x86/kvm/hyperv.c
index 63a17bbbf0e5..d676335a5448 100644
--- a/arch/x86/kvm/hyperv.c
+++ b/arch/x86/kvm/hyperv.c
@@ -127,19 +127,161 @@ static int synic_set_sint(struct kvm_vcpu_hv_synic
*synic, int sint,
return 0;
}
+static void vp_idx_map_free(struct rcu_head *rcu)
+{
+ struct vp_idx_map *map = container_of(rcu, struct vp_idx_map, rcu);
+
+ kfree(map);
+}
+
+static u32 vp_idx_to_vcpu_idx(struct kvm *kvm, u32 vp_idx)
+{
+ struct kvm_hv *hv = &kvm->arch.hyperv;
+ u32 vcpu_idx = U32_MAX, tmp_vp_idx;
+ int l_index = 0, r_index, tmp_index;
+ struct vp_idx_map *map;
+
+ /*
+* Make an educated guess: vp_idx is initialized to == vcpu_idx, it
+* stays this way unless changed by userspace.
+*/
+ if (vp_idx < KVM_MAX_VCPUS) {
+ struct kvm_vcpu *vcpu = kvm_get_vcpu(kvm, vp_idx);
+
+ if (vcpu && vcpu_to_hv_vcpu(vcpu)->vp_index == vp_idx)
+ return vp_idx;
+ }
+
+ rcu_read_lock();
+ map = rcu_dereference(hv->vp_idx_map);
+ if (!map)
+ goto unlock;
+
+ r_index = map->len - 1;
+
+ while (r_index >= l_index) {
+ tmp_index = (r_index + l_index)/2;
+ tmp_vp_idx = map->vp_idx_elem[tmp_index].vp_idx;
+
+ if (tmp_vp_idx == vp_idx) {
+ vcpu_idx = map->vp_idx_elem[tmp_index].vcpu_idx;
+ break;
+ } else if (tmp_vp_idx < vp_idx) {
+ l_index = tmp_index + 1;
+ } else /* (tmp_vp_idx > vp_idx) */ {
+ r_index = tmp_index - 1;
+ }
+ };
+
+unlock:
+ rcu_read_unlock();
+
+ return vcpu_idx;
+}
+
+/*
+ * Atomically updates vp_idx map removing old and adding new vp_idx->vcpu_idx
+ * mapping. vp_idx == U32_MAX means only the old mapping should be removed.
+ */
+static int vp_idx_update(struct kvm_hv *hv, u32 vp_idx, u32 vcpu_idx)
+{
+ struct vp_idx_map *new, *old;
+ int i, add = 1, remove = 1, nindex, oindex;
+ u32 vp_idx_old = U32_MAX;
+ bool added = false;
+ int ret;
+
+ mutex_lock(&hv->hv_lock);
+ old = rcu_dereference_protected(hv->vp_idx_map, &hv->hv_lock);
+ if (!old) {
+ ret = -EFAULT;
+ goto unlock_exit;
+ }
+
+ if (vp_idx == U32_MAX)
+ add = 0;
+
+ for (i = 0; i < old->len; i++) {
+ /* Check if we have stale mapping for vcpu_idx */
+ if (old->vp_idx_elem[i].vcpu_idx == vcpu_idx)
+ vp_idx_old = old->vp_idx_elem[i].vp_idx;
+
+ /* Check if we have another mapping for vp_idx */
+ if (old->vp_idx_elem[i].vp_idx == vp_idx) {
+ ret = -EEXIST;
+ goto unlock_exit;
+ }
+ }
+
+ if (vp_idx_old == U32_MAX)
+ remove = 0;
+
+ new = kmalloc(sizeof(*new) + sizeof(new->vp_idx_elem[0]) *
+ (old->len + add - remove), GFP_KERNEL);
+ if (!new) {
+ ret = -ENOMEM;
+ goto unlock_exit;
+ }
+ new->
