Fix typo in CHANGELOG.md

Moved space to the correct place.

Signed-off-by: Simon Hürlimann <simon.huerlimann@cyt.ch>
Signed-off-by: Liu Yuan <namei.unix@gmail.com>
sheep/http: add nolock version for onode_lookup()

Remove lock from onode_create() and add nolock version
for onode_lookup()

Signed-off-by: Robin Dong <sanbai@taobao.com>
Signed-off-by: Liu Yuan <namei.unix@gmail.com>
sheep/http: change routine of kv_create_object()

At present, the implemention of swift interface for creating object in sheepdog
is:

1. lock container
2. check whether the onode with same object name is exists.
3. unlock container
4. upload object
5. create onode

this sequence have a problem: if two clients uploading same objects
concurrently, it will create two objects with same names in container.
To avoid duplicated names, we must put "create onode" operation in container
lock regions.

Therefore we need to change the processes of creating object to:

1. lock container
2. check whether the onode is exists.
3. allocate data space for object, and create onode, then write it done
4. unlock container
5. upload object

this routine will avoid uploading duplicated objects.

Therefore, we change routine of kv_create_object(): create onode and alloc
space first, then recveive data from fastcgi of http, and write it.

Signed-off-by: Robin Dong <sanbai@taobao.com>
Signed-off-by: Liu Yuan <namei.unix@gmail.com>
sheep/cluster: let local_lock() support nested

In kv_create_object(), we need to lock bucket and then lock allocator of it:

    lock(bucket_vid)
        lock(data_vid)
        unlock(data_vid)
    unlock(bucket_vid)

so the implementations of ->lock() for 'local' in cluster must support nested
lock.

The pthread_mutex_t with attribute of "PTHREAD_PROCESS_SHARED" could used by
threads in different processes.
(ref: http://stackoverflow.com/questions/17809231/mutex-attribute-pthread-process-shared-inverts-logic,
http://royontechnology.blogspot.com/2007/06/comparison-of-pthreadprocessshared-in.html)

First, we create a 'global_lock' to protect lock_tree, then we can create new
'SHARED' lock to use. Since the pthread_mutex_t is actually store in files, we
must check the exists of files before init mutex on mmap-memory.

Signed-off-by: Robin Dong <sanbai@taobao.com>
Signed-off-by: Liu Yuan <namei.unix@gmail.com>
sheep/http: add flag for onode

The processes of creating object is:

1. lock container
2. check whether the onode is exists.
3. allocate data space for object, and create onode, then write it done
4. unlock container
5. upload object

This routine will avoid uploading duplicated objects but have  an exception:
if the client halt the uploading progress, we will have a
"uploading incompleted" onode.

The solution is: we can add code for onode to identify its status.
A new onode will be set to "INIT", and after uploading completed, the onode will
be set to  "COMPLETED". So, when users try to use swift interface to GET a
"incompleted" object, sheep will find out the onode is "INIT" which means
"not completed", so sheep will return "partial content"for http request, and
user could remove the object and upload it again.

Signed-off-by: Robin Dong <sanbai@taobao.com>
Signed-off-by: Liu Yuan <namei.unix@gmail.com>
sheep/http: allow 'Force: true' http header to delete 'incompleted' object forcely

Imaging a scenario:

1. Client A is uploading a large object which names 'elephant', it
   only allocate meta-data in oalloc and is creating SD_OBJ_DATA files.
2. Client B send a DELETE request to remove object 'elephant', it
   will remove all the backend files for 'elephant'.
   At the same time, Client A dosen't know what happend because uploading
   progress don't need to lock any vdi.
3. Client A return Create-object-success, but the real data have all been
   removed.

To avoid this scenario, we let DELETE operation do nothing but only return
'CONFLICT' when the object is 'incompleted'. And, users can send the DELETE
request with a new header 'Force: true' which will remove 'incompleted'
object forcely when users make sure that there isn't any uploading progress
for this object.

Signed-off-by: Robin Dong <sanbai@taobao.com>
Signed-off-by: Liu Yuan <namei.unix@gmail.com>
tests: add test case for new kv_create_object() implemention

Signed-off-by: Robin Dong <sanbai@taobao.com>
Signed-off-by: Liu Yuan <namei.unix@gmail.com>
sheep/md: change process of for_each_object_in_wd() to multi-threads

In our test environment, we upload 6TB data and kill one node, then the sheep
daemons on each server will try to rename files from 'data' to '.stale', but
the rename operations cost almost half an hour. And in this half an hour, the
whole cluster can't be read or write.

To accelerate the speed of renames, we change for_each_object_in_wd() to
multi-threads, which is one thread for one disk.

Signed-off-by: Robin Dong <sanbai@taobao.com>
Signed-off-by: Liu Yuan <namei.unix@gmail.com>
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.  This also reduces the vdi header size.

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>
tests: show ledger objects in list

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>
doc: add documentation of object reclaim algorithm

Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>