← Back to branch summary

~ubuntu-branches/ubuntu/raring/ceph/raring

« back to all changes in this revision

Viewing changes to src/os/HashIndex.cc

  • Committer: Package Import Robot
  • Author(s): Laszlo Boszormenyi (GCS)
  • Date: 2012-02-05 10:07:38 UTC
  • mfrom: (1.1.7) (0.1.11 sid)
  • Revision ID: package-import@ubuntu.com-20120205100738-00s0bxx93mamy8tk
Tags: 0.41-1
New upstream release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/os/HashIndex.cc
18
18
 
19
19
#include "HashIndex.h"
20
20
 
 
21
#include "common/debug.h"
 
22
#define DOUT_SUBSYS filestore
 
23
 
21
24
const string HashIndex::SUBDIR_ATTR = "contents";
22
25
const string HashIndex::IN_PROGRESS_OP_TAG = "in_progress_op";
23
26
 
122
125
  return get_mangled_name(*path, hoid, mangled_name, exists_out);
123
126
}
124
127
 
125
 
static void split_handle(collection_list_handle_t handle, 
126
 
                         uint32_t *hash, uint32_t *index) {
127
 
  *hash = handle.hash;
128
 
  *index = handle.index;
129
 
}
130
 
 
131
 
static collection_list_handle_t form_handle(uint32_t hash, uint32_t index) {
132
 
  collection_list_handle_t handle;
133
 
  handle.hash = hash;
134
 
  handle.index = index;
135
 
  return handle;
136
 
}
137
 
 
138
 
int HashIndex::_collection_list_partial(snapid_t seq, int max_count,
139
 
                                        vector<hobject_t> *ls, 
140
 
                                        collection_list_handle_t *last) {
141
 
  vector<string> path;
142
 
  uint32_t index, hash;
143
 
  string lower_bound;
144
 
  if (last) {
145
 
    split_handle(*last, &hash, &index);
146
 
    lower_bound = get_hash_str(hash);
147
 
  }
148
 
  int r = list(path, 
149
 
               max_count ? &max_count : NULL, 
150
 
               &seq,
151
 
               last ? &lower_bound : NULL,
152
 
               last ? &index : NULL, 
153
 
               ls);
154
 
  if (r < 0)
155
 
    return r;
156
 
  if (last && ls->size())
157
 
    *last = form_handle(ls->rbegin()->hash, index);
158
 
  return 0;
159
 
}
160
 
 
161
128
int HashIndex::_collection_list(vector<hobject_t> *ls) {
162
129
  vector<string> path;
163
 
  return list(path, NULL, NULL, NULL, NULL, ls);
 
130
  return list_by_hash(path, 0, 0, 0, 0, ls);
 
131
}
 
132
 
 
133
int HashIndex::_collection_list_partial(const hobject_t &start,
 
134
                                        int min_count,
 
135
                                        int max_count,
 
136
                                        snapid_t seq,
 
137
                                        vector<hobject_t> *ls,
 
138
                                        hobject_t *next) {
 
139
  vector<string> path;
 
140
  *next = start;
 
141
  dout(20) << "_collection_list_partial " << start << " " << min_count << "-" << max_count << " ls.size " << ls->size() << dendl;
 
142
  return list_by_hash(path, min_count, max_count, seq, next, ls);
164
143
}
165
144
 
166
145
int HashIndex::start_split(const vector<string> &path) {
207
186
 
208
187
bool HashIndex::must_split(const subdir_info_s &info) {
209
188
  return (info.hash_level < (unsigned)MAX_HASH_LEVEL &&
210
 
          info.objs > ((unsigned)merge_threshold * 32));
 
189
          info.objs > ((unsigned)merge_threshold * 16 * split_multiplier));
211
190
                            
212
191
}
213
192
 
371
350
void HashIndex::get_path_components(const hobject_t &hoid,
372
351
                                    vector<string> *path) {
373
352
  char buf[MAX_HASH_LEVEL + 1];
374
 
  snprintf(buf, sizeof(buf), "%.*X", MAX_HASH_LEVEL, hoid.hash);
 
353
  snprintf(buf, sizeof(buf), "%.*X", MAX_HASH_LEVEL, (uint32_t)hoid.get_filestore_key());
375
354
 
376
 
  // Path components are the hex characters of hoid.hash in, least
 
355
  // Path components are the hex characters of hoid.hash, least
377
356
  // significant first
378
357
  for (int i = 0; i < MAX_HASH_LEVEL; ++i) {
379
 
    path->push_back(string(&buf[MAX_HASH_LEVEL - 1 - i], 1));
 
358
    path->push_back(string(&buf[i], 1));
380
359
  }
381
360
}
382
361
 
394
373
  return get_hash_str(hoid.hash);
395
374
}
396
375
 
397
 
int HashIndex::list(const vector<string> &path,
398
 
                    const int *max_count,
399
 
                    const snapid_t *seq,
400
 
                    const string *lower_bound,
401
 
                    uint32_t *index,
402
 
                    vector<hobject_t> *out) {
403
 
  if (lower_bound)
404
 
    assert(index);
405
 
  vector<string> next_path = path;
406
 
  next_path.push_back("");
407
 
  set<string> hash_prefixes;
408
 
  multimap<string, hobject_t> objects;
 
376
uint32_t HashIndex::hash_prefix_to_hash(string prefix) {
 
377
  while (prefix.size() < sizeof(uint32_t) * 2) {
 
378
    prefix.push_back('0');
 
379
  }
 
380
  uint32_t hash;
 
381
  sscanf(prefix.c_str(), "%x", &hash);
 
382
  // nibble reverse
 
383
  hash = ((hash & 0x0f0f0f0f) << 4) | ((hash & 0xf0f0f0f0) >> 4);
 
384
  hash = ((hash & 0x00ff00ff) << 8) | ((hash & 0xff00ff00) >> 8);
 
385
  hash = ((hash & 0x0000ffff) << 16) | ((hash & 0xffff0000) >> 16);
 
386
  return hash;
 
387
}
 
388
 
 
389
int HashIndex::get_path_contents_by_hash(const vector<string> &path,
 
390
                                         const string *lower_bound,
 
391
                                         const hobject_t *next_object,
 
392
                                         const snapid_t *seq,
 
393
                                         set<string> *hash_prefixes,
 
394
                                         multimap<string, hobject_t> *objects) {
 
395
  set<string> subdirs;
409
396
  map<string, hobject_t> rev_objects;
410
397
  int r;
411
 
  int max = max_count ? *max_count : 0;
412
398
  string cur_prefix;
413
399
  for (vector<string>::const_iterator i = path.begin();
414
400
       i != path.end();
415
401
       ++i) {
416
402
    cur_prefix.append(*i);
417
403
  }
418
 
 
419
404
  r = list_objects(path, 0, 0, &rev_objects);
420
405
  if (r < 0)
421
406
    return r;
425
410
    string hash_prefix = get_path_str(i->second);
426
411
    if (lower_bound && hash_prefix < *lower_bound)
427
412
      continue;
 
413
    if (next_object && i->second < *next_object)
 
414
      continue;
428
415
    if (seq && i->second.snap < *seq)
429
416
      continue;
430
 
    hash_prefixes.insert(hash_prefix);
431
 
    objects.insert(pair<string, hobject_t>(hash_prefix, i->second));
 
417
    hash_prefixes->insert(hash_prefix);
 
418
    objects->insert(pair<string, hobject_t>(hash_prefix, i->second));
432
419
  }
433
 
  set<string> subdirs;
434
420
  r = list_subdirs(path, &subdirs);
435
421
  if (r < 0)
436
422
    return r;
440
426
    string candidate = cur_prefix + *i;
441
427
    if (lower_bound && candidate < lower_bound->substr(0, candidate.size()))
442
428
      continue;
443
 
    hash_prefixes.insert(cur_prefix + *i);
 
429
    if (next_object &&
 
430
        candidate < get_path_str(*next_object).substr(0, candidate.size()))
 
431
      continue;
 
432
    hash_prefixes->insert(cur_prefix + *i);
444
433
  }
 
434
  return 0;
 
435
}
445
436
 
446
 
  uint32_t counter = 0;
 
437
int HashIndex::list_by_hash(const vector<string> &path,
 
438
                            int min_count,
 
439
                            int max_count,
 
440
                            snapid_t seq,
 
441
                            hobject_t *next,
 
442
                            vector<hobject_t> *out) {
 
443
  assert(out);
 
444
  vector<string> next_path = path;
 
445
  next_path.push_back("");
 
446
  set<string> hash_prefixes;
 
447
  multimap<string, hobject_t> objects;
 
448
  int r = get_path_contents_by_hash(path,
 
449
                                    NULL,
 
450
                                    next,
 
451
                                    &seq,
 
452
                                    &hash_prefixes,
 
453
                                    &objects);
 
454
  if (r < 0)
 
455
    return r;
 
456
  dout(20) << " prefixes " << hash_prefixes << dendl;
447
457
  for (set<string>::iterator i = hash_prefixes.begin();
448
 
       i != hash_prefixes.end() && (!max_count || max > 0);
 
458
       i != hash_prefixes.end();
449
459
       ++i) {
450
460
    multimap<string, hobject_t>::iterator j = objects.find(*i);
451
 
    if (j != objects.end()) {
452
 
      counter = 0;
453
 
      for (; (!max_count || max > 0) && j != objects.end() && j->first == *i; ++j, ++counter) {
454
 
        if (lower_bound && *lower_bound == *i && counter < *index)
455
 
          continue;
456
 
        out->push_back(j->second);
457
 
        if (max_count)
458
 
          max--;
 
461
    if (j == objects.end()) {
 
462
      if (min_count > 0 && out->size() > (unsigned)min_count) {
 
463
        if (next)
 
464
          *next = hobject_t("", "", CEPH_NOSNAP, hash_prefix_to_hash(*i));
 
465
        return 0;
459
466
      }
460
 
      if (index)
461
 
        *index = counter;
462
 
      continue;
463
 
    } 
 
467
      *(next_path.rbegin()) = *(i->rbegin());
 
468
      hobject_t next_recurse;
 
469
      if (next)
 
470
        next_recurse = *next;
 
471
      r = list_by_hash(next_path,
 
472
                       min_count,
 
473
                       max_count,
 
474
                       seq,
 
475
                       &next_recurse,
 
476
                       out);
464
477
 
465
 
    // subdir
466
 
    *(next_path.rbegin()) = *(i->rbegin());
467
 
    int old_size = out->size();
468
 
    assert(next_path.size() > path.size());
469
 
    r = list(next_path, max_count ? &max : NULL, seq, lower_bound, index, out);
470
 
    if (r < 0)
471
 
      return r;
472
 
    if (max_count)
473
 
      max -= out->size() - old_size;
 
478
      if (r < 0)
 
479
        return r;
 
480
      if (!next_recurse.is_max()) {
 
481
        if (next)
 
482
          *next = next_recurse;
 
483
        return 0;
 
484
      }
 
485
    } else {
 
486
      while (j != objects.end() && j->first == *i) {
 
487
        if (max_count > 0 && out->size() == (unsigned)max_count) {
 
488
          if (next)
 
489
            *next = j->second;
 
490
          return 0;
 
491
        }
 
492
        if (!next || j->second >= *next) {
 
493
          out->push_back(j->second);
 
494
        }
 
495
        ++j;
 
496
      }
 
497
    }
474
498
  }
 
499
  if (next)
 
500
    *next = hobject_t::get_max();
475
501
  return 0;
476
502
}