[Qemu-commits] [qemu/qemu] 500732: util: Add interval-tree.c

qemu-commits
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-commits] [qemu/qemu] 500732: util: Add interval-tree.c

From:	Peter Maydell
Subject:	[Qemu-commits] [qemu/qemu] 500732: util: Add interval-tree.c
Date:	Fri, 16 Dec 2022 13:52:47 -0800
  Branch: refs/heads/staging
  Home:   https://github.com/qemu/qemu
  Commit: 500732bf0e74ecacb21ca8a0f69523d7fde67507
      
https://github.com/qemu/qemu/commit/500732bf0e74ecacb21ca8a0f69523d7fde67507
  Author: Richard Henderson <richard.henderson@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    A include/qemu/interval-tree.h
    M tests/unit/meson.build
    A tests/unit/test-interval-tree.c
    A util/interval-tree.c
    M util/meson.build

  Log Message:
  -----------
  util: Add interval-tree.c

Copy and simplify the Linux kernel's interval_tree_generic.h,
instantiating for uint64_t.

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: dcbce177f6516631386361a04e1cd21aec394dba
      
https://github.com/qemu/qemu/commit/dcbce177f6516631386361a04e1cd21aec394dba
  Author: Richard Henderson <richard.henderson@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/tb-maint.c

  Log Message:
  -----------
  accel/tcg: Rename page_flush_tb

Rename to tb_remove_all, to remove the PageDesc "page" from the name,
and to avoid suggesting a "flush" in the icache sense.

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Reviewed-by: Philippe Mathieu-Daudé <philmd@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: 9ba696ad190a973a45c56ab4cbae2dd5207b0117
      
https://github.com/qemu/qemu/commit/9ba696ad190a973a45c56ab4cbae2dd5207b0117
  Author: Richard Henderson <richard.henderson@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/internal.h
    M accel/tcg/tb-maint.c
    M accel/tcg/translate-all.c
    M include/exec/exec-all.h

  Log Message:
  -----------
  accel/tcg: Use interval tree for TBs in user-only mode

Begin weaning user-only away from PageDesc.

Since, for user-only, all TB (and page) manipulation is done with
a single mutex, and there is no virtual/physical discontinuity to
split a TB across discontinuous pages, place all of the TBs into
a single IntervalTree. This makes it trivial to find all of the
TBs intersecting a range.

Retain the existing PageDesc + linked list implementation for
system mode.  Move the portion of the implementation that overlaps
the new user-only code behind the common ifdef.

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: 6677f9ae706165fb12ad2d709b58f3feab14aaaa
      
https://github.com/qemu/qemu/commit/6677f9ae706165fb12ad2d709b58f3feab14aaaa
  Author: Richard Henderson <richard.henderson@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/internal.h
    M accel/tcg/user-exec.c

  Log Message:
  -----------
  accel/tcg: Use interval tree for TARGET_PAGE_DATA_SIZE

Continue weaning user-only away from PageDesc.

Use an interval tree to record target data.
Chunk the data, to minimize allocation overhead.

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: 9ce7e612935563062d85ce04aaef2011f94c440c
      
https://github.com/qemu/qemu/commit/9ce7e612935563062d85ce04aaef2011f94c440c
  Author: Richard Henderson <richard.henderson@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/internal.h
    M accel/tcg/translate-all.c
    M accel/tcg/user-exec.c

  Log Message:
  -----------
  accel/tcg: Move page_{get,set}_flags to user-exec.c

This page tracking implementation is specific to user-only,
since the system softmmu version is in cputlb.c.  Move it
out of translate-all.c to user-exec.c.

Reviewed-by: Philippe Mathieu-Daudé <philmd@linaro.org>
Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: c0520994867e44a59da7d206bbce7544a0e8425a
      
https://github.com/qemu/qemu/commit/c0520994867e44a59da7d206bbce7544a0e8425a
  Author: Richard Henderson <richard.henderson@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/internal.h
    M accel/tcg/tb-maint.c
    M accel/tcg/user-exec.c
    A tests/tcg/multiarch/test-vma.c

  Log Message:
  -----------
  accel/tcg: Use interval tree for user-only page tracking

Finish weaning user-only away from PageDesc.

Using an interval tree to track page permissions means that
we can represent very large regions efficiently.

Resolves: https://gitlab.com/qemu-project/qemu/-/issues/290
Resolves: https://gitlab.com/qemu-project/qemu/-/issues/967
Resolves: https://gitlab.com/qemu-project/qemu/-/issues/1214
Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: 119245032f60f77a1d3f614296628e857882ecf8
      
https://github.com/qemu/qemu/commit/119245032f60f77a1d3f614296628e857882ecf8
  Author: Richard Henderson <richard.henderson@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/internal.h
    M accel/tcg/tb-maint.c
    M accel/tcg/translate-all.c

  Log Message:
  -----------
  accel/tcg: Move PageDesc tree into tb-maint.c for system

Now that PageDesc is not used for user-only, and for system
it is only used for tb maintenance, move the implementation
into tb-main.c appropriately ifdefed.

We have not yet eliminated all references to PageDesc for
user-only, so retain a typedef to the structure without definition.

Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: b6762ab42adfa04d8f6207b12f3d2bb4ef88779b
      
https://github.com/qemu/qemu/commit/b6762ab42adfa04d8f6207b12f3d2bb4ef88779b
  Author: Richard Henderson <richard.henderson@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/internal.h
    M accel/tcg/tb-maint.c
    M accel/tcg/translate-all.c
    M include/exec/translate-all.h

  Log Message:
  -----------
  accel/tcg: Move remainder of page locking to tb-maint.c

The only thing that still touches PageDesc in translate-all.c
are some locking routines related to tb-maint.c which have not
yet been moved.  Do so now.

Move some code up in tb-maint.c as well, to untangle the maze
of ifdefs, and allow a sensible final ordering.

Move some declarations from exec/translate-all.h to internal.h,
as they are only used within accel/tcg/.

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: 57cf42b9160c4598223977664040061a526ceb04
      
https://github.com/qemu/qemu/commit/57cf42b9160c4598223977664040061a526ceb04
  Author: Philippe Mathieu-Daudé <philmd@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/internal.h

  Log Message:
  -----------
  accel/tcg: Restrict cpu_io_recompile() to system emulation

Missed in commit 6526919224 ("accel/tcg: Restrict cpu_io_recompile()
from other accelerators").

Signed-off-by: Philippe Mathieu-Daudé <philmd@linaro.org>
Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Message-Id: <20221209093649.43738-2-philmd@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: 30f7b2d5a5ade0b3e10dc72789827923c76cad77
      
https://github.com/qemu/qemu/commit/30f7b2d5a5ade0b3e10dc72789827923c76cad77
  Author: Philippe Mathieu-Daudé <philmd@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/cputlb.c
    M accel/tcg/trace-events
    M trace-events

  Log Message:
  -----------
  accel/tcg: Remove trace events from trace-root.h

Commit d9bb58e510 ("tcg: move tcg related files into accel/tcg/
subdirectory") introduced accel/tcg/trace-events, so we don't
need to use the root trace-events anymore.

Signed-off-by: Philippe Mathieu-Daudé <philmd@linaro.org>
Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Message-Id: <20221209093649.43738-3-philmd@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: 4348c79bf8ded61e9852e735eb688a4afa03bf7b
      
https://github.com/qemu/qemu/commit/4348c79bf8ded61e9852e735eb688a4afa03bf7b
  Author: Philippe Mathieu-Daudé <philmd@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/cputlb.c
    M accel/tcg/internal.h
    M accel/tcg/tb-maint.c

  Log Message:
  -----------
  accel/tcg: Rename tb_invalidate_phys_page_fast{,__locked}()

Emphasize this function is called with pages locked.

Signed-off-by: Philippe Mathieu-Daudé <philmd@linaro.org>
Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Message-Id: <20221209093649.43738-4-philmd@linaro.org>
[rth: Use "__locked" suffix, to match other instances.]
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: 6ca965e96e6b2abdf1da43485c08a743bf94131b
      
https://github.com/qemu/qemu/commit/6ca965e96e6b2abdf1da43485c08a743bf94131b
  Author: Philippe Mathieu-Daudé <philmd@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/cputlb.c
    M accel/tcg/internal.h
    M accel/tcg/tb-maint.c

  Log Message:
  -----------
  accel/tcg: Factor tb_invalidate_phys_range_fast() out

Signed-off-by: Philippe Mathieu-Daudé <philmd@linaro.org>
Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Message-Id: <20221209093649.43738-5-philmd@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: a9d0226381d6d70a9c1901ad1480961c93de8b8d
      
https://github.com/qemu/qemu/commit/a9d0226381d6d70a9c1901ad1480961c93de8b8d
  Author: Philippe Mathieu-Daudé <philmd@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/internal.h
    M accel/tcg/tb-maint.c

  Log Message:
  -----------
  accel/tcg: Restrict page_collection structure to system TB maintainance

Only the system emulation part of TB maintainance uses the
page_collection structure. Restrict its declaration (and the
functions requiring it) to tb-maint.c.

Convert the 'len' argument of tb_invalidate_phys_page_fast__locked()
from signed to unsigned.

Signed-off-by: Philippe Mathieu-Daudé <philmd@linaro.org>
Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
Message-Id: <20221209093649.43738-6-philmd@linaro.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>


  Commit: 6f46acf890f92f832c8f6757fa232d6a4f0fdc53
      
https://github.com/qemu/qemu/commit/6f46acf890f92f832c8f6757fa232d6a4f0fdc53
  Author: Peter Maydell <peter.maydell@linaro.org>
  Date:   2022-12-16 (Fri, 16 Dec 2022)

  Changed paths:
    M accel/tcg/cputlb.c
    M accel/tcg/internal.h
    M accel/tcg/tb-maint.c
    M accel/tcg/trace-events
    M accel/tcg/translate-all.c
    M accel/tcg/user-exec.c
    M include/exec/exec-all.h
    M include/exec/translate-all.h
    A include/qemu/interval-tree.h
    A tests/tcg/multiarch/test-vma.c
    M tests/unit/meson.build
    A tests/unit/test-interval-tree.c
    M trace-events
    A util/interval-tree.c
    M util/meson.build

  Log Message:
  -----------
  Merge tag 'pull-tcg-20221216' of https://gitlab.com/rth7680/qemu into staging

Use interval trees for user-only vma mappings.
Assorted cleanups to page locking.

# gpg: Signature made Fri 16 Dec 2022 18:48:14 GMT
# gpg:                using RSA key 7A481E78868B4DB6A85A05C064DF38E8AF7E215F
# gpg:                issuer "richard.henderson@linaro.org"
# gpg: Good signature from "Richard Henderson <richard.henderson@linaro.org>" 
[full]
# Primary key fingerprint: 7A48 1E78 868B 4DB6 A85A  05C0 64DF 38E8 AF7E 215F

* tag 'pull-tcg-20221216' of https://gitlab.com/rth7680/qemu:
  accel/tcg: Restrict page_collection structure to system TB maintainance
  accel/tcg: Factor tb_invalidate_phys_range_fast() out
  accel/tcg: Rename tb_invalidate_phys_page_fast{,__locked}()
  accel/tcg: Remove trace events from trace-root.h
  accel/tcg: Restrict cpu_io_recompile() to system emulation
  accel/tcg: Move remainder of page locking to tb-maint.c
  accel/tcg: Move PageDesc tree into tb-maint.c for system
  accel/tcg: Use interval tree for user-only page tracking
  accel/tcg: Move page_{get,set}_flags to user-exec.c
  accel/tcg: Use interval tree for TARGET_PAGE_DATA_SIZE
  accel/tcg: Use interval tree for TBs in user-only mode
  accel/tcg: Rename page_flush_tb
  util: Add interval-tree.c

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>


Compare: https://github.com/qemu/qemu/compare/d038d2645aca...6f46acf890f9
[Prev in Thread]
Current Thread
[Next in Thread]
[Qemu-commits] [qemu/qemu] 500732: util: Add interval-tree.c, Peter Maydell <=
Prev by Date: [Qemu-commits] [qemu/qemu] 00eb93: block: Inline bdrv_detach_child()
Next by Date: [Qemu-commits] [qemu/qemu] d17052: hw/s390x/s390-pci-inst.c: Use device_cold_reset() ...
Previous by thread: [Qemu-commits] [qemu/qemu] 00eb93: block: Inline bdrv_detach_child()
Next by thread: [Qemu-commits] [qemu/qemu] d17052: hw/s390x/s390-pci-inst.c: Use device_cold_reset() ...
Index(es):
- Date
- Thread