Adding upstream version 18.2.2.upstream/18.2.2

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 468 insertions, 0 deletions

diff --git a/src/erasure-code/ErasureCodeInterface.h b/src/erasure-code/ErasureCodeInterface.h
new file mode 100644
index 000000000..b0c24e1e4
--- /dev/null
+++ b/src/erasure-code/ErasureCodeInterface.h
@@ -0,0 +1,468 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- 
+// vim: ts=8 sw=2 smarttab
+/*
+ * Ceph distributed storage system
+ *
+ * Copyright (C) 2013 Cloudwatt <libre.licensing@cloudwatt.com>
+ *
+ * Author: Loic Dachary <loic@dachary.org>
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Lesser General Public
+ *  License as published by the Free Software Foundation; either
+ *  version 2.1 of the License, or (at your option) any later version.
+ * 
+ */
+
+#ifndef CEPH_ERASURE_CODE_INTERFACE_H
+#define CEPH_ERASURE_CODE_INTERFACE_H
+
+/*! @file ErasureCodeInterface.h
+    @brief Interface provided by erasure code plugins
+
+    The erasure coded pools rely on plugins implementing
+    **ErasureCodeInterface** to encode and decode content. All codes
+    are systematic (i.e. the data is not mangled and can be
+    reconstructed by concatenating chunks ).
+    
+    Methods returning an **int** return **0** on success and a
+    negative value on error. If the value returned on error is not
+    explained in **ErasureCodeInterface**, the sources or the
+    documentation of the interface implementer (i.e. the plugin ) must
+    be read to figure out what it means. It is recommended that each
+    error code matches an *errno* value that relates to the cause of
+    the error.
+
+    If an object is small enough, the caller can process it with
+    one call to the **encode** or **decode** method.
+
+	+---------------- coded object O -------------------------+
+	|+----------------+ +----------------+ +----------------+ |
+	||    chunk  0    | |    chunk  1    | |    chunk  2    | |
+	||    [0,N)       | |    [N,2N)      | |    [2N,3N)     | |
+	|+----------------+ +----------------+ +----------------+ |
+	+------^--------------------------------------------------+
+	       |
+   chunk B / C | offset B % C ( where C is the chunk size )
+	       |
+	 +-----^---- raw object O ----+------+
+	 |     B     [0,X)            | pad  |
+	 +----------------------------+------+
+
+    The object size is paded so that each chunks are of the same size.
+    In the example above, if the actual object size was X, then it
+    will be padded to 2N >= X assuming there are two data chunks (0
+    and 1) and one coding chunk (2).
+
+    For chunks of size C, byte B of the object is found in chunk number
+    B / C at offset B % C.
+
+    If an object is too large to be encoded in memory, the caller
+    should divide it in smaller units named **stripes**.
+
+	+---------------------- object O -------------------------+
+	|+----------------+ +----------------+ +----------------+ |
+ stripe ||    chunk  0    | |    chunk  1    | |    chunk  2    | |
+   0    ||    [0,N)       | |    [N,2N)      | |    [2N,3N)     | |
+	|+----------------+ +----------------+ +----------------+ |
+	|+----------------+ +----------------+ +----------------+ |
+ stripe ||    chunk  0    | |    chunk  1    | |    chunk  2    | |
+   1    ||    [X,M)       | |   [X+M,X+2M)   | |   [X+2M,X+3M)  | |
+	||                | |                | |                | |
+	|+----------------+ +----------------+ +----------------+ |
+	|                         ...                             |
+	+---------------------------------------------------------+
+
+    The interface does not concern itself with stripes nor does it
+    impose constraints on the size of each stripe. Variable names in
+    the interface always use **object** and never use **stripe**. 
+
+    Assuming the interface implementer provides three data chunks ( K
+    = 3 ) and two coding chunks ( M = 2 ), a buffer could be encoded as
+    follows:
+    
+    ~~~~~~~~~~~~~~~~{.c}
+    set<int> want_to_encode(0, 1, 2, // data chunks
+                            3, 4     // coding chunks
+                           );
+    bufferlist in = "ABCDEF";
+    map<int, bufferlist> encoded
+    encode(want_to_encode, in, &encoded);
+    encoded[0] == "AB" // data chunk 0
+    encoded[1] == "CD" // data chunk 1
+    encoded[2] == "EF" // data chunk 2
+    encoded[3]         // coding chunk 0
+    encoded[4]         // coding chunk 1
+    ~~~~~~~~~~~~~~~~
+
+    The **minimum_to_decode_with_cost** method can be used to minimize
+    the cost of fetching the chunks necessary to retrieve a given
+    content. For instance, if encoded[2] (contained **EF**) is missing
+    and accessing encoded[3] (the first coding chunk) is more
+    expensive than accessing encoded[4] (the second coding chunk),
+    **minimum_to_decode_with_cost** is expected to chose the first
+    coding chunk.
+
+    ~~~~~~~~~~~~~~~~{.c}
+    set<int> want_to_read(2); // want the chunk containing "EF"
+    map<int,int> available(
+          0 => 1,  // data chunk 0 : available and costs 1
+          1 => 1,  // data chunk 1 : available and costs 1
+                   // data chunk 2 : missing
+          3 => 9,  // coding chunk 1 : available and costs 9
+          4 => 1,  // coding chunk 2 : available and costs 1
+    );
+    set<int> minimum;
+    minimum_to_decode_with_cost(want_to_read,
+                                available,
+                                &minimum);
+    minimum == set<int>(0, 1, 4); // NOT set<int>(0, 1, 3);
+    ~~~~~~~~~~~~~~~~
+    
+    It sets **minimum** with three chunks to reconstruct the desired
+    data chunk and will pick the second coding chunk ( 4 ) because it
+    is less expensive ( 1 < 9 ) to retrieve than the first coding
+    chunk ( 3 ). The caller is responsible for retrieving the chunks
+    and call **decode** to reconstruct the second data chunk.
+    
+    ~~~~~~~~~~~~~~~~{.c}
+    map<int,bufferlist> chunks;
+    for i in minimum.keys():
+      chunks[i] = fetch_chunk(i); // get chunk from storage
+    map<int, bufferlist> decoded;
+    decode(want_to_read, chunks, &decoded);
+    decoded[2] == "EF"
+    ~~~~~~~~~~~~~~~~
+
+    The semantic of the cost value is defined by the caller and must
+    be known to the implementer. For instance, it may be more
+    expensive to retrieve two chunks with cost 1 + 9 = 10 than two
+    chunks with cost 6 + 6 = 12. 
+ */ 
+
+#include <map>
+#include <set>
+#include <vector>
+#include <ostream>
+#include <memory>
+#include <string>
+#include "include/buffer_fwd.h"
+
+class CrushWrapper;
+
+namespace ceph {
+
+  typedef std::map<std::string,std::string> ErasureCodeProfile;
+
+  inline std::ostream& operator<<(std::ostream& out, const ErasureCodeProfile& profile) {
+    out << "{";
+    for (ErasureCodeProfile::const_iterator it = profile.begin();
+	 it != profile.end();
+	 ++it) {
+      if (it != profile.begin()) out << ",";
+      out << it->first << "=" << it->second;
+    }
+    out << "}";
+    return out;
+  }
+
+
+  class ErasureCodeInterface {
+  public:
+    virtual ~ErasureCodeInterface() {}
+
+    /**
+     * Initialize the instance according to the content of
+     * **profile**. The **ss** stream is set with debug messages or
+     * error messages, the content of which depend on the
+     * implementation.
+     *
+     * Return 0 on success or a negative errno on error. When
+     * returning on error, the implementation is expected to
+     * provide a human readable explanation in **ss**.
+     *
+     * @param [in] profile a key/value map
+     * @param [out] ss contains informative messages when an error occurs
+     * @return 0 on success or a negative errno on error.
+     */
+    virtual int init(ErasureCodeProfile &profile, std::ostream *ss) = 0;
+
+    /**
+     * Return the profile that was used to initialize the instance
+     * with the **init** method.
+     *
+     * @return the profile in use by the instance
+     */
+    virtual const ErasureCodeProfile &get_profile() const = 0;
+
+    /**
+     * Create a new rule in **crush** under the name **name**,
+     * unless it already exists.
+     *
+     * Return the rule number that was created on success. If a
+     * rule **name** already exists, return -EEXISTS, otherwise
+     * return a negative value indicating an error with a semantic
+     * defined by the implementation.
+     *
+     * @param [in] name of the rule to create
+     * @param [in] crush crushmap in which the rule is created
+     * @param [out] ss contains informative messages when an error occurs
+     * @return a rule on success or a negative errno on error.
+     */
+    virtual int create_rule(const std::string &name,
+			    CrushWrapper &crush,
+			    std::ostream *ss) const = 0;
+
+    /**
+     * Return the number of chunks created by a call to the **encode**
+     * method.
+     *
+     * In the simplest case it can be K + M, i.e. the number
+     * of data chunks (K) plus the number of parity chunks
+     * (M). However, if the implementation provides local parity there
+     * could be an additional overhead.
+     *
+     * @return the number of chunks created by encode()
+     */
+    virtual unsigned int get_chunk_count() const = 0;
+
+    /**
+     * Return the number of data chunks created by a call to the
+     * **encode** method. The data chunks contain the buffer provided
+     * to **encode**, verbatim, with padding at the end of the last
+     * chunk.
+     *
+     * @return the number of data chunks created by encode()
+     */
+    virtual unsigned int get_data_chunk_count() const = 0;
+
+    /**
+     * Return the number of coding chunks created by a call to the
+     * **encode** method. The coding chunks are used to recover from
+     * the loss of one or more chunks. If there is one coding chunk,
+     * it is possible to recover from the loss of exactly one
+     * chunk. If there are two coding chunks, it is possible to
+     * recover from the loss of at most two chunks, etc.
+     *
+     * @return the number of coding chunks created by encode()
+     */
+    virtual unsigned int get_coding_chunk_count() const = 0;
+
+    /**
+     * Return the number of sub chunks chunks created by a call to the
+     * **encode** method. Each chunk can be viewed as union of sub-chunks
+     * For the case of array codes, the sub-chunk count > 1, where as the
+     * scalar codes have sub-chunk count = 1.
+     *
+     * @return the number of sub-chunks per chunk created by encode()
+     */
+    virtual int get_sub_chunk_count() = 0;
+
+    /**
+     * Return the size (in bytes) of a single chunk created by a call
+     * to the **decode** method. The returned size multiplied by
+     * **get_chunk_count()** is greater or equal to **object_size**.
+     *
+     * If the object size is properly aligned, the chunk size is
+     * **object_size / get_chunk_count()**. However, if
+     * **object_size** is not a multiple of **get_chunk_count** or if
+     * the implementation imposes additional alignment constraints,
+     * the chunk size may be larger.
+     *
+     * The byte found at offset **B** of the original object is mapped
+     * to chunk **B / get_chunk_size()** at offset **B % get_chunk_size()**.
+     *
+     * @param [in] object_size the number of bytes of the object to **encode()**
+     * @return the size (in bytes) of a single chunk created by **encode()**
+     */
+    virtual unsigned int get_chunk_size(unsigned int object_size) const = 0;
+
+    /**
+     * Compute the smallest subset of **available** chunks that needs
+     * to be retrieved in order to successfully decode
+     * **want_to_read** chunks.
+     *
+     * It is strictly equivalent to calling
+     * **minimum_to_decode_with_cost** where each **available** chunk
+     * has the same cost.
+     *
+     * @see minimum_to_decode_with_cost 
+     *
+     * @param [in] want_to_read chunk indexes to be decoded
+     * @param [in] available chunk indexes containing valid data
+     * @param [out] minimum chunk indexes and corresponding 
+     *              subchunk index offsets, count.
+     * @return **0** on success or a negative errno on error.
+     */
+    virtual int minimum_to_decode(const std::set<int> &want_to_read,
+                                  const std::set<int> &available,
+                                  std::map<int, std::vector<std::pair<int, int>>> 
+                                  *minimum) = 0;
+
+    /**
+     * Compute the smallest subset of **available** chunks that needs
+     * to be retrieved in order to successfully decode
+     * **want_to_read** chunks. If there are more than one possible
+     * subset, select the subset that minimizes the overall retrieval
+     * cost.
+     *
+     * The **available** parameter maps chunk indexes to their
+     * retrieval cost. The higher the cost value, the more costly it
+     * is to retrieve the chunk content. 
+     *
+     * Returns -EIO if there are not enough chunk indexes in
+     * **available** to decode **want_to_read**.
+     *
+     * Returns 0 on success.
+     *
+     * The **minimum** argument must be a pointer to an empty set.
+     *
+     * @param [in] want_to_read chunk indexes to be decoded
+     * @param [in] available map chunk indexes containing valid data 
+     *             to their retrieval cost
+     * @param [out] minimum chunk indexes to retrieve 
+     * @return **0** on success or a negative errno on error.
+     */
+    virtual int minimum_to_decode_with_cost(const std::set<int> &want_to_read,
+                                            const std::map<int, int> &available,
+                                            std::set<int> *minimum) = 0;
+
+    /**
+     * Encode the content of **in** and store the result in
+     * **encoded**. All buffers pointed to by **encoded** have the
+     * same size. The **encoded** map contains at least all chunk
+     * indexes found in the **want_to_encode** set.
+     *
+     * The **encoded** map is expected to be a pointer to an empty
+     * map.
+     *
+     * Assuming the **in** parameter is **length** bytes long, 
+     * the concatenation of the first **length** bytes of the
+     * **encoded** buffers is equal to the content of the **in**
+     * parameter.
+     *
+     * The **encoded** map may contain more chunks than required by
+     * **want_to_encode** and the caller is expected to permanently
+     * store all of them, not just the chunks listed in
+     * **want_to_encode**.
+     *
+     * The **encoded** map may contain pointers to data stored in
+     * the **in** parameter. If the caller modifies the content of
+     * **in** after calling the encode method, it may have a side
+     * effect on the content of **encoded**. 
+     *
+     * The **encoded** map may contain pointers to buffers allocated
+     * by the encode method. They will be freed when **encoded** is
+     * freed. The allocation method is not specified.
+     *
+     * Returns 0 on success.
+     *
+     * @param [in] want_to_encode chunk indexes to be encoded
+     * @param [in] in data to be encoded
+     * @param [out] encoded map chunk indexes to chunk data
+     * @return **0** on success or a negative errno on error.
+     */
+    virtual int encode(const std::set<int> &want_to_encode,
+                       const bufferlist &in,
+                       std::map<int, bufferlist> *encoded) = 0;
+
+
+    virtual int encode_chunks(const std::set<int> &want_to_encode,
+                              std::map<int, bufferlist> *encoded) = 0;
+
+    /**
+     * Decode the **chunks** and store at least **want_to_read**
+     * chunks in **decoded**.
+     *
+     * The **decoded** map must be a pointer to an empty map.
+     *
+     * There must be enough **chunks** ( as returned by
+     * **minimum_to_decode** or **minimum_to_decode_with_cost** ) to
+     * perform a successful decoding of all chunks listed in
+     * **want_to_read**.
+     *
+     * All buffers pointed by **in** must have the same size.
+     *
+     * On success, the **decoded** map may contain more chunks than
+     * required by **want_to_read** and they can safely be used by the
+     * caller.
+     *
+     * If a chunk is listed in **want_to_read** and there is a
+     * corresponding **bufferlist** in **chunks**, it will be
+     * referenced in **decoded**. If not it will be reconstructed from
+     * the existing chunks. 
+     *
+     * Because **decoded** may contain pointers to data found in
+     * **chunks**, modifying the content of **chunks** after calling
+     * decode may have a side effect on the content of **decoded**.
+     *
+     * Returns 0 on success.
+     *
+     * @param [in] want_to_read chunk indexes to be decoded
+     * @param [in] chunks map chunk indexes to chunk data
+     * @param [out] decoded map chunk indexes to chunk data
+     * @param [in] chunk_size chunk size
+     * @return **0** on success or a negative errno on error.
+     */
+    virtual int decode(const std::set<int> &want_to_read,
+                       const std::map<int, bufferlist> &chunks,
+                       std::map<int, bufferlist> *decoded, int chunk_size) = 0;
+
+    virtual int decode_chunks(const std::set<int> &want_to_read,
+                              const std::map<int, bufferlist> &chunks,
+                              std::map<int, bufferlist> *decoded) = 0;
+
+    /**
+     * Return the ordered list of chunks or an empty vector
+     * if no remapping is necessary.
+     *
+     * By default encoding an object with K=2,M=1 will create three
+     * chunks, the first two are data and the last one coding. For
+     * a 10MB object, it would be:
+     *
+     *   chunk 0 for the first 5MB
+     *   chunk 1 for the last 5MB
+     *   chunk 2 for the 5MB coding chunk
+     *
+     * The plugin may, however, decide to remap them in a different
+     * order, such as:
+     *
+     *   chunk 0 for the last 5MB
+     *   chunk 1 for the 5MB coding chunk
+     *   chunk 2 for the first 5MB
+     *
+     * The vector<int> remaps the chunks so that the first chunks are
+     * data, in sequential order, and the last chunks contain parity
+     * in the same order as they were output by the encoding function.
+     *
+     * In the example above the mapping would be:
+     *
+     *   [ 1, 2, 0 ]
+     *
+     * The returned vector<int> only contains information for chunks
+     * that need remapping. If no remapping is necessary, the
+     * vector<int> is empty.
+     *
+     * @return vector<int> list of indices of chunks to be remapped
+     */
+    virtual const std::vector<int> &get_chunk_mapping() const = 0;
+
+    /**
+     * Decode the first **get_data_chunk_count()** **chunks** and
+     * concatenate them into **decoded**.
+     *
+     * Returns 0 on success.
+     *
+     * @param [in] chunks map chunk indexes to chunk data
+     * @param [out] decoded concatenante of the data chunks
+     * @return **0** on success or a negative errno on error.
+     */
+    virtual int decode_concat(const std::map<int, bufferlist> &chunks,
+			      bufferlist *decoded) = 0;
+  };
+
+  typedef std::shared_ptr<ErasureCodeInterface> ErasureCodeInterfaceRef;
+
+}
+
+#endif