add forward error correction for erasure code

This is imported and based on zfec

Signed-off-by: Liu Yuan <namei.unix@gmail.com>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
gateway: remove init_target_nodes

Signed-off-by: Liu Yuan <namei.unix@gmail.com>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
gateway: remove shortcut for local node in gateway_forward_request

Shortcut forward-reqeust to local node doesn't improve performance a lot because
we forward the requests to many nodes concurrently and wait for all the
responses of all the requests, slowest one determine the how long we take for
this request.

Removing the shortcut for local node doesn't reduce the performance but result
in a more simplifed code.

Signed-off-by: Liu Yuan <namei.unix@gmail.com>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
gateway: rename write_info as forward_info

Signed-off-by: Liu Yuan <namei.unix@gmail.com>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
gateway: support forward read request

Signed-off-by: Liu Yuan <namei.unix@gmail.com>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
gateway: allow sending different requests to replica

This is a preparation patch

Signed-off-by: Liu Yuan <namei.unix@gmail.com>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
sheep: use copy_policy to control erasure vdi

inode->copy_policy is a good place to control erasure coded vdi. But I don't
think we need uint16_t for it, so I just allocate uint8_t for it.

to create a erasure coded vdi:

$dog vdi create -e test 10G # This will create a erasure coded vdi

For now we only use a fixed scheme (4 data and 2 parity strips) with '-e'. But
I have '-e number' in plan, that users could specify how many parity replica he
wants with different erasure scheme for different vdis. E.g, we can have

-e 2 --> 4 : 2 (0.5 redundancy and can stand with 2 nodes failure)
-e 3 --> 8 : 3 (0.375 redunandcy and can stand with 3 nodes failure)
-e 4 --> 8 : 4 (0.5 redandancy and can stand with 4 nodes failure)

Signed-off-by: Liu Yuan <namei.unix@gmail.com>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
erasure: add basic read/write code proper

Instead of storing copy in the replica, erasure code tries to spread data on all
the replica to achieve the same fault tolerance while reducing the redundancy to
minimal.

For a simple test on my box, aligned-4k write get 1.5x faster than replication
at most, while read get 1.15x faster, compared with copies=3 (4:2 scheme)

For 6 nodes cluster with 1000Mb/s NIC, I got the following result:

replication(3 copies): write 36.5 MB/s, read 71.8 MB/s
erasure code(4 : 2)  : write 46.6 MB/s, read 82.9 MB/

/*
 * Stripe: data strips + parity strips, spread on all replica
 * DS: data strip
 * PS: parity strip
 * R: Replica
 *
 *  +--------------------stripe ----------------------+
 *  v                                                 v
 * +----+----------------------------------------------+
 * | ds | ds | ds | ds | ds | ... | ps | ps | ... | ps |
 * +----+----------------------------------------------+
 * | .. | .. | .. | .. | .. | ... | .. | .. | ... | .. |
 * +----+----+----+----+----+ ... +----+----+-----+----+
 *  R1    R2   R3   R4   R5   ...   Rn  Rn+1  Rn+2  Rn+3
 */

We use replica to hold data and parity strips. Suppose we have a
4:2 scheme, 4 data strips and 2 parity strips on 6 replica and strip size = 1k,
so basically we'll generate 2k parites for each 4k write, we call this 6K as
stripe as a whole. For write, we'll horizontally spread data, not vertically as
replciation. So for read, we have to assemble the strip from all the data
replica.

The downsize for erasure coding is:
1. for recovery, we have to recover 0.5x more data
2. if any replica fails, we have to wait for its recover for read.
3. it needs at least 6(4+2) nodes to work.

Signed-off-by: Liu Yuan <namei.unix@gmail.com>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
erasure: add unligned write support

unligned write is that either 'offset' or 'offset + length' isn't aligned to
SD_EC_D_SIZE. In this case, we have to read data stripes that hold the
unaligned write part(s) before write.

Signed-off-by: Liu Yuan <namei.unix@gmail.com>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
change copy type from uint32_t to uint8_t

We can't add more field into sd_req.obj. But we can make use of 'uint32_t copies'
which effectively we only use its first 8 bytes. By squeezing copy_policy into
this room, we won't change the layout of sd_req.

For now copy_policy is just used by sheep and dog, so no need to change the QEMU
code at all.

Signed-off-by: Liu Yuan <namei.unix@gmail.com>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>
make dog copy_policy aware

- add copy_plicy to sd_write_object()
- farm is copy_policy aware too
- we can pass copy_plicy in struct sd_req, which means that even if the vdi
isn't registered in the sheep, we can still give sheep enough information it is
an easure object or not. This is required by cluster snapshot operation.

With this patch, we can pass functional/030

Signed-off-by: Liu Yuan <namei.unix@gmail.com>
Signed-off-by: MORITA Kazutaka <morita.kazutaka@lab.ntt.co.jp>