ceph/src/test/erasure-code/ErasureCodeExample.h

   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) 2013 Cloudwatt <libre.licensing@cloudwatt.com>
   7  *
   8  * Author: Loic Dachary <loic@dachary.org>
   9  *
  10  *  This library is free software; you can redistribute it and/or
  11  *  modify it under the terms of the GNU Lesser General Public
  12  *  License as published by the Free Software Foundation; either
  13  *  version 2.1 of the License, or (at your option) any later version.
  14  *
  15  */
  16
  17 #ifndef CEPH_ERASURE_CODE_EXAMPLE_H
  18 #define CEPH_ERASURE_CODE_EXAMPLE_H
  19
  20 #include <unistd.h>
  21 #include <errno.h>
  22 #include <algorithm>
  23 #include <sstream>
  24
  25 #include "crush/CrushWrapper.h"
  26 #include "osd/osd_types.h"
  27 #include "erasure-code/ErasureCode.h"
  28
  29 #define FIRST_DATA_CHUNK 0
  30 #define SECOND_DATA_CHUNK 1
  31 #define DATA_CHUNKS 2u
  32
  33 #define CODING_CHUNK 2
  34 #define CODING_CHUNKS 1u
  35
  36 #define MINIMUM_TO_RECOVER 2u
  37
  38 class ErasureCodeExample final : public ErasureCode {
  39 public:
  40   ~ErasureCodeExample() override {}
  41
  42   int create_rule(const string &name,
  43                              CrushWrapper &crush,
  44                              ostream *ss) const override {
  45     return crush.add_simple_rule(name, "default", "host", "",
  46                                  "indep", pg_pool_t::TYPE_ERASURE, ss);
  47   }
  48
  49   int minimum_to_decode_with_cost(const set<int> &want_to_read,
  50                                           const map<int, int> &available,
  51                                           set<int> *minimum) override {
  52     //
  53     // If one chunk is more expensive to fetch than the others,
  54     // recover it instead. For instance, if the cost reflects the
  55     // time it takes for a chunk to be retrieved from a remote
  56     // OSD and if CPU is cheap, it could make sense to recover
  57     // instead of fetching the chunk.
  58     //
  59     map<int, int> c2c(available);
  60     if (c2c.size() > DATA_CHUNKS) {
  61       if (c2c[FIRST_DATA_CHUNK] > c2c[SECOND_DATA_CHUNK] &&
  62           c2c[FIRST_DATA_CHUNK] > c2c[CODING_CHUNK])
  63         c2c.erase(FIRST_DATA_CHUNK);
  64       else if(c2c[SECOND_DATA_CHUNK] > c2c[FIRST_DATA_CHUNK] &&
  65               c2c[SECOND_DATA_CHUNK] > c2c[CODING_CHUNK])
  66         c2c.erase(SECOND_DATA_CHUNK);
  67       else if(c2c[CODING_CHUNK] > c2c[FIRST_DATA_CHUNK] &&
  68               c2c[CODING_CHUNK] > c2c[SECOND_DATA_CHUNK])
  69         c2c.erase(CODING_CHUNK);
  70     }
  71     set <int> available_chunks;
  72     for (map<int, int>::const_iterator i = c2c.begin();
  73          i != c2c.end();
  74          ++i)
  75       available_chunks.insert(i->first);
  76     return _minimum_to_decode(want_to_read, available_chunks, minimum);
  77   }
  78
  79   unsigned int get_chunk_count() const override {
  80     return DATA_CHUNKS + CODING_CHUNKS;
  81   }
  82
  83   unsigned int get_data_chunk_count() const override {
  84     return DATA_CHUNKS;
  85   }
  86
  87   unsigned int get_chunk_size(unsigned int object_size) const override {
  88     return ( object_size / DATA_CHUNKS ) + 1;
  89   }
  90
  91   int encode(const set<int> &want_to_encode,
  92                      const bufferlist &in,
  93                      map<int, bufferlist> *encoded) override {
  94     //
  95     // make sure all data chunks have the same length, allocating
  96     // padding if necessary.
  97     //
  98     unsigned int chunk_length = get_chunk_size(in.length());
  99     bufferlist out(in);
 100     unsigned int width = get_chunk_count() * get_chunk_size(in.length());
 101     bufferptr pad(width - in.length());
 102     pad.zero(0, get_data_chunk_count());
 103     out.push_back(pad);
 104     //
 105     // compute the coding chunk with first chunk ^ second chunk
 106     //
 107     char *p = out.c_str();
 108     for (unsigned i = 0; i < chunk_length; i++)
 109       p[i + CODING_CHUNK * chunk_length] =
 110         p[i + FIRST_DATA_CHUNK * chunk_length] ^
 111         p[i + SECOND_DATA_CHUNK * chunk_length];
 112     //
 113     // populate the bufferlist with bufferptr pointing
 114     // to chunk boundaries
 115     //
 116     const bufferptr &ptr = out.front();
 117     for (set<int>::iterator j = want_to_encode.begin();
 118          j != want_to_encode.end();
 119          ++j) {
 120       bufferlist tmp;
 121       bufferptr chunk(ptr, (*j) * chunk_length, chunk_length);
 122       tmp.push_back(chunk);
 123       tmp.claim_append((*encoded)[*j]);
 124       (*encoded)[*j].swap(tmp);
 125     }
 126     return 0;
 127   }
 128
 129   int encode_chunks(const set<int> &want_to_encode,
 130                             map<int, bufferlist> *encoded) override {
 131     ceph_abort();
 132     return 0;
 133   }
 134
 135   int _decode(const set<int> &want_to_read,
 136               const map<int, bufferlist> &chunks,
 137               map<int, bufferlist> *decoded) {
 138     //
 139     // All chunks have the same size
 140     //
 141     unsigned chunk_length = (*chunks.begin()).second.length();
 142     for (set<int>::iterator i = want_to_read.begin();
 143          i != want_to_read.end();
 144          ++i) {
 145       if (chunks.find(*i) != chunks.end()) {
 146         //
 147         // If the chunk is available, just copy the bufferptr pointer
 148         // to the decoded argument.
 149         //
 150         (*decoded)[*i] = chunks.find(*i)->second;
 151       } else if(chunks.size() != 2) {
 152         //
 153         // If a chunk is missing and there are not enough chunks
 154         // to recover, abort.
 155         //
 156         return -ERANGE;
 157       } else {
 158         //
 159         // No matter what the missing chunk is, XOR of the other
 160         // two recovers it.
 161         //
 162         map<int, bufferlist>::const_iterator k = chunks.begin();
 163         const char *a = k->second.front().c_str();
 164         ++k;
 165         const char *b = k->second.front().c_str();
 166         bufferptr chunk(chunk_length);
 167         char *c = chunk.c_str();
 168         for (unsigned j = 0; j < chunk_length; j++) {
 169           c[j] = a[j] ^ b[j];
 170         }
 171
 172         bufferlist tmp;
 173         tmp.append(chunk);
 174         tmp.claim_append((*decoded)[*i]);
 175         (*decoded)[*i].swap(tmp);
 176       }
 177     }
 178     return 0;
 179   }
 180
 181   int decode_chunks(const set<int> &want_to_read,
 182                             const map<int, bufferlist> &chunks,
 183                             map<int, bufferlist> *decoded) override {
 184     ceph_abort();
 185     return 0;
 186   }
 187
 188   const vector<int> &get_chunk_mapping() const override {
 189     static vector<int> mapping;
 190     return mapping;
 191   }
 192
 193 };
 194
 195 #endif