kvm tools: remove max_high field in rb_int_node structure

Since nothing depends on the max_high field values anymore, we can just
remove the field and the code that was used to maintain it.

Signed-

kvm tools: remove max_high field in rb_int_node structure

Since nothing depends on the max_high field values anymore, we can just
remove the field and the code that was used to maintain it.

Signed-off-by: Michel Lespinasse <walken@google.com>
Signed-off-by: Pekka Enberg <penberg@kernel.org>

show more ...

kvm tools: rb_int_search_single simplification

As the rbtree intervals are not overlapping, rb_int_search_single can
trivially be implemented without making use of the max_high field.

Signed-off-by

kvm tools: rb_int_search_single simplification

As the rbtree intervals are not overlapping, rb_int_search_single can
trivially be implemented without making use of the max_high field.

Signed-off-by: Michel Lespinasse <walken@google.com>
Signed-off-by: Pekka Enberg <penberg@kernel.org>

show more ...

kvm tools: ensure non-overlapping intervals in rb_int_insert()

The rbtree interval API is designed for handling non-overlapping intervals;
modify rb_int_insert() to guarantee this property is mainta

kvm tools: ensure non-overlapping intervals in rb_int_insert()

The rbtree interval API is designed for handling non-overlapping intervals;
modify rb_int_insert() to guarantee this property is maintained by
returning -EEXIST when attempting to insert a new interval that overlaps
an existing interval.

Also fix an issue where the computation of 'result' could trigger an
integer overflow which would break the rbtree ordering.

Signed-off-by: Michel Lespinasse <walken@google.com>
Signed-off-by: Pekka Enberg <penberg@kernel.org>

show more ...

kvm tools: fix rbtree-interval search

I've noticed message on kvm exit:

Warning: serial8250__exit failed.

kvm tool is not able to remove ioport range which was added previously.

The issue is ca

kvm tools: fix rbtree-interval search

I've noticed message on kvm exit:

Warning: serial8250__exit failed.

kvm tool is not able to remove ioport range which was added previously.

The issue is caused by bug in rbtree-interval. Search algorithm in
rb_int_search_single() expects correct value of max_high. But the tree
can contain leaf nodes, which never were updated by propagate_callback().
For this kind of nodes high_max will be 0 and we will not be able to
find and remove them.

Let's initialize max_high on RB_INT_INIT() time.

Fixing this bug makes other bug visible: propagate_callback() can be
called for empty tree: node == NULL. The callback is not ready for empty
tree. Let's fix that as well.

Tested-by: William Dauchy <william@gandi.net>
Signed-off-by: Kirill A. Shutemov <kirill.shutemov@linux.intel.com>
Signed-off-by: Pekka Enberg <penberg@kernel.org>

show more ...

kvm tools: Port to v3.7-rc1

There were a number of changes that caused problems:

- UAPI conversion

- the old version of the rbtree-augmented API got removed, I
updated the implementation to t

kvm tools: Port to v3.7-rc1

There were a number of changes that caused problems:

- UAPI conversion

- the old version of the rbtree-augmented API got removed, I
updated the implementation to the new API

- lib/rbtree.c wants a 'true' definition

Lightly tested: it boots a v3.7-rc1 defconfig+kvmconfig kernel.

Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Pekka Enberg <penberg@kernel.org>

show more ...

kvm tools: Fixes for virtio module

Fixes include:
- Error handling
- Cleanup
- Standard init/uninit

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>

kvm tools: Fixes for ioport module

Fixes include:
- Error handling
- Cleanup
- Standard init/uninit

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>

kvm tools: Fix rbtree-interval balancing

Augmentation is started on the pre-rotation node found in the search,
augment the rotated node instead.

Max high is the max of max highs below it, not the m

kvm tools: Fix rbtree-interval balancing

Augmentation is started on the pre-rotation node found in the search,
augment the rotated node instead.

Max high is the max of max highs below it, not the max of highs below it.

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
Signed-off-by: Pekka Enberg <penberg@kernel.org>

show more ...

kvm tools: Add interval red-black tree helper

Interval rb-tree allows to directly store interval ranges
and quickly lookup an overlap with a single point or a range.

The helper is based on the kern

kvm tools: Add interval red-black tree helper

Interval rb-tree allows to directly store interval ranges
and quickly lookup an overlap with a single point or a range.

The helper is based on the kernel rb-tree implementation
(located in <linux/rbtree.h>) which alows for the augmention
of the classical rb-tree to be used as an interval tree.

Acked-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
Signed-off-by: Pekka Enberg <penberg@kernel.org>

show more ...