This is a self-locking wrapper around virHashTable. Only a limited set
of APIs are implemented now (the ones which are used in the following
patch) as more can be added on demand.
Signed-off-by: NJiri Denemark <jdenemar@redhat.com>

I almost wrote a hash value free function that just called
VIR_FREE, then realized I couldn't be the first person to
do that.  Sure enough, it was worth factoring into a common
helper routine.

* src/util/virhash.h (virHashValueFree): New function.
* src/util/virhash.c (virHashValueFree): Implement it.
* src/util/virobject.h (virObjectFreeHashData): New function.
* src/libvirt_private.syms (virhash.h, virobject.h): Export them.
* src/nwfilter/nwfilter_learnipaddr.c (virNWFilterLearnInit): Use
common function.
* src/qemu/qemu_capabilities.c (virQEMUCapsCacheNew): Likewise.
* src/qemu/qemu_command.c (qemuDomainCCWAddressSetCreate):
Likewise.
* src/qemu/qemu_monitor.c (qemuMonitorGetBlockInfo): Likewise.
* src/qemu/qemu_process.c (qemuProcessWaitForMonitor): Likewise.
* src/util/virclosecallbacks.c (virCloseCallbacksNew): Likewise.
* src/util/virkeyfile.c (virKeyFileParseGroup): Likewise.
* tests/qemumonitorjsontest.c
(testQemuMonitorJSONqemuMonitorJSONGetBlockInfo): Likewise.
Signed-off-by: NEric Blake <eblake@redhat.com>

Any source file which calls the logging APIs now needs
to have a VIR_LOG_INIT("source.name") declaration at
the start of the file. This provides a static variable
of the virLogSource type.
Signed-off-by: NDaniel P. Berrange <berrange@redhat.com>

'const fooPtr' is the same as 'foo * const' (the pointer won't
change, but it's contents can).  But in general, if an interface
is trying to be const-correct, it should be using 'const foo *'
(the pointer is to data that can't be changed).

Fix up virhash to provide a const-correct interface: all actions
that don't modify the table take a const table.  Note that in
one case (virHashSearch), we actually strip const away - we aren't
modifying the contents of the table, so much as associated data
for ensuring that the code uses the table correctly (if this were
C++, it would be a case for the 'mutable' keyword).

* src/util/virhash.h (virHashKeyComparator, virHashEqual): Use
intended type.
(virHashSize, virHashTableSize, virHashLookup, virHashSearch):
Make const-correct.
* src/util/virhash.c (virHashEqualData, virHashEqual)
(virHashLookup, virHashSize, virHashTableSize, virHashSearch)
(virHashComputeKey): Fix fallout.
* src/conf/nwfilter_params.c
(virNWFilterFormatParameterNameSorter): Likewise.
* src/nwfilter/nwfilter_ebiptables_driver.c
(ebiptablesFilterOrderSort): Likewise.
* tests/virhashtest.c (testHashGetItemsCompKey)
(testHashGetItemsCompValue): Likewise.
Signed-off-by: NEric Blake <eblake@redhat.com>

Implement function to remove all entries of a hash table.

Return statements with parameter enclosed in parentheses were modified
and parentheses were removed. The whole change was scripted, here is how:

List of files was obtained using this command:
git grep -l -e '\<return\s*([^()]*\(([^()]*)[^()]*\)*)\s*;' |             \
grep -e '\.[ch]$' -e '\.py$'

Found files were modified with this command:
sed -i -e                                                                 \
's_^\(.*\<return\)\s*(\(\([^()]*([^()]*)[^()]*\)*\))\s*\(;.*$\)_\1 \2\4_' \
-e 's_^\(.*\<return\)\s*(\([^()]*\))\s*\(;.*$\)_\1 \2\3_'

Then checked for nonsense.

The whole command looks like this:
git grep -l -e '\<return\s*([^()]*\(([^()]*)[^()]*\)*)\s*;' |             \
grep -e '\.[ch]$' -e '\.py$' | xargs sed -i -e                            \
's_^\(.*\<return\)\s*(\(\([^()]*([^()]*)[^()]*\)*\))\s*\(;.*$\)_\1 \2\4_' \
-e 's_^\(.*\<return\)\s*(\([^()]*\))\s*\(;.*$\)_\1 \2\3_'

On RHEL5, I got:
util/virrandom.c:66: warning: nested extern declaration of '_gl_verify_function66' [-Wnested-externs]

The fix is to hoist the verify earlier.  Also some other hodge-podge
fixes I noticed while reviewing Dan's recent series.

* .gitignore: Ignore new test.
* src/util/cgroup.c: Bump copyright year.
* src/util/virhash.c: Fix typo in description.
* src/util/virrandom.c (virRandomBits): Mark doc comment, and
hoist assert to silence older gcc.

Recent discussions have illustrated the potential for DOS attacks
with the hash table implementations used by most languages and
libraries.

   https://lwn.net/Articles/474912/

libvirt has an internal hash table impl, and uses hash tables for
a variety of purposes. The hash key generation code is pretty
simple and thus not strongly collision resistant.

This patch replaces the current libvirt hash key generator with
the (public domain) Murmurhash3 code. In addition every hash
table now gets a random seed value which is used to perturb the
hashing code. This should make it impossible to mount any
practical attack against libvirt hashing code.

* bootstrap.conf: Import bitrotate module
* src/Makefile.am: Add virhashcode.[ch]
* src/util/util.c: Make virRandom() return a fixed 32 bit
  integer value.
* src/util/hash.c, src/util/hash.h, src/util/cgroup.c: Replace
  hash code generation with a call to virHashCodeGen()
* src/util/virhashcode.h, src/util/virhashcode.c: Add a new
  virHashCodeGen() API using the Murmurhash3 algorithm.

In preparation for the patch to include Murmurhash3, which
introduces a virhashcode.h and virhashcode.c files, rename
the existing hash.h and hash.c to virhash.h and virhash.c
respectively.

In preparation for conversion over to use the Murmurhash3
algorithm, convert various virHash APIs to use size_t or
uint32 for their return values/parameters, instead of the
variable size 'unsigned long' or 'int' types

Add function to compare two hash tables for equality.

Add a function to the virHashTable for getting an array of the hash table's
key-value pairs and have the keys (optionally) sorted.
Signed-off-by: NStefan Berger <stefanb@linux.vnet.ibm.com>

I noticed a couple typos in recent commits, and fixed the remaining
instances of them.

* docs/internals/command.html.in: Fix spelling errors.
* include/libvirt/libvirt.h.in (virConnectDomainEventCallback):
Likewise.
* python/libvirt-override.py (virEventAddHandle): Likewise.
* src/lxc/lxc_container.c (lxcContainerChild): Likewise.
* src/util/hash.c (virHashCreateFull): Likewise.
* src/storage/storage_backend_logical.c
(virStorageBackendLogicalMakeVol): Likewise.
* src/esx/esx_driver.c (esxFormatVMXFileName): Likewise.
* src/vbox/vbox_tmpl.c (vboxIIDIsEqual_v3_x): Likewise.

These VIR_XXXX0 APIs make us confused, use the non-0-suffix APIs instead.

How do these coversions works? The magic is using the gcc extension of ##.
When __VA_ARGS__ is empty, "##" will swallow the "," in "fmt," to
avoid compile error.

example: origin				after CPP
	high_level_api("%d", a_int)	low_level_api("%d", a_int)
	high_level_api("a  string")	low_level_api("a  string")

About 400 conversions.

8 special conversions:
VIR_XXXX0("") -> VIR_XXXX("msg") (avoid empty format) 2 conversions
VIR_XXXX0(string_literal_with_%) -> VIR_XXXX(%->%%) 0 conversions
VIR_XXXX0(non_string_literal) -> VIR_XXXX("%s", non_string_literal)
  (for security) 6 conversions
Signed-off-by: NLai Jiangshan <laijs@cn.fujitsu.com>

Commit 1671d1dc introduced a memory leak in virHashFree, and
wholesale table corruption in virHashRemoveSet (elements not
requested to be freed are lost).

* src/util/hash.c (virHashFree): Free bucket array.
(virHashRemoveSet): Don't lose elements.
* tests/hashtest.c (testHashCheckForEachCount): New method.
(testHashCheckCount): Expose the bug.

So far first entries for each hash key are stored directly in the hash
table while other entries mapped to the same key are linked through
pointers. As a result of that, the code is cluttered with special
handling for the first items.

This patch makes all entries (even the first ones) linked through
pointers, which significantly simplifies the code and makes it more
maintainable.

This adds several tests for remaining hash APIs (custom
hasher/comparator functions are not covered yet, though).

All tests pass both before and after the "Simplify hash implementation".

Commit 9677cd33 made it possible to
remove current entry when iterating through all hash entries. However,
it didn't properly handle a special case of removing first entry
assigned to a given key which contains several entries in its collision
list.

Calling most hash APIs is not safe from inside of an iterator callback.
Exceptions are APIs that do not modify the hash table and removing
current hash entry from virHashFroEach callback.

This patch make all APIs which are not safe fail instead of just relying
on the callback being nice not calling any unsafe APIs.

This fixes a possible crash of libvirtd during its startup. When qemu
driver reconnects to running domains, it iterates over all domain
objects in a hash. When reconnecting to an associated qemu monitor
fails and the domain is transient, it's immediately removed from the
hash. Despite the fact that it's explicitly forbidden to do so. If
libvirtd is lucky enough, virHashForEach will access random memory when
the callback finishes and the deamon will crash.

Since it's trivial to fix virHashForEach to allow removal of hash
entries while iterating through them, I went this way instead of fixing
qemuReconnectDomain callback (and possibly others) to avoid deleting the
entries.

Relax the restriction that the hash table key must be a string
by allowing an arbitrary hash code generator + comparison func
to be provided

* util/hash.c, util/hash.h: Allow any pointer as a key
* internal.h: Include stdbool.h as standard.
* conf/domain_conf.c, conf/domain_conf.c,
  conf/nwfilter_params.c, nwfilter/nwfilter_gentech_driver.c,
  nwfilter/nwfilter_gentech_driver.h, nwfilter/nwfilter_learnipaddr.c,
  qemu/qemu_command.c, qemu/qemu_driver.c,
  qemu/qemu_process.c, uml/uml_driver.c,
  xen/xm_internal.c: s/char */void */ in hash callbacks

Since the deallocator is passed into the constructor of
a hash table it is not desirable to pass it into each
function again. Remove it from all functions, but provide
a virHashSteal to allow a item to be removed from a hash
table without deleteing it.

* src/util/hash.c, src/util/hash.h: Remove deallocator
  param from all functions. Add virHashSteal
* src/libvirt_private.syms: Add virHashSteal
* src/conf/domain_conf.c, src/conf/nwfilter_params.c,
  src/nwfilter/nwfilter_learnipaddr.c,
  src/qemu/qemu_command.c, src/xen/xm_internal.c: Update
  for changed hash API

Remove the <stdbool.h> header from all source files / headers
and just put it into internal.h

* src/internal.h: Add <stdbool.h>

Two-argument free functions are uncommon; match the style elsewhere
by caching the callback at creation.

* src/util/hash.h (virHashCreate, virHashFree): Move deallocator
argument to creation.
* cfg.mk (useless_free_options): Add virHashFree.
* src/util/hash.c (_virHashTable): Track deallocator.
(virHashCreate, virHashFree): Update to new signature.
* src/conf/domain_conf.c (virDomainObjListDeinit)
(virDomainObjListInit, virDomainDiskDefForeachPath)
(virDomainSnapshotObjListDeinit, virDomainSnapshotObjListInit):
Update callers.
* src/conf/nwfilter_params.c (virNWFilterHashTableFree)
(virNWFilterHashTableCreate): Likewise.
* src/conf/nwfilter_conf.c (virNWFilterTriggerVMFilterRebuild):
Likewise.
* src/cpu/cpu_generic.c (genericHashFeatures, genericBaseline):
Likewise.
* src/xen/xm_internal.c (xenXMOpen, xenXMClose): Likewise.
* src/nwfilter/nwfilter_learnipaddr.c (virNWFilterLearnInit)
(virNWFilterLearnShutdown): Likewise.
* src/qemu/qemu_command.c (qemuDomainPCIAddressSetCreate)
(qemuDomainPCIAddressSetFree): Likewise.
* src/qemu/qemu_process.c (qemuProcessWaitForMonitor): Likewise.

The only difference between these 2 functions is that one errors
out when the entry is already present while the other modifies
the existing entry. Add an helper function with a boolean argument
indicating whether existing entries should be updated or not, and
use this helper in both functions.

The code in virHashUpdateEntry and virHashAddEntry is really
similar. However, the latter rebalances the hash table when
one of its buckets contains too many elements while the former
does not. Fix this discrepancy.

* src/util/hash.c (virHashGrow) [DEBUG_GROW]: Use modern logging.
Reported by Christophe Fergeau.

A couple of allocation were not calling virReportOOMError on allocation
errors

* src/util/hash.c: add the needed call in virHashCreate and
  virHashAddOrUpdateEntry

* src/util/hash.c: virHashAddEntry and virHashUpdateEntry were missing NULL
  checks on strdup
* AUTHORS: add Christophe Fergeau

Signed-off-by: NChris Lalancette <clalance@redhat.com>

Most of the hash iterators need to modify either payload of
data args. The const annotation prevents this.

* src/util/hash.h, src/util/hash.c: Remove const-ness from
  virHashForEach/Iterator
* src/xen/xm_internal.c: Remove bogus casts

* src/bridge.c, src/bridge.h, src/buf.c, src/buf.h, src/cgroup.c,
  src/cgroup.h, src/conf.c, src/conf.h, src/event.c, src/event.h,
  src/hash.c, src/hash.h, src/hostusb.c, src/hostusb.h,
  src/iptables.c, src/iptables.h, src/logging.c, src/logging.h,
  src/memory.c, src/memory.h, src/pci.c, src/pci.h, src/qparams.c,
  src/qparams.h, src/stats_linux.c, src/stats_linux.h,
  src/threads-pthread.c, src/threads-pthread.h, src/threads-win32.c,
  src/threads-win32.h, src/threads.c, src/threads.h, src/util.c,
  src/util.h, src/uuid.c, src/uuid.h, src/virterror.c,
  src/virterror_internal.h, src/xml.c, src/xml.h: Move all files
  into src/util/
* daemon/Makefile.am: Add -Isrc/util/ to build flags
* src/Makefile.am: Add -Isrc/util/ to build flags and update for
  moved files
* src/libvirt_private.syms: Export cgroup APIs since they're now
  in util rather than linking directly to drivers
* src/xen/xs_internal.c: Disable bogus virEventRemoveHandle call
  when built under PROXY
* proxy/Makefile.am: Update for changed file locations. Remove
  bogus build of event.c
* tools/Makefile.am, tests/Makefile.am: Add -Isrc/util/ to build flags

* src/capabilities.c, src/capabilities.h, src/domain_conf.c,
  src/domain_conf.h, src/domain_event.c, src/domain_event.h,
  src/interface_conf.c, src/interface_conf.h,
  src/network_conf.c, src/network_conf.h, src/node_device_conf.c,
  src/node_device_conf.h, src/secret_conf.c, src/secret_conf.h,
  src/storage_conf.c, src/storage_conf.h, src/storage_encryption_conf.c,
  src/storage_encryption_conf.h: Move to src/conf/
* src/Makefile.am: Add -Isrc/conf to the individual build targets
  which need to use XML config APIs. Remove LIBXML_CFLAGS, LIBSSH2_CFLAGS
  and SELINUX_CFLAGS from global INCLUDES and only have them in build
  targets which actually need them.  Create a libvirt_conf.la
  convenience library for all config parsers
* src/hostusb.h: Remove bogus include of domain_conf.h
* tests/Makefile.am: Add -Isrc/conf. Remove bogus -I$builddir/src
  since it never has any generated header files
* daemon/Makefile.am: Add -Isrc/conf
* proxy/Makefile.am: Add -Isrc/conf and cope with renamed files
* src/hash.c: Remove bogus include of libxml/threads.h