[ceph.git] / ceph / src / erasure-code / ErasureCode.cc

// -*- 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) 2014 Cloudwatt <libre.licensing@cloudwatt.com>
 * Copyright (C) 2014 Red Hat <contact@redhat.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.
 * 
 */

#include <algorithm>
#include <cerrno>

#include "ErasureCode.h"

#include "common/strtol.h"
#include "include/buffer.h"
#include "crush/CrushWrapper.h"
#include "osd/osd_types.h"

#define DEFAULT_RULE_ROOT "default"
#define DEFAULT_RULE_FAILURE_DOMAIN "host"

using std::make_pair;
using std::map;
using std::ostream;
using std::pair;
using std::set;
using std::string;
using std::vector;

using ceph::bufferlist;

namespace ceph {
const unsigned ErasureCode::SIMD_ALIGN = 32;

int ErasureCode::init(
  ErasureCodeProfile &profile,
  std::ostream *ss)
{
  int err = 0;
  err |= to_string("crush-root", profile,
		   &rule_root,
		   DEFAULT_RULE_ROOT, ss);
  err |= to_string("crush-failure-domain", profile,
		   &rule_failure_domain,
		   DEFAULT_RULE_FAILURE_DOMAIN, ss);
  err |= to_string("crush-device-class", profile,
		   &rule_device_class,
		   "", ss);
  if (err)
    return err;
  _profile = profile;
  return 0;
}

int ErasureCode::create_rule(
  const std::string &name,
  CrushWrapper &crush,
  std::ostream *ss) const
{
  int ruleid = crush.add_simple_rule(
    name,
    rule_root,
    rule_failure_domain,
    rule_device_class,
    "indep",
    pg_pool_t::TYPE_ERASURE,
    ss);

  if (ruleid < 0)
    return ruleid;

  return ruleid;
}

int ErasureCode::sanity_check_k_m(int k, int m, ostream *ss)
{
  if (k < 2) {
    *ss << "k=" << k << " must be >= 2" << std::endl;
    return -EINVAL;
  }
  if (m < 1) {
    *ss << "m=" << m << " must be >= 1" << std::endl;
    return -EINVAL;
  }
  return 0;
}

int ErasureCode::chunk_index(unsigned int i) const
{
  return chunk_mapping.size() > i ? chunk_mapping[i] : i;
}

int ErasureCode::_minimum_to_decode(const set<int> &want_to_read,
                                   const set<int> &available_chunks,
                                   set<int> *minimum)
{
  if (includes(available_chunks.begin(), available_chunks.end(),
	       want_to_read.begin(), want_to_read.end())) {
    *minimum = want_to_read;
  } else {
    unsigned int k = get_data_chunk_count();
    if (available_chunks.size() < (unsigned)k)
      return -EIO;
    set<int>::iterator i;
    unsigned j;
    for (i = available_chunks.begin(), j = 0; j < (unsigned)k; ++i, j++)
      minimum->insert(*i);
  }
  return 0;
}

int ErasureCode::minimum_to_decode(const set<int> &want_to_read,
                                   const set<int> &available_chunks,
                                   map<int, vector<pair<int, int>>> *minimum)
{
  set<int> minimum_shard_ids;
  int r = _minimum_to_decode(want_to_read, available_chunks, &minimum_shard_ids);
  if (r != 0) {
    return r;
  }
  vector<pair<int, int>> default_subchunks;
  default_subchunks.push_back(make_pair(0, get_sub_chunk_count()));
  for (auto &&id : minimum_shard_ids) {
    minimum->insert(make_pair(id, default_subchunks));
  }
  return 0;
}

int ErasureCode::minimum_to_decode_with_cost(const set<int> &want_to_read,
                                             const map<int, int> &available,
                                             set<int> *minimum)
{
  set <int> available_chunks;
  for (map<int, int>::const_iterator i = available.begin();
       i != available.end();
       ++i)
    available_chunks.insert(i->first);
  return _minimum_to_decode(want_to_read, available_chunks, minimum);
}

int ErasureCode::encode_prepare(const bufferlist &raw,
                                map<int, bufferlist> &encoded) const
{
  unsigned int k = get_data_chunk_count();
  unsigned int m = get_chunk_count() - k;
  unsigned blocksize = get_chunk_size(raw.length());
  unsigned padded_chunks = k - raw.length() / blocksize;
  bufferlist prepared = raw;

  for (unsigned int i = 0; i < k - padded_chunks; i++) {
    bufferlist &chunk = encoded[chunk_index(i)];
    chunk.substr_of(prepared, i * blocksize, blocksize);
    chunk.rebuild_aligned_size_and_memory(blocksize, SIMD_ALIGN);
    ceph_assert(chunk.is_contiguous());
  }
  if (padded_chunks) {
    unsigned remainder = raw.length() - (k - padded_chunks) * blocksize;
    bufferptr buf(buffer::create_aligned(blocksize, SIMD_ALIGN));

    raw.begin((k - padded_chunks) * blocksize).copy(remainder, buf.c_str());
    buf.zero(remainder, blocksize - remainder);
    encoded[chunk_index(k-padded_chunks)].push_back(std::move(buf));

    for (unsigned int i = k - padded_chunks + 1; i < k; i++) {
      bufferptr buf(buffer::create_aligned(blocksize, SIMD_ALIGN));
      buf.zero();
      encoded[chunk_index(i)].push_back(std::move(buf));
    }
  }
  for (unsigned int i = k; i < k + m; i++) {
    bufferlist &chunk = encoded[chunk_index(i)];
    chunk.push_back(buffer::create_aligned(blocksize, SIMD_ALIGN));
  }

  return 0;
}

int ErasureCode::encode(const set<int> &want_to_encode,
                        const bufferlist &in,
                        map<int, bufferlist> *encoded)
{
  unsigned int k = get_data_chunk_count();
  unsigned int m = get_chunk_count() - k;
  bufferlist out;
  int err = encode_prepare(in, *encoded);
  if (err)
    return err;
  encode_chunks(want_to_encode, encoded);
  for (unsigned int i = 0; i < k + m; i++) {
    if (want_to_encode.count(i) == 0)
      encoded->erase(i);
  }
  return 0;
}

int ErasureCode::_decode(const set<int> &want_to_read,
			 const map<int, bufferlist> &chunks,
			 map<int, bufferlist> *decoded)
{
  vector<int> have;
  have.reserve(chunks.size());
  for (map<int, bufferlist>::const_iterator i = chunks.begin();
       i != chunks.end();
       ++i) {
    have.push_back(i->first);
  }
  if (includes(
	have.begin(), have.end(), want_to_read.begin(), want_to_read.end())) {
    for (set<int>::iterator i = want_to_read.begin();
	 i != want_to_read.end();
	 ++i) {
      (*decoded)[*i] = chunks.find(*i)->second;
    }
    return 0;
  }
  unsigned int k = get_data_chunk_count();
  unsigned int m = get_chunk_count() - k;
  unsigned blocksize = (*chunks.begin()).second.length();
  for (unsigned int i =  0; i < k + m; i++) {
    if (chunks.find(i) == chunks.end()) {
      bufferlist tmp;
      bufferptr ptr(buffer::create_aligned(blocksize, SIMD_ALIGN));
      tmp.push_back(ptr);
      tmp.claim_append((*decoded)[i]);
      (*decoded)[i].swap(tmp);
    } else {
      (*decoded)[i] = chunks.find(i)->second;
      (*decoded)[i].rebuild_aligned(SIMD_ALIGN);
    }
  }
  return decode_chunks(want_to_read, chunks, decoded);
}

int ErasureCode::decode(const set<int> &want_to_read,
                        const map<int, bufferlist> &chunks,
                        map<int, bufferlist> *decoded, int chunk_size)
{
  return _decode(want_to_read, chunks, decoded);
}

int ErasureCode::parse(const ErasureCodeProfile &profile,
		       ostream *ss)
{
  return to_mapping(profile, ss);
}

const vector<int> &ErasureCode::get_chunk_mapping() const {
  return chunk_mapping;
}

int ErasureCode::to_mapping(const ErasureCodeProfile &profile,
			    ostream *ss)
{
  if (profile.find("mapping") != profile.end()) {
    std::string mapping = profile.find("mapping")->second;
    int position = 0;
    vector<int> coding_chunk_mapping;
    for(std::string::iterator it = mapping.begin(); it != mapping.end(); ++it) {
      if (*it == 'D')
	chunk_mapping.push_back(position);
      else
	coding_chunk_mapping.push_back(position);
      position++;
    }
    chunk_mapping.insert(chunk_mapping.end(),
			 coding_chunk_mapping.begin(),
			 coding_chunk_mapping.end());
  }
  return 0;
}

int ErasureCode::to_int(const std::string &name,
			ErasureCodeProfile &profile,
			int *value,
			const std::string &default_value,
			ostream *ss)
{
  if (profile.find(name) == profile.end() ||
      profile.find(name)->second.size() == 0)
    profile[name] = default_value;
  std::string p = profile.find(name)->second;
  std::string err;
  int r = strict_strtol(p.c_str(), 10, &err);
  if (!err.empty()) {
    *ss << "could not convert " << name << "=" << p
	<< " to int because " << err
	<< ", set to default " << default_value << std::endl;
    *value = strict_strtol(default_value.c_str(), 10, &err);
    return -EINVAL;
  }
  *value = r;
  return 0;
}

int ErasureCode::to_bool(const std::string &name,
			 ErasureCodeProfile &profile,
			 bool *value,
			 const std::string &default_value,
			 ostream *ss)
{
  if (profile.find(name) == profile.end() ||
      profile.find(name)->second.size() == 0)
    profile[name] = default_value;
  const std::string p = profile.find(name)->second;
  *value = (p == "yes") || (p == "true");
  return 0;
}

int ErasureCode::to_string(const std::string &name,
			   ErasureCodeProfile &profile,
			   std::string *value,
			   const std::string &default_value,
			   ostream *ss)
{
  if (profile.find(name) == profile.end() ||
      profile.find(name)->second.size() == 0)
    profile[name] = default_value;
  *value = profile[name];
  return 0;
}

int ErasureCode::decode_concat(const map<int, bufferlist> &chunks,
			       bufferlist *decoded)
{
  set<int> want_to_read;

  for (unsigned int i = 0; i < get_data_chunk_count(); i++) {
    want_to_read.insert(chunk_index(i));
  }
  map<int, bufferlist> decoded_map;
  int r = _decode(want_to_read, chunks, &decoded_map);
  if (r == 0) {
    for (unsigned int i = 0; i < get_data_chunk_count(); i++) {
      decoded->claim_append(decoded_map[chunk_index(i)]);
    }
  }
  return r;
}
}
Commit	Line	Data
7c673cae FG	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
7c673cae	18	#include <algorithm>
9f95a23c	19	#include <cerrno>
7c673cae	20
7c673cae	21	#include "ErasureCode.h"
31f18b77 FG	22
31f18b77 FG	23	#include "common/strtol.h"
7c673cae	24	#include "include/buffer.h"
224ce89b WB	25	#include "crush/CrushWrapper.h"
224ce89b WB	26	#include "osd/osd_types.h"
7c673cae	27
224ce89b WB	28	#define DEFAULT_RULE_ROOT "default"
	29	#define DEFAULT_RULE_FAILURE_DOMAIN "host"
	30
9f95a23c TL	31	using std::make_pair;
	32	using std::map;
	33	using std::ostream;
	34	using std::pair;
	35	using std::set;
	36	using std::string;
	37	using std::vector;
	38
	39	using ceph::bufferlist;
	40
	41	namespace ceph {
11fdf7f2 TL	42	const unsigned ErasureCode::SIMD_ALIGN = 32;
11fdf7f2 TL	43
224ce89b WB	44	int ErasureCode::init(
	45	ErasureCodeProfile &profile,
	46	std::ostream *ss)
	47	{
	48	int err = 0;
	49	err \|= to_string("crush-root", profile,
	50	&rule_root,
	51	DEFAULT_RULE_ROOT, ss);
	52	err \|= to_string("crush-failure-domain", profile,
	53	&rule_failure_domain,
	54	DEFAULT_RULE_FAILURE_DOMAIN, ss);
	55	err \|= to_string("crush-device-class", profile,
	56	&rule_device_class,
	57	"", ss);
	58	if (err)
	59	return err;
	60	_profile = profile;
	61	return 0;
	62	}
	63
	64	int ErasureCode::create_rule(
	65	const std::string &name,
	66	CrushWrapper &crush,
	67	std::ostream *ss) const
	68	{
	69	int ruleid = crush.add_simple_rule(
	70	name,
	71	rule_root,
	72	rule_failure_domain,
	73	rule_device_class,
	74	"indep",
	75	pg_pool_t::TYPE_ERASURE,
	76	ss);
	77
	78	if (ruleid < 0)
	79	return ruleid;
	80
224ce89b WB	81	return ruleid;
	82	}
	83
11fdf7f2	84	int ErasureCode::sanity_check_k_m(int k, int m, ostream *ss)
7c673cae FG	85	{
	86	if (k < 2) {
	87	*ss << "k=" << k << " must be >= 2" << std::endl;
	88	return -EINVAL;
7c673cae	89	}
11fdf7f2 TL	90	if (m < 1) {
	91	*ss << "m=" << m << " must be >= 1" << std::endl;
	92	return -EINVAL;
	93	}
	94	return 0;
7c673cae FG	95	}
	96
	97	int ErasureCode::chunk_index(unsigned int i) const
	98	{
	99	return chunk_mapping.size() > i ? chunk_mapping[i] : i;
	100	}
	101
11fdf7f2	102	int ErasureCode::_minimum_to_decode(const set<int> &want_to_read,
7c673cae FG	103	const set<int> &available_chunks,
	104	set<int> *minimum)
	105	{
	106	if (includes(available_chunks.begin(), available_chunks.end(),
	107	want_to_read.begin(), want_to_read.end())) {
	108	*minimum = want_to_read;
	109	} else {
	110	unsigned int k = get_data_chunk_count();
	111	if (available_chunks.size() < (unsigned)k)
	112	return -EIO;
	113	set<int>::iterator i;
	114	unsigned j;
	115	for (i = available_chunks.begin(), j = 0; j < (unsigned)k; ++i, j++)
	116	minimum->insert(*i);
	117	}
	118	return 0;
	119	}
	120
11fdf7f2 TL	121	int ErasureCode::minimum_to_decode(const set<int> &want_to_read,
	122	const set<int> &available_chunks,
	123	map<int, vector<pair<int, int>>> *minimum)
	124	{
	125	set<int> minimum_shard_ids;
	126	int r = _minimum_to_decode(want_to_read, available_chunks, &minimum_shard_ids);
	127	if (r != 0) {
	128	return r;
	129	}
	130	vector<pair<int, int>> default_subchunks;
	131	default_subchunks.push_back(make_pair(0, get_sub_chunk_count()));
	132	for (auto &&id : minimum_shard_ids) {
	133	minimum->insert(make_pair(id, default_subchunks));
	134	}
	135	return 0;
	136	}
	137
7c673cae FG	138	int ErasureCode::minimum_to_decode_with_cost(const set<int> &want_to_read,
	139	const map<int, int> &available,
	140	set<int> *minimum)
	141	{
	142	set <int> available_chunks;
	143	for (map<int, int>::const_iterator i = available.begin();
	144	i != available.end();
	145	++i)
	146	available_chunks.insert(i->first);
11fdf7f2	147	return _minimum_to_decode(want_to_read, available_chunks, minimum);
7c673cae FG	148	}
	149
	150	int ErasureCode::encode_prepare(const bufferlist &raw,
	151	map<int, bufferlist> &encoded) const
	152	{
	153	unsigned int k = get_data_chunk_count();
	154	unsigned int m = get_chunk_count() - k;
	155	unsigned blocksize = get_chunk_size(raw.length());
	156	unsigned padded_chunks = k - raw.length() / blocksize;
	157	bufferlist prepared = raw;
	158
	159	for (unsigned int i = 0; i < k - padded_chunks; i++) {
	160	bufferlist &chunk = encoded[chunk_index(i)];
	161	chunk.substr_of(prepared, i * blocksize, blocksize);
	162	chunk.rebuild_aligned_size_and_memory(blocksize, SIMD_ALIGN);
11fdf7f2	163	ceph_assert(chunk.is_contiguous());
7c673cae FG	164	}
	165	if (padded_chunks) {
	166	unsigned remainder = raw.length() - (k - padded_chunks) * blocksize;
	167	bufferptr buf(buffer::create_aligned(blocksize, SIMD_ALIGN));
	168
9f95a23c	169	raw.begin((k - padded_chunks) * blocksize).copy(remainder, buf.c_str());
7c673cae FG	170	buf.zero(remainder, blocksize - remainder);
	171	encoded[chunk_index(k-padded_chunks)].push_back(std::move(buf));
	172
	173	for (unsigned int i = k - padded_chunks + 1; i < k; i++) {
	174	bufferptr buf(buffer::create_aligned(blocksize, SIMD_ALIGN));
	175	buf.zero();
	176	encoded[chunk_index(i)].push_back(std::move(buf));
	177	}
	178	}
	179	for (unsigned int i = k; i < k + m; i++) {
	180	bufferlist &chunk = encoded[chunk_index(i)];
	181	chunk.push_back(buffer::create_aligned(blocksize, SIMD_ALIGN));
	182	}
	183
	184	return 0;
	185	}
	186
	187	int ErasureCode::encode(const set<int> &want_to_encode,
	188	const bufferlist &in,
	189	map<int, bufferlist> *encoded)
	190	{
	191	unsigned int k = get_data_chunk_count();
	192	unsigned int m = get_chunk_count() - k;
	193	bufferlist out;
	194	int err = encode_prepare(in, *encoded);
	195	if (err)
	196	return err;
	197	encode_chunks(want_to_encode, encoded);
	198	for (unsigned int i = 0; i < k + m; i++) {
	199	if (want_to_encode.count(i) == 0)
	200	encoded->erase(i);
	201	}
	202	return 0;
	203	}
	204
11fdf7f2 TL	205	int ErasureCode::_decode(const set<int> &want_to_read,
	206	const map<int, bufferlist> &chunks,
	207	map<int, bufferlist> *decoded)
7c673cae FG	208	{
	209	vector<int> have;
	210	have.reserve(chunks.size());
	211	for (map<int, bufferlist>::const_iterator i = chunks.begin();
	212	i != chunks.end();
	213	++i) {
	214	have.push_back(i->first);
	215	}
	216	if (includes(
	217	have.begin(), have.end(), want_to_read.begin(), want_to_read.end())) {
	218	for (set<int>::iterator i = want_to_read.begin();
	219	i != want_to_read.end();
	220	++i) {
	221	(decoded)[i] = chunks.find(*i)->second;
	222	}
	223	return 0;
	224	}
	225	unsigned int k = get_data_chunk_count();
	226	unsigned int m = get_chunk_count() - k;
	227	unsigned blocksize = (*chunks.begin()).second.length();
	228	for (unsigned int i = 0; i < k + m; i++) {
	229	if (chunks.find(i) == chunks.end()) {
11fdf7f2	230	bufferlist tmp;
7c673cae	231	bufferptr ptr(buffer::create_aligned(blocksize, SIMD_ALIGN));
11fdf7f2 TL	232	tmp.push_back(ptr);
	233	tmp.claim_append((*decoded)[i]);
	234	(*decoded)[i].swap(tmp);
7c673cae FG	235	} else {
	236	(*decoded)[i] = chunks.find(i)->second;
	237	(*decoded)[i].rebuild_aligned(SIMD_ALIGN);
	238	}
	239	}
	240	return decode_chunks(want_to_read, chunks, decoded);
	241	}
	242
11fdf7f2 TL	243	int ErasureCode::decode(const set<int> &want_to_read,
	244	const map<int, bufferlist> &chunks,
	245	map<int, bufferlist> *decoded, int chunk_size)
	246	{
	247	return _decode(want_to_read, chunks, decoded);
	248	}
	249
7c673cae FG	250	int ErasureCode::parse(const ErasureCodeProfile &profile,
	251	ostream *ss)
	252	{
	253	return to_mapping(profile, ss);
	254	}
	255
	256	const vector<int> &ErasureCode::get_chunk_mapping() const {
	257	return chunk_mapping;
	258	}
	259
	260	int ErasureCode::to_mapping(const ErasureCodeProfile &profile,
	261	ostream *ss)
	262	{
	263	if (profile.find("mapping") != profile.end()) {
	264	std::string mapping = profile.find("mapping")->second;
	265	int position = 0;
	266	vector<int> coding_chunk_mapping;
	267	for(std::string::iterator it = mapping.begin(); it != mapping.end(); ++it) {
	268	if (*it == 'D')
	269	chunk_mapping.push_back(position);
	270	else
	271	coding_chunk_mapping.push_back(position);
	272	position++;
	273	}
	274	chunk_mapping.insert(chunk_mapping.end(),
	275	coding_chunk_mapping.begin(),
	276	coding_chunk_mapping.end());
	277	}
	278	return 0;
	279	}
	280
	281	int ErasureCode::to_int(const std::string &name,
	282	ErasureCodeProfile &profile,
	283	int *value,
	284	const std::string &default_value,
	285	ostream *ss)
	286	{
	287	if (profile.find(name) == profile.end() \|\|
	288	profile.find(name)->second.size() == 0)
	289	profile[name] = default_value;
	290	std::string p = profile.find(name)->second;
	291	std::string err;
	292	int r = strict_strtol(p.c_str(), 10, &err);
	293	if (!err.empty()) {
	294	*ss << "could not convert " << name << "=" << p
	295	<< " to int because " << err
	296	<< ", set to default " << default_value << std::endl;
	297	*value = strict_strtol(default_value.c_str(), 10, &err);
	298	return -EINVAL;
	299	}
	300	*value = r;
	301	return 0;
	302	}
	303
	304	int ErasureCode::to_bool(const std::string &name,
	305	ErasureCodeProfile &profile,
	306	bool *value,
	307	const std::string &default_value,
	308	ostream *ss)
	309	{
	310	if (profile.find(name) == profile.end() \|\|
	311	profile.find(name)->second.size() == 0)
	312	profile[name] = default_value;
	313	const std::string p = profile.find(name)->second;
314	*value = (p == "yes") \|\| (p == "true");
315	return 0;
316	}
317
318	int ErasureCode::to_string(const std::string &name,
319	ErasureCodeProfile &profile,
320	std::string *value,
321	const std::string &default_value,
322	ostream *ss)
323	{
324	if (profile.find(name) == profile.end() \|\|
325	profile.find(name)->second.size() == 0)
326	profile[name] = default_value;
327	*value = profile[name];
328	return 0;
329	}
330
331	int ErasureCode::decode_concat(const map<int, bufferlist> &chunks,
332	bufferlist *decoded)
333	{
334	set<int> want_to_read;
335
336	for (unsigned int i = 0; i < get_data_chunk_count(); i++) {
337	want_to_read.insert(chunk_index(i));
338	}
339	map<int, bufferlist> decoded_map;
11fdf7f2	340	int r = _decode(want_to_read, chunks, &decoded_map);
7c673cae FG	341	if (r == 0) {
	342	for (unsigned int i = 0; i < get_data_chunk_count(); i++) {
	343	decoded->claim_append(decoded_map[chunk_index(i)]);
	344	}
	345	}
	346	return r;
	347	}
9f95a23c	348	}