[Qemu-devel] [PATCH v4 00/14] tb hash improvements

[Emilio G. Cota]

Changes from v3:

- added reviewed-by tags from v3. I dropped the review tags from the
  'qht' and 'info jit' patches because they have changed quite a bit
  from v3.
- qdist: new module to print intuitive histograms, see 'info jit' below.
- qht:
  + bug fix: remove unnecessary requirement of hashes being !0; the
    only requirement is that pointers must be !NULL.
    * qht-test: hash the integers we insert with their own integer values
      instead of using tb_hash_func5. This gives us better control
      of the hash values we're testing, and anyway the values we
      test are all unique, so this doesn't matter.
  + bug fix: was not setting map->n_items to 0 in qht_reset().
  + Do not leave NULL holes after removals. Instead, swap this hole
    with the last valid item in the chain. Performance-wise this
    makes no difference when resize is on; however, without resize
    the gain is measurable.
    * A consequence of this is a slight change in MRU promotion: the
      last item in the head bucket is simply swapped with orig[pos],
      without bringing orig to head->next.
    * Added bucket corruption checks, enabled with #define QHT_DEBUG.
  + Do not set QHT_MODE_MRU_INSERT for the TB hash. With long chains it
    causes quite a performance decrease; with short chains, such as what
    we have with xxhash + auto-resize, it has no measurable performance
    impact.
  + 'info jit' stats:
    * Report the number of empty buckets
    * Do not count empty buckets when reporting avg bucket chain length;
      by doing this we get an idea of how many buckets the average lookup
      is going through.
    * Report the avg bucket chain length + a histogram for its distribution.
    * Report avg bucket chain occupancy (in %) + its distribution's histogram.
  + qht-test: add a few more test cases
  + header guard: s/define QHT_H/define QEMU_QHT_H/
  + consistently use uint32_t for keeping the result of tb_hash_func()
  + avoid false leak reports from valgrind after calling call_rcu(map)
    by placing the 'struct rcu_head' field at the top of struct qht_map.
- define QEMU_ALIGNED(X) instead of QEMU_ALIGNED(B)
- add copyright + license to include/processor.h
- add atomic_test_and_set to include/atomic.h, using __atomic_test_and_set
  when available.
- spinlock:
  + use newly-added atomic_test_and_set instead of atomic_xchg
  + remove TATAS for spin_try_lock

Thanks,

                Emilio