osd/osd_types: add explicit hash to object_locator_t

Instead of hashing the object name or key, we allow the hash position to be
provided explicitly.

Signed-off-by: Sage Weil <sage@inktank.com>
osd/OSDMap: use new object_locator_t::hash to place object in a pg

The hash value, is provided, becomes the ps (placement seed) portion of the
pg_t, skipping any hashing of the object name (or locator key).

Signed-off-by: Sage Weil <sage@inktank.com>
common/bloom_filter: make compressible_bloom_filter encodable

Signed-off-by: Sage Weil <sage@inktank.com>
osd_types: add generic HitSet type with bloom and explicit implementations

Track a set of hash values, either explicitly or using a bloom_filter. Hide
the implementation and allow us to transparently encode and decode.

Signed-off-by: Sage Weil <sage@inktank.com>
osd/osd_types: add pg_hit_set_{info,history}_t

Signed-off-by: Sage Weil <sage@inktank.com>
librados: stubs for minimal hit set interface

Signed-off-by: Sage Weil <sage@inktank.com>
librados: stubs to determine hash position when enumerating objects

Signed-off-by: Sage Weil <sage@inktank.com>
librados: stub to begin enumerating objects starting from a hash position

Signed-off-by: Sage Weil <sage@inktank.com>
common/bloom_filter: drop raw_table_size_ member

We were storing table_size_ and raw_table_size_, where one is the size in
bits and the other is the size in bytes.  This is silly.  Store only the
size in bytes.

Also, bytes are always 8 bits, so use bit shifts and drop some of that
silliness too.

Move the member declarations to the top of the class so you read them
before the methods.

Fix some annoying whitespace.

Avoid allocating a 0-length array.

Mark the encoding incompatible with v1.

Signed-off-by: Sage Weil <sage@inktank.com>
osd/osd_types: include pg_hit_set_history_t in pg_info_t

Track metadata about the currently accumulating HitSet as well as
previously archived ones in the pg_info_t.  This will not scale well for
extremely long histories, but does let us avoid explicitly sharing this
metadata during recovery or other normal update activity.

Signed-off-by: Sage Weil <sage@inktank.com>
wip