1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
8 * This is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License version 2.1, as published by the Free Software
11 * Foundation. See file COPYING.
15 #include "include/compat.h"
16 #include "include/types.h"
17 #include "include/buffer.h"
18 #include "osd/osd_types.h"
21 #include "HashIndex.h"
23 #include "common/errno.h"
24 #include "common/debug.h"
25 #define dout_context cct
26 #define dout_subsys ceph_subsys_filestore
28 const string HashIndex::SUBDIR_ATTR = "contents";
29 const string HashIndex::SETTINGS_ATTR = "settings";
30 const string HashIndex::IN_PROGRESS_OP_TAG = "in_progress_op";
32 /// hex digit to integer value
33 int hex_to_int(char c)
35 if (c >= '0' && c <= '9')
37 if (c >= 'A' && c <= 'F')
42 /// int value to hex digit
43 char int_to_hex(int v)
51 /// reverse bits in a nibble (0..15)
52 int reverse_nibble_bits(int in)
62 /// reverse nibble bits in a hex digit
63 char reverse_hexdigit_bits(char c)
65 return int_to_hex(reverse_nibble_bits(hex_to_int(c)));
68 /// reverse nibble bits in a hex string
69 string reverse_hexdigit_bits_string(string s)
71 for (unsigned i=0; i<s.size(); ++i)
72 s[i] = reverse_hexdigit_bits(s[i]);
76 /// compare hex digit (as length 1 string) bitwise
77 bool cmp_hexdigit_bitwise(const string& l, const string& r)
79 assert(l.length() == 1 && r.length() == 1);
80 int lv = hex_to_int(l[0]);
81 int rv = hex_to_int(r[0]);
84 return reverse_nibble_bits(lv) < reverse_nibble_bits(rv);
87 /// compare hex digit string bitwise
88 bool cmp_hexdigit_string_bitwise(const string& l, const string& r)
90 string ll = reverse_hexdigit_bits_string(l);
91 string rr = reverse_hexdigit_bits_string(r);
95 int HashIndex::cleanup() {
97 int r = get_attr_path(vector<string>(), IN_PROGRESS_OP_TAG, bl);
99 // No in progress operations!
102 bufferlist::iterator i = bl.begin();
103 InProgressOp in_progress(i);
105 r = get_info(in_progress.path, &info);
107 return end_split_or_merge(in_progress.path);
112 if (in_progress.is_split())
113 return complete_split(in_progress.path, info);
114 else if (in_progress.is_merge())
115 return complete_merge(in_progress.path, info);
116 else if (in_progress.is_col_split()) {
117 for (vector<string>::iterator i = in_progress.path.begin();
118 i != in_progress.path.end();
120 vector<string> path(in_progress.path.begin(), i);
121 int r = reset_attr(path);
131 int HashIndex::reset_attr(
132 const vector<string> &path)
135 int r = path_exists(path, &exists);
140 map<string, ghobject_t> objects;
141 vector<string> subdirs;
142 r = list_objects(path, 0, 0, &objects);
145 r = list_subdirs(path, &subdirs);
150 info.hash_level = path.size();
151 info.objs = objects.size();
152 info.subdirs = subdirs.size();
153 return set_info(path, info);
156 int HashIndex::col_split_level(
159 const vector<string> &path,
164 /* For each subdir, move, recurse, or ignore based on comparing the low order
165 * bits of the hash represented by the subdir path with inbits, match passed
168 vector<string> subdirs;
169 int r = from.list_subdirs(path, &subdirs);
172 map<string, ghobject_t> objects;
173 r = from.list_objects(path, 0, 0, &objects);
178 for (vector<string>::iterator i = subdirs.begin();
183 vector<string> sub_path(path.begin(), path.end());
184 sub_path.push_back(*i);
185 path_to_hobject_hash_prefix(sub_path, &bits, &hash);
187 if (hobject_t::match_hash(hash, bits, match)) {
197 if (*mkdirred > path.size())
198 *mkdirred = path.size();
199 } // else, skip, doesn't need to be moved or recursed into
201 if (hobject_t::match_hash(hash, inbits, match)) {
204 } // else, skip, doesn't need to be moved or recursed into
207 /* Then, do the same for each object */
208 map<string, ghobject_t> objs_to_move;
209 for (map<string, ghobject_t>::iterator i = objects.begin();
212 if (i->second.match(inbits, match)) {
213 objs_to_move.insert(*i);
217 if (objs_to_move.empty() && to_move.empty())
220 // Make parent directories as needed
221 while (*mkdirred < path.size()) {
224 vector<string> creating_path(path.begin(), path.begin()+*mkdirred);
225 r = to.path_exists(creating_path, &exists);
233 info.hash_level = creating_path.size();
234 if (*mkdirred < path.size() - 1)
236 r = to.start_col_split(creating_path);
239 r = to.create_path(creating_path);
242 r = to.set_info(creating_path, info);
245 r = to.end_split_or_merge(creating_path);
250 subdir_info_s from_info;
251 subdir_info_s to_info;
252 r = from.get_info(path, &from_info);
255 r = to.get_info(path, &to_info);
259 from.start_col_split(path);
260 to.start_col_split(path);
263 for (set<string>::iterator i = to_move.begin();
268 r = move_subdir(from, to, path, *i);
273 for (map<string, ghobject_t>::iterator i = objs_to_move.begin();
274 i != objs_to_move.end();
278 r = move_object(from, to, path, *i);
284 r = to.set_info(path, to_info);
287 r = from.set_info(path, from_info);
290 from.end_split_or_merge(path);
291 to.end_split_or_merge(path);
295 int HashIndex::_split(
298 CollectionIndex* dest) {
299 assert(collection_version() == dest->collection_version());
300 unsigned mkdirred = 0;
301 return col_split_level(
303 *static_cast<HashIndex*>(dest),
310 int HashIndex::split_dirs(const vector<string> &path) {
311 dout(20) << __func__ << " " << path << dendl;
313 int r = get_info(path, &info);
315 dout(10) << "error looking up info for " << path << ": "
316 << cpp_strerror(r) << dendl;
320 if (must_split(info)) {
321 dout(1) << __func__ << " " << path << " has " << info.objs
322 << " objects, starting split." << dendl;
323 r = initiate_split(path, info);
325 dout(10) << "error initiating split on " << path << ": "
326 << cpp_strerror(r) << dendl;
330 r = complete_split(path, info);
331 dout(1) << __func__ << " " << path << " split completed."
334 dout(10) << "error completing split on " << path << ": "
335 << cpp_strerror(r) << dendl;
340 vector<string> subdirs;
341 r = list_subdirs(path, &subdirs);
343 dout(10) << "error listing subdirs of " << path << ": "
344 << cpp_strerror(r) << dendl;
347 for (vector<string>::const_iterator it = subdirs.begin();
348 it != subdirs.end(); ++it) {
349 vector<string> subdir_path(path);
350 subdir_path.push_back(*it);
351 r = split_dirs(subdir_path);
360 int HashIndex::apply_layout_settings() {
362 dout(10) << __func__ << " split multiple = " << split_multiplier
363 << " merge threshold = " << merge_threshold
364 << " split rand factor = " << cct->_conf->filestore_split_rand_factor
366 int r = write_settings();
369 return split_dirs(path);
372 int HashIndex::_init() {
375 int r = set_info(path, info);
378 return write_settings();
381 int HashIndex::write_settings() {
382 if (cct->_conf->filestore_split_rand_factor > 0) {
383 settings.split_rand_factor = rand() % cct->_conf->filestore_split_rand_factor;
385 settings.split_rand_factor = 0;
390 return add_attr_path(path, SETTINGS_ATTR, bl);
393 int HashIndex::read_settings() {
396 int r = get_attr_path(path, SETTINGS_ATTR, bl);
400 derr << __func__ << " error reading settings: " << cpp_strerror(r) << dendl;
403 bufferlist::iterator it = bl.begin();
405 dout(20) << __func__ << " split_rand_factor = " << settings.split_rand_factor << dendl;
409 /* LFNIndex virtual method implementations */
410 int HashIndex::_created(const vector<string> &path,
411 const ghobject_t &oid,
412 const string &mangled_name) {
415 r = get_info(path, &info);
419 r = set_info(path, info);
423 if (must_split(info)) {
424 dout(1) << __func__ << " " << path << " has " << info.objs
425 << " objects, starting split." << dendl;
426 int r = initiate_split(path, info);
429 r = complete_split(path, info);
430 dout(1) << __func__ << " " << path << " split completed."
438 int HashIndex::_remove(const vector<string> &path,
439 const ghobject_t &oid,
440 const string &mangled_name) {
442 r = remove_object(path, oid);
446 r = get_info(path, &info);
450 r = set_info(path, info);
453 if (must_merge(info)) {
454 r = initiate_merge(path, info);
457 return complete_merge(path, info);
463 int HashIndex::_lookup(const ghobject_t &oid,
464 vector<string> *path,
465 string *mangled_name,
467 vector<string> path_comp;
468 get_path_components(oid, &path_comp);
469 vector<string>::iterator next = path_comp.begin();
472 int r = path_exists(*path, &exists);
481 if (next == path_comp.end())
483 path->push_back(*(next++));
485 return get_mangled_name(*path, oid, mangled_name, hardlink);
488 int HashIndex::_collection_list_partial(const ghobject_t &start,
489 const ghobject_t &end,
491 vector<ghobject_t> *ls,
498 dout(20) << __func__ << " start:" << start << " end:" << end << "-" << max_count << " ls.size " << ls->size() << dendl;
499 return list_by_hash(path, end, max_count, next, ls);
502 int HashIndex::prep_delete() {
503 return recursive_remove(vector<string>());
506 int HashIndex::_pre_hash_collection(uint32_t pg_num, uint64_t expected_num_objs) {
509 subdir_info_s root_info;
510 // Make sure there is neither objects nor sub-folders
511 // in this collection
512 ret = get_info(path, &root_info);
516 // Do the folder splitting first
517 ret = pre_split_folder(pg_num, expected_num_objs);
520 // Initialize the folder info starting from root
521 return init_split_folder(path, 0);
524 int HashIndex::pre_split_folder(uint32_t pg_num, uint64_t expected_num_objs)
526 // If folder merging is enabled (by setting the threshold positive),
528 if (merge_threshold > 0)
530 const coll_t c = coll();
531 // Do not split if the expected number of objects in this collection is zero (by default)
532 if (expected_num_objs == 0)
535 // Calculate the number of leaf folders (which actually store files)
536 // need to be created
537 const uint64_t objs_per_folder = ((uint64_t)(abs(merge_threshold)) * (uint64_t)split_multiplier + settings.split_rand_factor) * 16;
538 uint64_t leavies = expected_num_objs / objs_per_folder ;
540 if (leavies == 0 || expected_num_objs == objs_per_folder)
544 if (!c.is_pg_prefix(&spgid))
546 const ps_t ps = spgid.pgid.ps();
548 // the most significant bits of pg_num
549 const int pg_num_bits = calc_num_bits(pg_num - 1);
551 // calculate the number of levels we only create one sub folder
552 int num = pg_num_bits / 4;
553 // pg num's hex value is like 1xxx,xxxx,xxxx but not 1111,1111,1111,
554 // so that splitting starts at level 3
555 if (pg_num_bits % 4 == 0 && pg_num < ((uint32_t)1 << pg_num_bits)) {
560 // Start with creation that only has one subfolder
561 vector<string> paths;
564 ps_t v = tmp_id & 0x0000000f;
565 paths.push_back(to_hex(v));
566 ret = create_path(paths);
567 if (ret < 0 && ret != -EEXIST)
569 tmp_id = tmp_id >> 4;
572 // Starting from here, we can split by creating multiple subfolders
573 const int left_bits = pg_num_bits - dump_num * 4;
574 // this variable denotes how many bits (for this level) that can be
575 // used for sub folder splitting
576 int split_bits = 4 - left_bits;
577 // the below logic is inspired by rados.h#ceph_stable_mod,
578 // it basically determines how many sub-folders should we
579 // create for splitting
580 assert(pg_num_bits > 0); // otherwise BAD_SHIFT
581 if (((1 << (pg_num_bits - 1)) | ps) >= pg_num) {
584 const uint32_t subs = (1 << split_bits);
585 // Calculate how many levels we create starting from here
588 while (leavies > 1) {
590 leavies = leavies >> 4;
592 for (uint32_t i = 0; i < subs; ++i) {
593 assert(split_bits <= 4); // otherwise BAD_SHIFT
594 int v = tmp_id | (i << ((4 - split_bits) % 4));
595 paths.push_back(to_hex(v));
596 ret = create_path(paths);
597 if (ret < 0 && ret != -EEXIST)
599 ret = recursive_create_path(paths, level);
607 int HashIndex::init_split_folder(vector<string> &path, uint32_t hash_level)
609 // Get the number of sub directories for the current path
610 vector<string> subdirs;
611 int ret = list_subdirs(path, &subdirs);
615 info.subdirs = subdirs.size();
616 info.hash_level = hash_level;
617 ret = set_info(path, info);
620 ret = fsync_dir(path);
624 // Do the same for subdirs
625 vector<string>::const_iterator iter;
626 for (iter = subdirs.begin(); iter != subdirs.end(); ++iter) {
627 path.push_back(*iter);
628 ret = init_split_folder(path, hash_level + 1);
636 int HashIndex::recursive_create_path(vector<string>& path, int level)
640 for (int i = 0; i < 16; ++i) {
641 path.push_back(to_hex(i));
642 int ret = create_path(path);
643 if (ret < 0 && ret != -EEXIST)
645 ret = recursive_create_path(path, level - 1);
653 int HashIndex::recursive_remove(const vector<string> &path) {
654 return _recursive_remove(path, true);
657 int HashIndex::_recursive_remove(const vector<string> &path, bool top) {
658 vector<string> subdirs;
659 dout(20) << __func__ << " path=" << path << dendl;
660 int r = list_subdirs(path, &subdirs);
663 map<string, ghobject_t> objects;
664 r = list_objects(path, 0, 0, &objects);
667 if (!objects.empty())
669 vector<string> subdir(path);
670 for (vector<string>::iterator i = subdirs.begin();
673 subdir.push_back(*i);
674 r = _recursive_remove(subdir, false);
682 return remove_path(path);
685 int HashIndex::start_col_split(const vector<string> &path) {
687 InProgressOp op_tag(InProgressOp::COL_SPLIT, path);
689 int r = add_attr_path(vector<string>(), IN_PROGRESS_OP_TAG, bl);
692 return fsync_dir(vector<string>());
695 int HashIndex::start_split(const vector<string> &path) {
697 InProgressOp op_tag(InProgressOp::SPLIT, path);
699 int r = add_attr_path(vector<string>(), IN_PROGRESS_OP_TAG, bl);
702 return fsync_dir(vector<string>());
705 int HashIndex::start_merge(const vector<string> &path) {
707 InProgressOp op_tag(InProgressOp::MERGE, path);
709 int r = add_attr_path(vector<string>(), IN_PROGRESS_OP_TAG, bl);
712 return fsync_dir(vector<string>());
715 int HashIndex::end_split_or_merge(const vector<string> &path) {
716 return remove_attr_path(vector<string>(), IN_PROGRESS_OP_TAG);
719 int HashIndex::get_info(const vector<string> &path, subdir_info_s *info) {
721 int r = get_attr_path(path, SUBDIR_ATTR, buf);
724 bufferlist::iterator bufiter = buf.begin();
725 info->decode(bufiter);
726 assert(path.size() == (unsigned)info->hash_level);
730 int HashIndex::set_info(const vector<string> &path, const subdir_info_s &info) {
732 assert(path.size() == (unsigned)info.hash_level);
734 return add_attr_path(path, SUBDIR_ATTR, buf);
737 bool HashIndex::must_merge(const subdir_info_s &info) {
738 return (info.hash_level > 0 &&
739 merge_threshold > 0 &&
740 info.objs < (unsigned)merge_threshold &&
744 bool HashIndex::must_split(const subdir_info_s &info) {
745 return (info.hash_level < (unsigned)MAX_HASH_LEVEL &&
746 info.objs > ((unsigned)(abs(merge_threshold) * split_multiplier + settings.split_rand_factor) * 16));
750 int HashIndex::initiate_merge(const vector<string> &path, subdir_info_s info) {
751 return start_merge(path);
754 int HashIndex::complete_merge(const vector<string> &path, subdir_info_s info) {
755 vector<string> dst = path;
757 subdir_info_s dstinfo;
759 r = path_exists(path, &exists);
762 r = get_info(dst, &dstinfo);
766 r = move_objects(path, dst);
772 r = remove_path(path);
776 if (must_merge(dstinfo)) {
777 r = initiate_merge(dst, dstinfo);
783 return complete_merge(dst, dstinfo);
788 return end_split_or_merge(path);
791 int HashIndex::initiate_split(const vector<string> &path, subdir_info_s info) {
792 return start_split(path);
795 int HashIndex::complete_split(const vector<string> &path, subdir_info_s info) {
796 int level = info.hash_level;
797 map<string, ghobject_t> objects;
798 vector<string> dst = path;
801 r = list_objects(path, 0, 0, &objects);
804 vector<string> subdirs_vec;
805 r = list_subdirs(path, &subdirs_vec);
809 subdirs.insert(subdirs_vec.begin(), subdirs_vec.end());
810 map<string, map<string, ghobject_t> > mapped;
811 map<string, ghobject_t> moved;
813 for (map<string, ghobject_t>::iterator i = objects.begin();
816 vector<string> new_path;
817 get_path_components(i->second, &new_path);
818 mapped[new_path[level]][i->first] = i->second;
820 for (map<string, map<string, ghobject_t> >::iterator i = mapped.begin();
823 dst[level] = i->first;
824 /* If the info already exists, it must be correct,
825 * we may be picking up a partially finished split */
827 // subdir has already been fully copied
828 if (subdirs.count(i->first) && !get_info(dst, &temp)) {
829 for (map<string, ghobject_t>::iterator j = i->second.begin();
830 j != i->second.end();
832 moved[j->first] = j->second;
834 objects.erase(j->first);
840 subdir_info_s info_new;
841 info_new.objs = i->second.size();
842 info_new.subdirs = 0;
843 info_new.hash_level = level + 1;
844 if (must_merge(info_new) && !subdirs.count(i->first)) {
849 // Subdir doesn't yet exist
850 if (!subdirs.count(i->first)) {
852 r = create_path(dst);
855 } // else subdir has been created but only partially copied
857 for (map<string, ghobject_t>::iterator j = i->second.begin();
858 j != i->second.end();
860 moved[j->first] = j->second;
862 objects.erase(j->first);
863 r = link_object(path, dst, j->second, j->first);
864 // May be a partially finished split
865 if (r < 0 && r != -EEXIST) {
874 // Presence of info must imply that all objects have been copied
875 r = set_info(dst, info_new);
885 r = remove_objects(path, moved, &objects);
888 info.objs = objects.size();
889 r = reset_attr(path);
895 return end_split_or_merge(path);
898 void HashIndex::get_path_components(const ghobject_t &oid,
899 vector<string> *path) {
900 char buf[MAX_HASH_LEVEL + 1];
901 snprintf(buf, sizeof(buf), "%.*X", MAX_HASH_LEVEL, (uint32_t)oid.hobj.get_nibblewise_key());
903 // Path components are the hex characters of oid.hobj.hash, least
905 for (int i = 0; i < MAX_HASH_LEVEL; ++i) {
906 path->push_back(string(&buf[i], 1));
910 string HashIndex::get_hash_str(uint32_t hash) {
911 char buf[MAX_HASH_LEVEL + 1];
912 snprintf(buf, sizeof(buf), "%.*X", MAX_HASH_LEVEL, hash);
914 for (int i = 0; i < MAX_HASH_LEVEL; ++i) {
915 retval.push_back(buf[MAX_HASH_LEVEL - 1 - i]);
920 string HashIndex::get_path_str(const ghobject_t &oid) {
921 assert(!oid.is_max());
922 return get_hash_str(oid.hobj.get_hash());
925 uint32_t HashIndex::hash_prefix_to_hash(string prefix) {
926 while (prefix.size() < sizeof(uint32_t) * 2) {
927 prefix.push_back('0');
930 sscanf(prefix.c_str(), "%x", &hash);
932 hash = ((hash & 0x0f0f0f0f) << 4) | ((hash & 0xf0f0f0f0) >> 4);
933 hash = ((hash & 0x00ff00ff) << 8) | ((hash & 0xff00ff00) >> 8);
934 hash = ((hash & 0x0000ffff) << 16) | ((hash & 0xffff0000) >> 16);
938 int HashIndex::get_path_contents_by_hash_bitwise(
939 const vector<string> &path,
940 const ghobject_t *next_object,
941 set<string, CmpHexdigitStringBitwise> *hash_prefixes,
942 set<pair<string, ghobject_t>, CmpPairBitwise> *objects)
944 map<string, ghobject_t> rev_objects;
946 r = list_objects(path, 0, 0, &rev_objects);
950 for (map<string, ghobject_t>::iterator i = rev_objects.begin();
951 i != rev_objects.end();
953 if (next_object && i->second < *next_object)
955 string hash_prefix = get_path_str(i->second);
956 hash_prefixes->insert(hash_prefix);
957 objects->insert(pair<string, ghobject_t>(hash_prefix, i->second));
959 vector<string> subdirs;
960 r = list_subdirs(path, &subdirs);
964 // sort subdirs bitwise (by reversing hex digit nibbles)
965 std::sort(subdirs.begin(), subdirs.end(), cmp_hexdigit_bitwise);
967 // Local to this function, we will convert the prefix strings
968 // (previously simply the reversed hex digits) to also have each
969 // digit's nibbles reversed. This will make the strings sort
972 for (vector<string>::const_iterator i = path.begin();
975 cur_prefix.append(reverse_hexdigit_bits_string(*i));
977 string next_object_string;
979 next_object_string = reverse_hexdigit_bits_string(get_path_str(*next_object));
980 for (vector<string>::iterator i = subdirs.begin();
983 string candidate = cur_prefix + reverse_hexdigit_bits_string(*i);
985 if (next_object->is_max())
987 if (candidate < next_object_string.substr(0, candidate.size()))
990 // re-reverse the hex digit nibbles for the caller
991 hash_prefixes->insert(reverse_hexdigit_bits_string(candidate));
996 int HashIndex::list_by_hash(const vector<string> &path,
997 const ghobject_t &end,
1000 vector<ghobject_t> *out)
1003 return list_by_hash_bitwise(path, end, max_count, next, out);
1006 int HashIndex::list_by_hash_bitwise(
1007 const vector<string> &path,
1008 const ghobject_t& end,
1011 vector<ghobject_t> *out)
1013 vector<string> next_path = path;
1014 next_path.push_back("");
1015 set<string, CmpHexdigitStringBitwise> hash_prefixes;
1016 set<pair<string, ghobject_t>, CmpPairBitwise> objects;
1017 int r = get_path_contents_by_hash_bitwise(path,
1023 for (set<string, CmpHexdigitStringBitwise>::iterator i = hash_prefixes.begin();
1024 i != hash_prefixes.end();
1026 dout(20) << __func__ << " prefix " << *i << dendl;
1027 set<pair<string, ghobject_t>, CmpPairBitwise>::iterator j = objects.lower_bound(
1028 make_pair(*i, ghobject_t()));
1029 if (j == objects.end() || j->first != *i) {
1030 *(next_path.rbegin()) = *(i->rbegin());
1031 ghobject_t next_recurse;
1033 next_recurse = *next;
1034 r = list_by_hash_bitwise(next_path,
1042 if (!next_recurse.is_max()) {
1044 *next = next_recurse;
1048 while (j != objects.end() && j->first == *i) {
1049 if (max_count > 0 && out->size() == (unsigned)max_count) {
1054 if (j->second >= end) {
1059 if (!next || j->second >= *next) {
1060 dout(20) << __func__ << " prefix " << *i << " ob " << j->second << dendl;
1061 out->push_back(j->second);
1068 *next = ghobject_t::get_max();