ceph/src/erasure-code/ErasureCode.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph distributed storage system
   5  *
   6  * Copyright (C) 2014 Cloudwatt <libre.licensing@cloudwatt.com>
   7  * Copyright (C) 2014 Red Hat <contact@redhat.com>
   8  *
   9  * Author: Loic Dachary <loic@dachary.org>
  10  *
  11  *  This library is free software; you can redistribute it and/or
  12  *  modify it under the terms of the GNU Lesser General Public
  13  *  License as published by the Free Software Foundation; either
  14  *  version 2.1 of the License, or (at your option) any later version.
  15  *
  16  */
  17
  18 #include <errno.h>
  19 #include <algorithm>
  20
  21 #include "ErasureCode.h"
  22
  23 #include "common/strtol.h"
  24 #include "include/buffer.h"
  25
  26 using namespace std;
  27
  28 const unsigned ErasureCode::SIMD_ALIGN = 32;
  29
  30 int ErasureCode::sanity_check_k(int k, ostream *ss)
  31 {
  32   if (k < 2) {
  33     *ss << "k=" << k << " must be >= 2" << std::endl;
  34     return -EINVAL;
  35   } else {
  36     return 0;
  37   }
  38 }
  39
  40 int ErasureCode::chunk_index(unsigned int i) const
  41 {
  42   return chunk_mapping.size() > i ? chunk_mapping[i] : i;
  43 }
  44
  45 int ErasureCode::minimum_to_decode(const set<int> &want_to_read,
  46                                    const set<int> &available_chunks,
  47                                    set<int> *minimum)
  48 {
  49   if (includes(available_chunks.begin(), available_chunks.end(),
  50                want_to_read.begin(), want_to_read.end())) {
  51     *minimum = want_to_read;
  52   } else {
  53     unsigned int k = get_data_chunk_count();
  54     if (available_chunks.size() < (unsigned)k)
  55       return -EIO;
  56     set<int>::iterator i;
  57     unsigned j;
  58     for (i = available_chunks.begin(), j = 0; j < (unsigned)k; ++i, j++)
  59       minimum->insert(*i);
  60   }
  61   return 0;
  62 }
  63
  64 int ErasureCode::minimum_to_decode_with_cost(const set<int> &want_to_read,
  65                                              const map<int, int> &available,
  66                                              set<int> *minimum)
  67 {
  68   set <int> available_chunks;
  69   for (map<int, int>::const_iterator i = available.begin();
  70        i != available.end();
  71        ++i)
  72     available_chunks.insert(i->first);
  73   return minimum_to_decode(want_to_read, available_chunks, minimum);
  74 }
  75
  76 int ErasureCode::encode_prepare(const bufferlist &raw,
  77                                 map<int, bufferlist> &encoded) const
  78 {
  79   unsigned int k = get_data_chunk_count();
  80   unsigned int m = get_chunk_count() - k;
  81   unsigned blocksize = get_chunk_size(raw.length());
  82   unsigned padded_chunks = k - raw.length() / blocksize;
  83   bufferlist prepared = raw;
  84
  85   for (unsigned int i = 0; i < k - padded_chunks; i++) {
  86     bufferlist &chunk = encoded[chunk_index(i)];
  87     chunk.substr_of(prepared, i * blocksize, blocksize);
  88     chunk.rebuild_aligned_size_and_memory(blocksize, SIMD_ALIGN);
  89     assert(chunk.is_contiguous());
  90   }
  91   if (padded_chunks) {
  92     unsigned remainder = raw.length() - (k - padded_chunks) * blocksize;
  93     bufferptr buf(buffer::create_aligned(blocksize, SIMD_ALIGN));
  94
  95     raw.copy((k - padded_chunks) * blocksize, remainder, buf.c_str());
  96     buf.zero(remainder, blocksize - remainder);
  97     encoded[chunk_index(k-padded_chunks)].push_back(std::move(buf));
  98
  99     for (unsigned int i = k - padded_chunks + 1; i < k; i++) {
 100       bufferptr buf(buffer::create_aligned(blocksize, SIMD_ALIGN));
 101       buf.zero();
 102       encoded[chunk_index(i)].push_back(std::move(buf));
 103     }
 104   }
 105   for (unsigned int i = k; i < k + m; i++) {
 106     bufferlist &chunk = encoded[chunk_index(i)];
 107     chunk.push_back(buffer::create_aligned(blocksize, SIMD_ALIGN));
 108   }
 109
 110   return 0;
 111 }
 112
 113 int ErasureCode::encode(const set<int> &want_to_encode,
 114                         const bufferlist &in,
 115                         map<int, bufferlist> *encoded)
 116 {
 117   unsigned int k = get_data_chunk_count();
 118   unsigned int m = get_chunk_count() - k;
 119   bufferlist out;
 120   int err = encode_prepare(in, *encoded);
 121   if (err)
 122     return err;
 123   encode_chunks(want_to_encode, encoded);
 124   for (unsigned int i = 0; i < k + m; i++) {
 125     if (want_to_encode.count(i) == 0)
 126       encoded->erase(i);
 127   }
 128   return 0;
 129 }
 130
 131 int ErasureCode::encode_chunks(const set<int> &want_to_encode,
 132                                map<int, bufferlist> *encoded)
 133 {
 134   assert("ErasureCode::encode_chunks not implemented" == 0);
 135 }
 136
 137 int ErasureCode::decode(const set<int> &want_to_read,
 138                         const map<int, bufferlist> &chunks,
 139                         map<int, bufferlist> *decoded)
 140 {
 141   vector<int> have;
 142   have.reserve(chunks.size());
 143   for (map<int, bufferlist>::const_iterator i = chunks.begin();
 144        i != chunks.end();
 145        ++i) {
 146     have.push_back(i->first);
 147   }
 148   if (includes(
 149         have.begin(), have.end(), want_to_read.begin(), want_to_read.end())) {
 150     for (set<int>::iterator i = want_to_read.begin();
 151          i != want_to_read.end();
 152          ++i) {
 153       (*decoded)[*i] = chunks.find(*i)->second;
 154     }
 155     return 0;
 156   }
 157   unsigned int k = get_data_chunk_count();
 158   unsigned int m = get_chunk_count() - k;
 159   unsigned blocksize = (*chunks.begin()).second.length();
 160   for (unsigned int i =  0; i < k + m; i++) {
 161     if (chunks.find(i) == chunks.end()) {
 162       bufferptr ptr(buffer::create_aligned(blocksize, SIMD_ALIGN));
 163       (*decoded)[i].push_front(ptr);
 164     } else {
 165       (*decoded)[i] = chunks.find(i)->second;
 166       (*decoded)[i].rebuild_aligned(SIMD_ALIGN);
 167     }
 168   }
 169   return decode_chunks(want_to_read, chunks, decoded);
 170 }
 171
 172 int ErasureCode::decode_chunks(const set<int> &want_to_read,
 173                                const map<int, bufferlist> &chunks,
 174                                map<int, bufferlist> *decoded)
 175 {
 176   assert("ErasureCode::decode_chunks not implemented" == 0);
 177 }
 178
 179 int ErasureCode::parse(const ErasureCodeProfile &profile,
 180                        ostream *ss)
 181 {
 182   return to_mapping(profile, ss);
 183 }
 184
 185 const vector<int> &ErasureCode::get_chunk_mapping() const {
 186   return chunk_mapping;
 187 }
 188
 189 int ErasureCode::to_mapping(const ErasureCodeProfile &profile,
 190                             ostream *ss)
 191 {
 192   if (profile.find("mapping") != profile.end()) {
 193     std::string mapping = profile.find("mapping")->second;
 194     int position = 0;
 195     vector<int> coding_chunk_mapping;
 196     for(std::string::iterator it = mapping.begin(); it != mapping.end(); ++it) {
 197       if (*it == 'D')
 198         chunk_mapping.push_back(position);
 199       else
 200         coding_chunk_mapping.push_back(position);
 201       position++;
 202     }
 203     chunk_mapping.insert(chunk_mapping.end(),
 204                          coding_chunk_mapping.begin(),
 205                          coding_chunk_mapping.end());
 206   }
 207   return 0;
 208 }
 209
 210 int ErasureCode::to_int(const std::string &name,
 211                         ErasureCodeProfile &profile,
 212                         int *value,
 213                         const std::string &default_value,
 214                         ostream *ss)
 215 {
 216   if (profile.find(name) == profile.end() ||
 217       profile.find(name)->second.size() == 0)
 218     profile[name] = default_value;
 219   std::string p = profile.find(name)->second;
 220   std::string err;
 221   int r = strict_strtol(p.c_str(), 10, &err);
 222   if (!err.empty()) {
 223     *ss << "could not convert " << name << "=" << p
 224         << " to int because " << err
 225         << ", set to default " << default_value << std::endl;
 226     *value = strict_strtol(default_value.c_str(), 10, &err);
 227     return -EINVAL;
 228   }
 229   *value = r;
 230   return 0;
 231 }
 232
 233 int ErasureCode::to_bool(const std::string &name,
 234                          ErasureCodeProfile &profile,
 235                          bool *value,
 236                          const std::string &default_value,
 237                          ostream *ss)
 238 {
 239   if (profile.find(name) == profile.end() ||
 240       profile.find(name)->second.size() == 0)
 241     profile[name] = default_value;
 242   const std::string p = profile.find(name)->second;
 243   *value = (p == "yes") || (p == "true");
 244   return 0;
 245 }
 246
 247 int ErasureCode::to_string(const std::string &name,
 248                            ErasureCodeProfile &profile,
 249                            std::string *value,
 250                            const std::string &default_value,
 251                            ostream *ss)
 252 {
 253   if (profile.find(name) == profile.end() ||
 254       profile.find(name)->second.size() == 0)
 255     profile[name] = default_value;
 256   *value = profile[name];
 257   return 0;
 258 }
 259
 260 int ErasureCode::decode_concat(const map<int, bufferlist> &chunks,
 261                                bufferlist *decoded)
 262 {
 263   set<int> want_to_read;
 264
 265   for (unsigned int i = 0; i < get_data_chunk_count(); i++) {
 266     want_to_read.insert(chunk_index(i));
 267   }
 268   map<int, bufferlist> decoded_map;
 269   int r = decode(want_to_read, chunks, &decoded_map);
 270   if (r == 0) {
 271     for (unsigned int i = 0; i < get_data_chunk_count(); i++) {
 272       decoded->claim_append(decoded_map[chunk_index(i)]);
 273     }
 274   }
 275   return r;
 276 }