dog/vdi: bug fix for voting majority, add test case to test it

There is a critical error in the function vote_majority_object.
When all the three copies are different, the original logic still
choose the last one as majority.
The root cause is step 2 of the voting algorithm was missed.

Signed-off-by: Ruoyu <liangry@ucweb.com>
Reviewed-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: Liu Yuan <namei.unix@gmail.com>
tests/functional: use dog instead of qemu-img in 016

It seems that qemu-img command has a bug of using cluster's nr_copies
instead of vdi's original nr_copies when it creates snapshot. This
patch lets 016 not use qemu-img.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
dog: use nr_copies of inode object instead of command line parameter

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
dog: forbid creating snapshot of hypervolume

Currently it is not supported.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
sheep: introduce generational reference counting for object reclaim

Generational reference counting is an algorithm to reclaim data
efficiently without race conditions on distributed system.  This
extends vdi objects structure to store generational reference counts,
and increments the counts when creating snapshots.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
sheep: introduce ledger objects

This introduces ledger objects, which keeps track of the number of
outstanding references of each generation.  Sheep decrements a
generational reference count with a gateway request SD_OP_DECREF_OBJ,
and reclaims objects when there is no generational reference.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
sheep: decrement generational reference count on vdi deletion

This removes old vdi deletion code, which reclaims objects only when
all relevant snapshots are deleted, and uses a generational reference
counting algorithm.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
sheep: decrement generational reference count on copy-on-write

This decrements a reference count of the old data object when
allocating a new data object on CoW.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
sheep: remove max children limit

We no longer need it.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
sheep: introduce sparse objects

We don't need to care about a fragmentation when
 - the object is unlikely to be accessed sequentially, and
 - the object is read-only.

In that sense, we can make the objects sparse if they are not data
objects and writable ones.

This fixes the problem that sheepdog consumes many disk spaces for
deleted vdi objects if your filesystem supports FALLOC_FL_PUNCH_HOLE.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
sheepdog proto: recycle old child_vdi_id for storing btree_counter

Now the area isn't used and clients (QEMU and tgt) don't care about
it, we can recycle it for storing the btree_counter.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
sheep: update store format version to v5

This patchset introduces two important change for sheep store:
1. generational reference counting: adding ledger object and expand
   inode object for generation reference
2. changing a place of btree_counter in inode object

Incrementing SD_FORMAT_VERSION in either of them would be
confusing. So this independent patch updates the number.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
tests: show ledger objects in list

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
doc: add documentation of object reclaim algorithm

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
tests/functional: add test for object reclaim

This patch also removes existing test 086. 086 tests the clone
functionality and it depends on a max number of clones. But the object
reclaim scheme removes the maximum number. Hence the test becomes
obsolete. This patch adds a new test for the object reclaim as 086.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
update CHANGELOG.md for new object reclaim scheme

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
tests/functional: add a new test of the object reclaim for cloned VDIs

This patch adds a new test of the object reclaim algorithm. The test
creates branch of VDI tree and checks the GC works well for the case.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
tests/functional: new test of object reclaim for a case of continuously snapshotted VDI

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
dog: add a new subcommand "dog vdi object dump-inode" for diagnosing inode object

Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
sheep: get_request() for deferred response