Igor Druzhinin [Wed, 28 Jun 2017 19:27:08 +0000 (20:27 +0100)]
tools/libxenforeignmemory: add xenforeignmemory_map2 function
The new function repeats the behavior of the first version
except it has an extended list of arguments which are subsequently
passed to mmap() call.
This is needed for QEMU depriviledging.
Signed-off-by: Igor Druzhinin <igor.druzhinin@citrix.com> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: Wei Liu <wei.liu2@citrix.com>
Reverse sorting order, add blank lines at register change.
Signed-off-by: Marek Marczykowski-Górecki <marmarek@invisiblethingslab.com> Acked-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: Wei Liu <wei.liu2@citrix.com>
To have it in .rodata, instead of reconstructing each time on stack.
Signed-off-by: Marek Marczykowski-Górecki <marmarek@invisiblethingslab.com> Acked-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: Wei Liu <wei.liu2@citrix.com>
Signed-off-by: Marek Marczykowski-Górecki <marmarek@invisiblethingslab.com> Acked-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: Wei Liu <wei.liu2@citrix.com>
This is result of parsing cpu_map.xml from libvirt.
The most important part is handling leaf 0x00000007, but while at it add
other bits too.
Signed-off-by: Marek Marczykowski-Górecki <marmarek@invisiblethingslab.com> Acked-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: Wei Liu <wei.liu2@citrix.com>
Sergey Dyasli [Wed, 28 Jun 2017 09:35:45 +0000 (10:35 +0100)]
vvmx: fix ept_sync() for nested p2m
If ept_sync_domain() is called for np2m, the following happens:
1. *np2m*::ept_data::invalidate cpumask is updated
2. IPIs are sent for CPUs in domain_dirty_cpumask forcing vmexits
3. vmx_vmenter_helper() checks *hostp2m*::ept_data::invalidate
and does nothing
Which is clearly a bug. Make ept_sync_domain() to update hostp2m's
invalidate mask in nested p2m case and make vmx_vmenter_helper() to
invalidate EPT translations for all EPTPs if nested virt is enabled.
Signed-off-by: Sergey Dyasli <sergey.dyasli@citrix.com> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: Kevin Tian <kevin.tian@intel.com>
Andrew Cooper [Wed, 28 Jun 2017 14:05:35 +0000 (15:05 +0100)]
x86/vvmx: Fix WRMSR interception of VMX MSRs
FEATURE_CONTROL is already read with LOCK bit set (so is unmodifiable), and
all VMX MSRs are read-only. Also, fix the MSR_IA32_VMX_TRUE_ENTRY_CTLS bound
to be MSR_IA32_VMX_VMFUNC, rather than having the intervening MSRs falling
into the default case.
Raise #GP faults if the guest tries to modify any of them.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com> Acked-by: Kevin Tian <kevin.tian@intel.com>
Zhongze Liu [Thu, 22 Jun 2017 16:35:28 +0000 (00:35 +0800)]
libxc: add xc_domain_add_to_physmap_batch to wrap XENMEM_add_to_physmap_batch
This is a preparation for the proposal "allow setting up shared memory areas
between VMs from xl config file". See:
V2: https://lists.xen.org/archives/html/xen-devel/2017-06/msg02256.html
V1: https://lists.xen.org/archives/html/xen-devel/2017-05/msg01288.html
The plan is to use XENMEM_add_to_physmap_batch in xl to map foregin pages from
one DomU to another so that the page could be shared. But currently there is no
wrapper for XENMEM_add_to_physmap_batch in libxc, so we just add a wrapper for
it.
Signed-off-by: Zhongze Liu <blackskygg@gmail.com> Acked-by: Wei Liu <wei.liu2@citrix.com>
Andrew Cooper [Fri, 23 Jun 2017 10:48:21 +0000 (10:48 +0000)]
xen/tmem: Switch to using bool
* Drop redundant initialisers
* Style corrections while changing client_over_quota()
* Drop all write-only bools from do_tmem_op()
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com> Reviewed-by: Wei Liu <wei.liu2@citrix.com>
Wei Liu [Mon, 26 Jun 2017 14:20:35 +0000 (15:20 +0100)]
xen: move do_nmi_op and make it x86 only
Since ARM doesn't need {compat,do}_nmi_op, move the hypercall handlers
from common/kernel.c to pv/callback.c. Drop the stubs in ARM. Delete
the common and ARM nmi.h and adjust header inclusions in various
files.
Signed-off-by: Wei Liu <wei.liu2@citrix.com> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: Stefano Stabellini <sstabellini@kernel.org>
Wei Liu [Mon, 5 Jun 2017 15:15:26 +0000 (16:15 +0100)]
x86/traps: factor out pv_trap_init
Factor out pv_trap_init and call it at the beginning of trap_init. We
then need to tune the code to generate stub handlers in entry.S. Take
the chance to tune init_irq_data so that 0x80 and 0x82 can be used for
regular interrupts in !CONFIG_PV case.
While at it, fix some coding style issues in init_irq_data and replace
0x80 with LEGACY_SYSCALL_VECTOR in pv_trap_init.
Signed-off-by: Wei Liu <wei.liu2@citrix.com> Reivewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
Andrew Cooper [Tue, 27 Jun 2017 17:45:03 +0000 (18:45 +0100)]
xen/pt: Avoid NULL dereference in hvm_pirq_eoi()
Coverity warns that pirq_dpci unconditionally dereferences a NULL pointer.
This warning appears to be triggered by pirq_dpci() which is a hidden ternary
expression. In reality, it appears that both callers pass a non-NULL pirq
parameter, so the code is ok in practice.
Rearange the logic to fail-safe, which should quiesce Coverity.
Clean up bool_t => bool and trailing whitespace for hvm_domain_use_pirq()
while auditing this area.
No (intended) functional change.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: Jan Beulich <jbeulich@suse.com> Reviewed-by: Roger Pau Monné <roger.pau@citrix.com>
Andrew Cooper [Tue, 27 Jun 2017 17:29:55 +0000 (18:29 +0100)]
xen/pt: Unlock d->event_lock on error paths
Introduced by c/s fba00494268 "x86/pt: enable binding of GSIs to a PVH Dom0"
Spotted by Coverity.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com> Reviewed-by: Roger Pau Monné <roger.pau@citrix.com>
Roger Pau Monne [Fri, 23 Jun 2017 09:59:51 +0000 (10:59 +0100)]
x86/vioapic: bind interrupts to PVH Dom0
Add the glue in order to bind the PVH Dom0 GSI from bare metal. This
is done when Dom0 unmasks the vIO APIC pins, by fetching the current
pin settings and setting up the PIRQ, which will then be bound to
Dom0.
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
Roger Pau Monne [Mon, 26 Jun 2017 09:47:13 +0000 (10:47 +0100)]
x86/pt: enable binding of GSIs to a PVH Dom0
Achieve this by expanding pt_irq_create_bind in order to support
mapping interrupts of type PT_IRQ_TYPE_PCI to a PVH Dom0. GSIs bound
to Dom0 are always identity bound, which means the all the fields
inside of the u.pci sub-struct are ignored, and only the machine_irq
is actually used in order to determine which GSI the caller wants to
bind.
Also, the hvm_irq_dpci struct is not used by a PVH Dom0, since that's
used to route interrupts and allow different host to guest GSI
mappings, which is not used by a PVH Dom0.
This requires adding some specific handlers for such directly mapped
GSIs, which bypass the PCI interrupt routing done by Xen for HVM
guests.
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
Olaf Hering [Mon, 26 Jun 2017 12:55:07 +0000 (14:55 +0200)]
rombios: prevent building with PIC/PIE
If the default compiler silently defaults to to -fPIC/-fPIE building
rombios fails:
ld -melf_i386 -s -r 32bitbios.o tcgbios/tcgbiosext.o util.o pmm.o -o 32bitbios_all.o
There are undefined symbols in the BIOS:
U _GLOBAL_OFFSET_TABLE_
make[10]: *** [Makefile:26: 32bitbios_all.o] Error 11
Prevent the failure by enforcing non-PIC/PIE mode.
Signed-off-by: Olaf Hering <olaf@aepfle.de> Acked-by: Andrew Cooper <andrew.cooper3@citrix.com>
Andrew Cooper [Mon, 26 Jun 2017 11:58:25 +0000 (12:58 +0100)]
x86/mm: Fix infinite loop in get_spage_pages()
c/s 2b8eb37 switched int i to being unsigned, but the undo logic on failure
relied in i being signed. As i being unsigned in still preforable, adjust the
undo logic to work with an unsigned i.
Coverity-ID: 1413017 Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Konrad Rzeszutek Will <konrad.wilk@oracle.com> Reviewed-by: Wei Liu <wei.liu2@citrix.com>
Bhupinder Thakur [Thu, 22 Jun 2017 07:38:37 +0000 (13:08 +0530)]
xen/arm: Rename vgic_reg* functions definitions and calls to vreg_reg*
This patch renames the vgic_reg* access functions defined in vreg.h to vreg_reg*
and replaces all calls to vgic_reg* functions in vgic/its emulation code to vreg_reg*.
vreg_reg* are generic functions, which can be used to operate on 32/64-bit registers.
SBSA UART emulation code will also use vreg_reg* access functions for
accessing emulated pl011 registers.
Bhupinder Thakur [Thu, 22 Jun 2017 07:38:36 +0000 (13:08 +0530)]
xen/arm: vpl011: Move vgic register access functions to vreg.h
These functions are generic in nature and can be reused by other emulation
code in Xen. vGICv3 ITS and SBSA UART emulation code, would use these
functions to operate on their registers.
This patch moves the register access function definitions from vgic.h to
vreg.h.
Wei Liu [Mon, 5 Jun 2017 14:16:17 +0000 (15:16 +0100)]
x86: clean up PV emulation code
Replace bool_t with bool. Fix coding style issues. Add spaces around
binary ops. Use 1U for shifting. Eliminate TOGGLE_MODE.
Signed-off-by: Wei Liu <wei.liu2@citrix.com> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
Andrew Cooper [Tue, 13 Jun 2017 20:36:58 +0000 (21:36 +0100)]
xen/livepatch: Don't crash on encountering STN_UNDEF relocations
A symndx of STN_UNDEF is special, and means a symbol value of 0. While
legitimate in the ELF standard, its existance in a livepatch is questionable
at best. Until a plausible usecase presents itself, reject such a relocation
with -EOPNOTSUPP.
Additionally, fix an off-by-one error while range checking symndx, and perform
a safety check on elf->sym[symndx].sym before derefencing it, to avoid
tripping over a NULL pointer when calculating val.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Stefano Stabellini <sstabellini@kernel.org> Reviewed-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com> Tested-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com> [x86 and arm32] Reviewed-by: Jan Beulich <JBeulich@suse.com> Reviewed-by: Ross Lagerwall <ross.lagerwall@citrix.com>
Andrew Cooper [Thu, 22 Jun 2017 17:55:31 +0000 (18:55 +0100)]
xen/livepatch: Use zeroed memory allocations for arrays
Each of these arrays is sparse. Use zeroed allocations to cause uninitialised
array elements to contain deterministic values, most importantly for the
embedded pointers.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com> Tested-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com> [x86 and arm32] Reviewed-by: Ross Lagerwall <ross.lagerwall@citrix.com>
Andrew Cooper [Tue, 13 Jun 2017 20:17:47 +0000 (21:17 +0100)]
xen/livepatch: Clean up arch relocation handling
* Reduce symbol scope and initalisation as much as possible
* Annotate a fallthrough case in arm64
* Fix switch statement style in arm32
No functional change.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com> Reviewed-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com> Tested-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com> [x86 and arm32]
Andrew Cooper [Wed, 21 Jun 2017 11:36:18 +0000 (12:36 +0100)]
xen: Replace ASSERT(0) with ASSERT_UNREACHABLE()
No functional change, but the result is more informative both in the code and
error messages if the assertions do get hit.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com> Reviewed-by: Julien Grall <julien.gralL@arm.com> Acked-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>
Andrew Cooper [Tue, 18 Apr 2017 14:41:16 +0000 (15:41 +0100)]
x86/mm: Misc nonfunctional cleanup
* Drop trailing whitespace
* Apply Xen comment and space style
* Switch bool_t to bool
* Drop TOGGLE_MODE() macro
* Replace erroneous mandatory barriers with smp barriers
* Switch boolean ints for real bools
No (intended) functional change.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
Fixed an issue where the maximum index allowed (31) goes beyond the
actual number of array elements (4) of ad->monitor.write_ctrlreg_mask.
Coverity-ID: 1412966
Signed-off-by: Razvan Cojocaru <rcojocaru@bitdefender.com> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
Jan Beulich [Fri, 23 Jun 2017 13:49:41 +0000 (15:49 +0200)]
make steal_page() return a proper error value
... and use it where suitable (the tmem caller doesn't propagate an
error code). While it doesn't matter as much, also make donate_page()
follow suit on x86 (on ARM it already returns -ENOSYS).
Also move their declarations to common code and add __must_check.
Signed-off-by: Jan Beulich <jbeulich@suse.com> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: Julien Grall <julien.grall@arm.com>
Jan Beulich [Fri, 23 Jun 2017 13:48:28 +0000 (15:48 +0200)]
x86emul: simplify SHLD/SHRD handling
First of all there's no point considering the "shift == width" case,
when immediately before that check we mask "shift" by "width - 1". And
then truncate_word() use can be reduced too: dst.val, as obtained by
generic operand fetching code, is already suitably truncated, and its
use can also be made symmetric in the main conditional expression (on
only left shift results). Finally masking the result of a right shift
is not necessary when the left hand operand doesn't have more than
"width" significant bits.
Signed-off-by: Jan Beulich <jbeulich@suse.com> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
Jan Beulich [Thu, 22 Jun 2017 07:58:07 +0000 (09:58 +0200)]
x86/mm: drop redundant domain parameter from get_page_from_gfn_p2m()
It can always be read from the passed p2m. Take the opportunity and
also rename the function, making the "p2m" suffix a prefix, to match
other p2m functions, and convert the "gfn" parameter's type.
Signed-off-by: Jan Beulich <jbeulich@suse.com> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: George Dunlap <george.dunlap@citrix.com>
Jan Beulich [Thu, 22 Jun 2017 07:55:08 +0000 (09:55 +0200)]
gnttab: limit mapkind()'s iteration count
There's no need for the function to observe increases of the maptrack
table (which can occur as the maptrack lock isn't being held) - actual
population of maptrack entries is excluded while we're here (by way of
holding the respective grant table lock for writing, while code
populating entries acquires it for reading). Latch the limit ahead of
the loop, allowing for the barrier to move out, too.
Signed-off-by: Jan Beulich <jbeulich@suse.com> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
George Dunlap [Thu, 22 Jun 2017 07:53:18 +0000 (09:53 +0200)]
gnttab: remove host map in the event of a grant_map failure
The current code appropriately removes the reference and type counts
on failure, but leaves the mapping set up. As the only path which can
trigger this is failure from IOMMU manipulation, and as unprivileged
domains are being crashed in that case, this is not by itself a
security issue.
Reported-by: Jan Beulich <jbeulich@suse.com> Signed-off-by: George Dunlap <george.dunlap@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
Jan Beulich [Thu, 22 Jun 2017 07:51:29 +0000 (09:51 +0200)]
ARM: simplify page type handling
There's no need to have anything here on ARM other than the distinction
between writable and non-writable pages (and even that could likely be
eliminated, but with a more intrusive change). Limit type to a single
bit and drop pinned and validated flags altogether.
Signed-off-by: Jan Beulich <jbeulich@suse.com> Reviewed-by: Stefano Stabellini <sstabellini@kernel.org>
Dario Faggioli [Thu, 22 Jun 2017 07:45:37 +0000 (09:45 +0200)]
idle_loop: either deal with tasklets or go idle
In fact, there are two kinds of tasklets: vCPU and
softirq context. When we want to do vCPU context tasklet
work, we force the idle vCPU (of a particular pCPU) into
execution, and run it from there.
This means there are two possible reasons for choosing
to run the idle vCPU:
1) we want a pCPU to go idle,
2) we want to run some vCPU context tasklet work.
If we're in case 2), it does not make sense to even
try to go idle (as the check will _always_ fail).
This patch rearranges the code of the body of idle
vCPUs, so that we actually check whether we are in
case 1) or 2), and act accordingly.
As a matter of fact, this also means that we do not
check if there's any tasklet work to do after waking
up from idle. This is not a problem, because:
a) for softirq context tasklets, if any is queued
"during" wakeup from idle, TASKLET_SOFTIRQ is
raised, and the call to do_softirq() (which is still
happening *after* the wakeup) will take care of it;
b) for vCPU context tasklets, if any is queued "during"
wakeup from idle, SCHEDULE_SOFTIRQ is raised and
do_softirq() (happening after the wakeup) calls
the scheduler. The scheduler sees that there is
tasklet work pending and confirms the idle vCPU
in execution, which then will get to execute
do_tasklet().
Add a pointer to the gic device tree bindings. Add an explanation on how
to calculate irq numbers from device tree.
Add a brief explanation of the reg property and a pointer to the xl docs
for a description of the iomem property. Add a note that in the example
we are using different memory addresses for guests and host.
Juergen Gross [Thu, 15 Jun 2017 09:58:27 +0000 (11:58 +0200)]
tools/xen-detect: try sysfs node for obtaining guest type
Instead of relying on cpuid instruction behaviour to tell which domain
type we are just try asking the kernel via the appropriate sysfs node
(added in Linux kernel 4.13).
Keep the old detection logic as a fallback for older kernels.
Petre Pircalabu [Tue, 20 Jun 2017 15:13:20 +0000 (17:13 +0200)]
x86/monitor: add masking support for write_ctrlreg events
Add support for filtering out the write_ctrlreg monitor events if they
are generated only by changing certains bits.
A new parameter (bitmask) was added to the xc_monitor_write_ctrlreg
function in order to mask the event generation if the changed bits are
set.
Signed-off-by: Petre Pircalabu <ppircalabu@bitdefender.com> Acked-by: Tamas K Lengyel <tamas@tklengyel.com> Acked-by: Wei Liu <wei.liu2@citrix.com>
Ross Lagerwall [Tue, 20 Jun 2017 15:13:02 +0000 (17:13 +0200)]
rombios/ata: wait for BSY to clear after write
After rombios transfers the data for a write, it checks the status and
fails if BSY is set. qemu-trad doesn't set BSY for PIO writes, but QEMU
upstream does, and this causes rombios to fail writes because they are
marked as BSY. Instead, wait for BSY to clear after a write.
INT 13 writes are probably rarely used these days, but they are used by
GRUB 2 to write to its environment file which happens by default on
Ubuntu.
Signed-off-by: Ross Lagerwall <ross.lagerwall@citrix.com> Acked-by: Andrew Cooper <andrew.cooper3@citrix.com>
Ian Jackson [Mon, 19 Jun 2017 14:04:08 +0000 (15:04 +0100)]
xen/test/Makefile: Fix clean target, broken by pattern rule
In "xen/test/livepatch: Regularise Makefiles" we reworked
xen/test/Makefile to use a pattern rule. However, there are two
problems with this. Both are related to the way that xen/Rules.mk is
implicitly part of this Makefile because of the way that Makefiles
under xen/ are invoked by their parent directory Makefiles.
Firstly, the Rules.mk `clean' target overrides the pattern rule in
xen/test/Makefile. The result is that `make -C xen clean' does not
actually run the livepatch clean target.
The Rules.mk clean target does have provision for recursing into
subdirectories, but that feature is tangled up with complex object
file iteration machinery which is not desirable here. However, we can
extend the Rules.mk clean target since it is a double-colon rule.
Sadly this involves duplicating the SUBDIR iteration boilerplate. (A
make function could be used but the cure would be worse than the
disease.)
Secondly, Rules.mk has a number of -include directives. make likes to
try to (re)build files mentioned in includes. With the % pattern
rule, this applies to those files too.
As a result, make -C xen clean would try to build `.*.d' (for example)
in xen/test. This would fail with an error message. The error would
be ignored because of the `-', but it's annoying and ugly.
Solve this by limiting the % pattern rule to the targets we expect it
to handle. These are those listed in the top-level Makefile help
message, apart from: those which are subdir- or component-qualified;
clean targets (which are handled specially, even distclean); and dist,
src-tarball-*, etc. (which are converted to install by an earlier
Makefile).
Reported-by: Andrew Cooper <andrew.cooper3@citrix.com> Signed-off-by: Ian Jackson <Ian.Jackson@eu.citrix.com> Tested-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com> Acked-by: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com> Release-acked-by: Julien Grall <julien.grall@arm.com>
Jan Beulich [Tue, 20 Jun 2017 12:51:53 +0000 (14:51 +0200)]
memory: don't suppress P2M update in populate_physmap()
Commit d18627583d ("memory: don't hand MFN info to translated guests")
wrongly added a null-handle check there - just like stated in its
description for memory_exchange(), the array is also an input for
populate_physmap() (and hence can't reasonably be null). I have no idea
how I've managed to overlook this.
Signed-off-by: Jan Beulich <jbeulich@suse.com> Acked-by: Andrew Cooper <andrew.cooper3@citrix.com>
Wolfram Strepp [Tue, 20 Jun 2017 12:51:07 +0000 (14:51 +0200)]
rb_tree: make clear distinction between two different cases in rb_erase()
There are two cases when a node, having 2 childs, is erased:
'normal case': the successor is not the right-hand-child of the node to be
erased
'special case': the successor is the right-hand child of the node to be erased
Here some ascii-art, with following symbols (referring to the code):
O: node to be deleted
N: the successor of O
P: parent of N
C: child of N
L: some other node
normal case:
O N
/ \ / \
/ \ / \
L \ L \
/ \ P ----> / \ P
/ \ / \
/ /
N C
\ / \
\
C
/ \
special case:
O|P N
/ \ / \
/ \ / \
L \ L \
/ \ N ----> / C
\ / \
\
C
/ \
Notice that for the special case we don't have to reconnect C to N.
Signed-off-by: Wolfram Strepp <wstrepp@gmx.de> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 4c60117811171d867d4f27f17ea07d7419d45dae]
Wolfram Strepp [Tue, 20 Jun 2017 12:50:13 +0000 (14:50 +0200)]
rbtree: optimize rb_erase()
Tfour 4 redundant if-conditions in function __rb_erase_color() in
lib/rbtree.c are removed.
In pseudo-source-code, the structure of the code is as follows:
if ((!A || B) && (!C || D)) {
.
.
.
} else {
if (!C || D) {//if this is true, it implies: (A == true) && (B == false)
if (A) {//hence this always evaluates to 'true'...
.
}
.
//at this point, C always becomes true, because of:
__rb_rotate_right/left();
//and:
other = parent->rb_right/left;
}
.
.
if (C) {//...and this too !
.
}
}
Signed-off-by: Wolfram Strepp <wstrepp@gmx.de> Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 55a63998b8967615a15e2211ba0ff3a84a565824]
Artem Bityutskiy [Tue, 20 Jun 2017 12:49:40 +0000 (14:49 +0200)]
rbtree: add const qualifier to some functions
The 'rb_first()', 'rb_last()', 'rb_next()' and 'rb_prev()' calls
take a pointer to an RB node or RB root. They do not change the
pointed objects, so add a 'const' qualifier in order to make life
of the users of these functions easier.
Indeed, if I have my own constant pointer &const struct my_type *p,
and I call 'rb_next(&p->rb)', I get a GCC warning:
warning: passing argument 1 of \91rb_next\92 discards qualifiers from pointer target
type
projects / xen.git / log