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