bset.c (c052dd9a26f60bcf70c0c3fcc08e07abb60295cd) bset.c (dc9d98d621bdce0552997200ce855659875a5c9f)
1/*
2 * Code for working with individual keys, and sorted sets of keys with in a
3 * btree node
4 *
5 * Copyright 2012 Google, Inc.
6 */
7
8#include "bcache.h"
9#include "btree.h"
1/*
2 * Code for working with individual keys, and sorted sets of keys with in a
3 * btree node
4 *
5 * Copyright 2012 Google, Inc.
6 */
7
8#include "bcache.h"
9#include "btree.h"
10#include "debug.h"
11
10
11#include <linux/console.h>
12#include <linux/random.h>
13#include <linux/prefetch.h>
14
12#include <linux/random.h>
13#include <linux/prefetch.h>
14
15#ifdef CONFIG_BCACHE_DEBUG
16
17void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned set)
18{
19 struct bkey *k, *next;
20
21 for (k = i->start; k < bset_bkey_last(i); k = next) {
22 next = bkey_next(k);
23
24 printk(KERN_ERR "block %u key %zi/%u: ", set,
25 (uint64_t *) k - i->d, i->keys);
26
27 if (b->ops->key_dump)
28 b->ops->key_dump(b, k);
29 else
30 printk("%llu:%llu\n", KEY_INODE(k), KEY_OFFSET(k));
31
32 if (next < bset_bkey_last(i) &&
33 bkey_cmp(k, b->ops->is_extents ?
34 &START_KEY(next) : next) > 0)
35 printk(KERN_ERR "Key skipped backwards\n");
36 }
37}
38
39void bch_dump_bucket(struct btree_keys *b)
40{
41 unsigned i;
42
43 console_lock();
44 for (i = 0; i <= b->nsets; i++)
45 bch_dump_bset(b, b->set[i].data,
46 bset_sector_offset(b, b->set[i].data));
47 console_unlock();
48}
49
50int __bch_count_data(struct btree_keys *b)
51{
52 unsigned ret = 0;
53 struct btree_iter iter;
54 struct bkey *k;
55
56 if (b->ops->is_extents)
57 for_each_key(b, k, &iter)
58 ret += KEY_SIZE(k);
59 return ret;
60}
61
62void __bch_check_keys(struct btree_keys *b, const char *fmt, ...)
63{
64 va_list args;
65 struct bkey *k, *p = NULL;
66 struct btree_iter iter;
67 const char *err;
68
69 for_each_key(b, k, &iter) {
70 if (b->ops->is_extents) {
71 err = "Keys out of order";
72 if (p && bkey_cmp(&START_KEY(p), &START_KEY(k)) > 0)
73 goto bug;
74
75 if (bch_ptr_invalid(b, k))
76 continue;
77
78 err = "Overlapping keys";
79 if (p && bkey_cmp(p, &START_KEY(k)) > 0)
80 goto bug;
81 } else {
82 if (bch_ptr_bad(b, k))
83 continue;
84
85 err = "Duplicate keys";
86 if (p && !bkey_cmp(p, k))
87 goto bug;
88 }
89 p = k;
90 }
91#if 0
92 err = "Key larger than btree node key";
93 if (p && bkey_cmp(p, &b->key) > 0)
94 goto bug;
95#endif
96 return;
97bug:
98 bch_dump_bucket(b);
99
100 va_start(args, fmt);
101 vprintk(fmt, args);
102 va_end(args);
103
104 panic("bch_check_keys error: %s:\n", err);
105}
106
107static void bch_btree_iter_next_check(struct btree_iter *iter)
108{
109 struct bkey *k = iter->data->k, *next = bkey_next(k);
110
111 if (next < iter->data->end &&
112 bkey_cmp(k, iter->b->ops->is_extents ?
113 &START_KEY(next) : next) > 0) {
114 bch_dump_bucket(iter->b);
115 panic("Key skipped backwards\n");
116 }
117}
118
119#else
120
121static inline void bch_btree_iter_next_check(struct btree_iter *iter) {}
122
123#endif
124
15/* Keylists */
16
17int __bch_keylist_realloc(struct keylist *l, unsigned u64s)
18{
19 size_t oldsize = bch_keylist_nkeys(l);
20 size_t newsize = oldsize + u64s;
21 uint64_t *old_keys = l->keys_p == l->inline_keys ? NULL : l->keys_p;
22 uint64_t *new_keys;

--- 1017 unchanged lines hidden (view full) ---

1040 bch_time_stats_update(&state->time, start_time);
1041}
1042
1043void bch_btree_sort_partial(struct btree *b, unsigned start,
1044 struct bset_sort_state *state)
1045{
1046 size_t order = b->keys.page_order, keys = 0;
1047 struct btree_iter iter;
125/* Keylists */
126
127int __bch_keylist_realloc(struct keylist *l, unsigned u64s)
128{
129 size_t oldsize = bch_keylist_nkeys(l);
130 size_t newsize = oldsize + u64s;
131 uint64_t *old_keys = l->keys_p == l->inline_keys ? NULL : l->keys_p;
132 uint64_t *new_keys;

--- 1017 unchanged lines hidden (view full) ---

1150 bch_time_stats_update(&state->time, start_time);
1151}
1152
1153void bch_btree_sort_partial(struct btree *b, unsigned start,
1154 struct bset_sort_state *state)
1155{
1156 size_t order = b->keys.page_order, keys = 0;
1157 struct btree_iter iter;
1048 int oldsize = bch_count_data(b);
1158 int oldsize = bch_count_data(&b->keys);
1049
1050 __bch_btree_iter_init(&b->keys, &iter, NULL, &b->keys.set[start]);
1051
1052 if (start) {
1053 unsigned i;
1054
1055 for (i = start; i <= b->keys.nsets; i++)
1056 keys += b->keys.set[i].data->keys;
1057
1058 order = roundup_pow_of_two(__set_bytes(b->keys.set->data,
1059 keys)) / PAGE_SIZE;
1060 if (order)
1061 order = ilog2(order);
1062 }
1063
1064 __btree_sort(&b->keys, &iter, start, order, false, state);
1065
1159
1160 __bch_btree_iter_init(&b->keys, &iter, NULL, &b->keys.set[start]);
1161
1162 if (start) {
1163 unsigned i;
1164
1165 for (i = start; i <= b->keys.nsets; i++)
1166 keys += b->keys.set[i].data->keys;
1167
1168 order = roundup_pow_of_two(__set_bytes(b->keys.set->data,
1169 keys)) / PAGE_SIZE;
1170 if (order)
1171 order = ilog2(order);
1172 }
1173
1174 __btree_sort(&b->keys, &iter, start, order, false, state);
1175
1066 EBUG_ON(b->written && oldsize >= 0 && bch_count_data(b) != oldsize);
1176 EBUG_ON(b->written && oldsize >= 0 &&
1177 bch_count_data(&b->keys) != oldsize);
1067}
1068EXPORT_SYMBOL(bch_btree_sort_partial);
1069
1070void bch_btree_sort_and_fix_extents(struct btree_keys *b,
1071 struct btree_iter *iter,
1072 struct bset_sort_state *state)
1073{
1074 __btree_sort(b, iter, 0, b->page_order, true, state);

--- 74 unchanged lines hidden --- 		1178}
1179EXPORT_SYMBOL(bch_btree_sort_partial);
1180
1181void bch_btree_sort_and_fix_extents(struct btree_keys *b,
1182 struct btree_iter *iter,
1183 struct bset_sort_state *state)
1184{
1185 __btree_sort(b, iter, 0, b->page_order, true, state);

--- 74 unchanged lines hidden ---