Skip to content

Q
qemu

openeuler / qemu

通知 10
Star 0
Fork 0
Q
qemu
切换分支/标签
  1. 30 10月, 2018 2 次提交
  3. 18 6月, 2018 1 次提交
  5. 08 2月, 2018 1 次提交
  7. 18 12月, 2017 1 次提交
  9. 06 10月, 2017 1 次提交
  11. 11 7月, 2017 3 次提交
  13. 26 1月, 2017 1 次提交
  15. 29 11月, 2016 1 次提交
    • M
      hbitmap: Fix shifts of constants by granularity · 6725f887
      由 Max Reitz 提交于 
      An hbitmap's granularity may be anything from 0 to 63, so when shifting
constants by its value, they should not be plain ints.

Even having changed the types, hbitmap_serialization_granularity() still
tries to shift 64 to the right by the granularity. This operation is
undefined if the granularity is greater than 57. Adding an assertion is
fine for now, because serializing is done only in tests so far, but this
means that only bitmaps with a granularity below 58 can be serialized
and we should thus add a hbitmap_is_serializable() function later.

One of the two places touched in this patch uses
QEMU_ALIGN_UP(x, 1 << y). We can use ROUND_UP() there, since the second
parameter is obviously a power of two.
Signed-off-by: NMax Reitz <mreitz@redhat.com>
Message-Id: <20161115224732.1334-1-mreitz@redhat.com>
Reviewed-by: NStefan Hajnoczi <stefanha@redhat.com>
Signed-off-by: NFam Zheng <famz@redhat.com>
      6725f887
  17. 24 10月, 2016 2 次提交
  19. 16 6月, 2016 1 次提交
  21. 07 6月, 2016 1 次提交
  23. 05 2月, 2016 1 次提交
    • P
      util: Clean up includes · aafd7584
      由 Peter Maydell 提交于 
      Clean up includes so that osdep.h is included first and headers
which it implies are not included manually.

This commit was created with scripts/clean-includes.
Signed-off-by: NPeter Maydell <peter.maydell@linaro.org>
Message-id: 1454089805-5470-6-git-send-email-peter.maydell@linaro.org
      aafd7584
  25. 23 6月, 2015 1 次提交
  27. 28 4月, 2015 3 次提交
  29. 10 12月, 2014 1 次提交
  31. 11 6月, 2014 1 次提交
  33. 16 2月, 2013 1 次提交
  35. 03 2月, 2013 1 次提交
  37. 26 1月, 2013 2 次提交
    • P
      hbitmap: add assertion on hbitmap_iter_init · 1b095244
      由 Paolo Bonzini 提交于 
      hbitmap_iter_init causes an out-of-bounds access when the "first"
argument is or greater than or equal to the size of the bitmap.
Forbid this with an assertion, and remove the failing testcase.
Reported-by: NKevin Wolf <kwolf@redhat.com>
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>
Reviewed-by: NEric Blake <eblake@redhat.com>
Reviewed-by: NLaszlo Ersek <lersek@redhat.com>
Signed-off-by: NKevin Wolf <kwolf@redhat.com>
      1b095244
    • P
      add hierarchical bitmap data type and test cases · e7c033c3
      由 Paolo Bonzini 提交于 
      HBitmaps provides an array of bits.  The bits are stored as usual in an
array of unsigned longs, but HBitmap is also optimized to provide fast
iteration over set bits; going from one bit to the next is O(logB n)
worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
that the number of levels is in fact fixed.

In order to do this, it stacks multiple bitmaps with progressively coarser
granularity; in all levels except the last, bit N is set iff the N-th
unsigned long is nonzero in the immediately next level.  When iteration
completes on the last level it can examine the 2nd-last level to quickly
skip entire words, and even do so recursively to skip blocks of 64 words or
powers thereof (32 on 32-bit machines).

Given an index in the bitmap, it can be split in group of bits like
this (for the 64-bit case):

     bits 0-57 => word in the last bitmap     | bits 58-63 => bit in the word
     bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word
     bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word

So it is easy to move up simply by shifting the index right by
log2(BITS_PER_LONG) bits.  To move down, you shift the index left
similarly, and add the word index within the group.  Iteration uses
ffs (find first set bit) to find the next word to examine; this
operation can be done in constant time in most current architectures.

Setting or clearing a range of m bits on all levels, the work to perform
is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap.

When iterating on a bitmap, each bit (on any level) is only visited
once.  Hence, The total cost of visiting a bitmap with m bits in it is
the number of bits that are set in all bitmaps.  Unless the bitmap is
extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized
cost of advancing from one bit to the next is usually constant.
Reviewed-by: NLaszlo Ersek <lersek@redhat.com>
Reviewed-by: NEric Blake <eblake@redhat.com>
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>
Signed-off-by: NKevin Wolf <kwolf@redhat.com>
      e7c033c3