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.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
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.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
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.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
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.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
sheep: remove max children limit

We no longer need it.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
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.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
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.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
sheep: get_request() for deferred response

With the new function, response message to clients can be deferred
safely without blocking the main thread.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
sheep, dog: prevent COW during snapshot creation

Current generational reference counting scheme for garbage collection
of snapshot object requires mutual exclusion between COW operation and
snapshot creation. Because both of COW operation and snapshot creation
requires modification of generation reference status. This patch adds
operations for preventing/allowing COW temporally.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
sheep: reduce needless remove request during object reclamation

The previous reference decrement operation issued too many (and not
required) remove requests. It harms performance and produces
meaningless error logs. This patch reduces the needless requests.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
sheep, dog: migrate deletion process from sheep to dog

Deletion process also requires modification of generational reference
status so it must not be executed with snapshot creation or COW
request at the same time.

This patch migrates deletion process from sheep to dog. The new
deletion process in dog is simply implemented as COW: zero filling
sd_inode->data_vdi_id[] and write it to sheep cluster. The GC code can
decrement reference by this inode update.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
dog: print status of generational reference of inodes in dump-inode

This patch lets "dog vdi object dump-inode" print status of
generational reference.

Example of output:
name: test
tag:
create_time: 53704f51349aa108
snap_ctime: 0
vm_clock_nsec: 0
copy_policy: 0
store_policy: 0
nr_copies: 3
block_size_shift: 22
snap_id: 2
vdi_id: 7c2b26
parent_vdi_id: 7c2b25
btree_counter: 0
data_vdi_id:
0: 8137509
gref:
1: 0

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
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.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
tests: show ledger objects in list

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
doc: add documentation of object reclaim algorithm

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
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.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
update CHANGELOG.md for new object reclaim scheme

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
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.

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>
tests/functional: new test of object reclaim for a case of continuously snapshotted VDI

Cc: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
Tested-by: Valerio Pachera <sirio81@gmail.com>
Cc: Alessandro Bolgia <alessandro@extensys.it>
Signed-off-by: Hitoshi Mitake <mitake.hitoshi@lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@gmail.com>