bset.c 33 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Code for working with individual keys, and sorted sets of keys with in a
  4. * btree node
  5. *
  6. * Copyright 2012 Google, Inc.
  7. */
  8. #define pr_fmt(fmt) "bcache: %s() " fmt, __func__
  9. #include "util.h"
  10. #include "bset.h"
  11. #include <linux/console.h>
  12. #include <linux/sched/clock.h>
  13. #include <linux/random.h>
  14. #include <linux/prefetch.h>
  15. #ifdef CONFIG_BCACHE_DEBUG
  16. void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned int set)
  17. {
  18. struct bkey *k, *next;
  19. for (k = i->start; k < bset_bkey_last(i); k = next) {
  20. next = bkey_next(k);
  21. pr_err("block %u key %u/%u: ", set,
  22. (unsigned int) ((u64 *) k - i->d), i->keys);
  23. if (b->ops->key_dump)
  24. b->ops->key_dump(b, k);
  25. else
  26. pr_cont("%llu:%llu\n", KEY_INODE(k), KEY_OFFSET(k));
  27. if (next < bset_bkey_last(i) &&
  28. bkey_cmp(k, b->ops->is_extents ?
  29. &START_KEY(next) : next) > 0)
  30. pr_err("Key skipped backwards\n");
  31. }
  32. }
  33. void bch_dump_bucket(struct btree_keys *b)
  34. {
  35. unsigned int i;
  36. console_lock();
  37. for (i = 0; i <= b->nsets; i++)
  38. bch_dump_bset(b, b->set[i].data,
  39. bset_sector_offset(b, b->set[i].data));
  40. console_unlock();
  41. }
  42. int __bch_count_data(struct btree_keys *b)
  43. {
  44. unsigned int ret = 0;
  45. struct btree_iter iter;
  46. struct bkey *k;
  47. if (b->ops->is_extents)
  48. for_each_key(b, k, &iter)
  49. ret += KEY_SIZE(k);
  50. return ret;
  51. }
  52. void __bch_check_keys(struct btree_keys *b, const char *fmt, ...)
  53. {
  54. va_list args;
  55. struct bkey *k, *p = NULL;
  56. struct btree_iter iter;
  57. const char *err;
  58. for_each_key(b, k, &iter) {
  59. if (b->ops->is_extents) {
  60. err = "Keys out of order";
  61. if (p && bkey_cmp(&START_KEY(p), &START_KEY(k)) > 0)
  62. goto bug;
  63. if (bch_ptr_invalid(b, k))
  64. continue;
  65. err = "Overlapping keys";
  66. if (p && bkey_cmp(p, &START_KEY(k)) > 0)
  67. goto bug;
  68. } else {
  69. if (bch_ptr_bad(b, k))
  70. continue;
  71. err = "Duplicate keys";
  72. if (p && !bkey_cmp(p, k))
  73. goto bug;
  74. }
  75. p = k;
  76. }
  77. #if 0
  78. err = "Key larger than btree node key";
  79. if (p && bkey_cmp(p, &b->key) > 0)
  80. goto bug;
  81. #endif
  82. return;
  83. bug:
  84. bch_dump_bucket(b);
  85. va_start(args, fmt);
  86. vprintk(fmt, args);
  87. va_end(args);
  88. panic("bch_check_keys error: %s:\n", err);
  89. }
  90. static void bch_btree_iter_next_check(struct btree_iter *iter)
  91. {
  92. struct bkey *k = iter->data->k, *next = bkey_next(k);
  93. if (next < iter->data->end &&
  94. bkey_cmp(k, iter->b->ops->is_extents ?
  95. &START_KEY(next) : next) > 0) {
  96. bch_dump_bucket(iter->b);
  97. panic("Key skipped backwards\n");
  98. }
  99. }
  100. #else
  101. static inline void bch_btree_iter_next_check(struct btree_iter *iter) {}
  102. #endif
  103. /* Keylists */
  104. int __bch_keylist_realloc(struct keylist *l, unsigned int u64s)
  105. {
  106. size_t oldsize = bch_keylist_nkeys(l);
  107. size_t newsize = oldsize + u64s;
  108. uint64_t *old_keys = l->keys_p == l->inline_keys ? NULL : l->keys_p;
  109. uint64_t *new_keys;
  110. newsize = roundup_pow_of_two(newsize);
  111. if (newsize <= KEYLIST_INLINE ||
  112. roundup_pow_of_two(oldsize) == newsize)
  113. return 0;
  114. new_keys = krealloc(old_keys, sizeof(uint64_t) * newsize, GFP_NOIO);
  115. if (!new_keys)
  116. return -ENOMEM;
  117. if (!old_keys)
  118. memcpy(new_keys, l->inline_keys, sizeof(uint64_t) * oldsize);
  119. l->keys_p = new_keys;
  120. l->top_p = new_keys + oldsize;
  121. return 0;
  122. }
  123. /* Pop the top key of keylist by pointing l->top to its previous key */
  124. struct bkey *bch_keylist_pop(struct keylist *l)
  125. {
  126. struct bkey *k = l->keys;
  127. if (k == l->top)
  128. return NULL;
  129. while (bkey_next(k) != l->top)
  130. k = bkey_next(k);
  131. return l->top = k;
  132. }
  133. /* Pop the bottom key of keylist and update l->top_p */
  134. void bch_keylist_pop_front(struct keylist *l)
  135. {
  136. l->top_p -= bkey_u64s(l->keys);
  137. memmove(l->keys,
  138. bkey_next(l->keys),
  139. bch_keylist_bytes(l));
  140. }
  141. /* Key/pointer manipulation */
  142. void bch_bkey_copy_single_ptr(struct bkey *dest, const struct bkey *src,
  143. unsigned int i)
  144. {
  145. BUG_ON(i > KEY_PTRS(src));
  146. /* Only copy the header, key, and one pointer. */
  147. memcpy(dest, src, 2 * sizeof(uint64_t));
  148. dest->ptr[0] = src->ptr[i];
  149. SET_KEY_PTRS(dest, 1);
  150. /* We didn't copy the checksum so clear that bit. */
  151. SET_KEY_CSUM(dest, 0);
  152. }
  153. bool __bch_cut_front(const struct bkey *where, struct bkey *k)
  154. {
  155. unsigned int i, len = 0;
  156. if (bkey_cmp(where, &START_KEY(k)) <= 0)
  157. return false;
  158. if (bkey_cmp(where, k) < 0)
  159. len = KEY_OFFSET(k) - KEY_OFFSET(where);
  160. else
  161. bkey_copy_key(k, where);
  162. for (i = 0; i < KEY_PTRS(k); i++)
  163. SET_PTR_OFFSET(k, i, PTR_OFFSET(k, i) + KEY_SIZE(k) - len);
  164. BUG_ON(len > KEY_SIZE(k));
  165. SET_KEY_SIZE(k, len);
  166. return true;
  167. }
  168. bool __bch_cut_back(const struct bkey *where, struct bkey *k)
  169. {
  170. unsigned int len = 0;
  171. if (bkey_cmp(where, k) >= 0)
  172. return false;
  173. BUG_ON(KEY_INODE(where) != KEY_INODE(k));
  174. if (bkey_cmp(where, &START_KEY(k)) > 0)
  175. len = KEY_OFFSET(where) - KEY_START(k);
  176. bkey_copy_key(k, where);
  177. BUG_ON(len > KEY_SIZE(k));
  178. SET_KEY_SIZE(k, len);
  179. return true;
  180. }
  181. /* Auxiliary search trees */
  182. /* 32 bits total: */
  183. #define BKEY_MID_BITS 3
  184. #define BKEY_EXPONENT_BITS 7
  185. #define BKEY_MANTISSA_BITS (32 - BKEY_MID_BITS - BKEY_EXPONENT_BITS)
  186. #define BKEY_MANTISSA_MASK ((1 << BKEY_MANTISSA_BITS) - 1)
  187. struct bkey_float {
  188. unsigned int exponent:BKEY_EXPONENT_BITS;
  189. unsigned int m:BKEY_MID_BITS;
  190. unsigned int mantissa:BKEY_MANTISSA_BITS;
  191. } __packed;
  192. /*
  193. * BSET_CACHELINE was originally intended to match the hardware cacheline size -
  194. * it used to be 64, but I realized the lookup code would touch slightly less
  195. * memory if it was 128.
  196. *
  197. * It definites the number of bytes (in struct bset) per struct bkey_float in
  198. * the auxiliar search tree - when we're done searching the bset_float tree we
  199. * have this many bytes left that we do a linear search over.
  200. *
  201. * Since (after level 5) every level of the bset_tree is on a new cacheline,
  202. * we're touching one fewer cacheline in the bset tree in exchange for one more
  203. * cacheline in the linear search - but the linear search might stop before it
  204. * gets to the second cacheline.
  205. */
  206. #define BSET_CACHELINE 128
  207. /* Space required for the btree node keys */
  208. static inline size_t btree_keys_bytes(struct btree_keys *b)
  209. {
  210. return PAGE_SIZE << b->page_order;
  211. }
  212. static inline size_t btree_keys_cachelines(struct btree_keys *b)
  213. {
  214. return btree_keys_bytes(b) / BSET_CACHELINE;
  215. }
  216. /* Space required for the auxiliary search trees */
  217. static inline size_t bset_tree_bytes(struct btree_keys *b)
  218. {
  219. return btree_keys_cachelines(b) * sizeof(struct bkey_float);
  220. }
  221. /* Space required for the prev pointers */
  222. static inline size_t bset_prev_bytes(struct btree_keys *b)
  223. {
  224. return btree_keys_cachelines(b) * sizeof(uint8_t);
  225. }
  226. /* Memory allocation */
  227. void bch_btree_keys_free(struct btree_keys *b)
  228. {
  229. struct bset_tree *t = b->set;
  230. if (bset_prev_bytes(b) < PAGE_SIZE)
  231. kfree(t->prev);
  232. else
  233. free_pages((unsigned long) t->prev,
  234. get_order(bset_prev_bytes(b)));
  235. if (bset_tree_bytes(b) < PAGE_SIZE)
  236. kfree(t->tree);
  237. else
  238. free_pages((unsigned long) t->tree,
  239. get_order(bset_tree_bytes(b)));
  240. free_pages((unsigned long) t->data, b->page_order);
  241. t->prev = NULL;
  242. t->tree = NULL;
  243. t->data = NULL;
  244. }
  245. int bch_btree_keys_alloc(struct btree_keys *b,
  246. unsigned int page_order,
  247. gfp_t gfp)
  248. {
  249. struct bset_tree *t = b->set;
  250. BUG_ON(t->data);
  251. b->page_order = page_order;
  252. t->data = (void *) __get_free_pages(__GFP_COMP|gfp, b->page_order);
  253. if (!t->data)
  254. goto err;
  255. t->tree = bset_tree_bytes(b) < PAGE_SIZE
  256. ? kmalloc(bset_tree_bytes(b), gfp)
  257. : (void *) __get_free_pages(gfp, get_order(bset_tree_bytes(b)));
  258. if (!t->tree)
  259. goto err;
  260. t->prev = bset_prev_bytes(b) < PAGE_SIZE
  261. ? kmalloc(bset_prev_bytes(b), gfp)
  262. : (void *) __get_free_pages(gfp, get_order(bset_prev_bytes(b)));
  263. if (!t->prev)
  264. goto err;
  265. return 0;
  266. err:
  267. bch_btree_keys_free(b);
  268. return -ENOMEM;
  269. }
  270. void bch_btree_keys_init(struct btree_keys *b, const struct btree_keys_ops *ops,
  271. bool *expensive_debug_checks)
  272. {
  273. b->ops = ops;
  274. b->expensive_debug_checks = expensive_debug_checks;
  275. b->nsets = 0;
  276. b->last_set_unwritten = 0;
  277. /*
  278. * struct btree_keys in embedded in struct btree, and struct
  279. * bset_tree is embedded into struct btree_keys. They are all
  280. * initialized as 0 by kzalloc() in mca_bucket_alloc(), and
  281. * b->set[0].data is allocated in bch_btree_keys_alloc(), so we
  282. * don't have to initiate b->set[].size and b->set[].data here
  283. * any more.
  284. */
  285. }
  286. /* Binary tree stuff for auxiliary search trees */
  287. /*
  288. * return array index next to j when does in-order traverse
  289. * of a binary tree which is stored in a linear array
  290. */
  291. static unsigned int inorder_next(unsigned int j, unsigned int size)
  292. {
  293. if (j * 2 + 1 < size) {
  294. j = j * 2 + 1;
  295. while (j * 2 < size)
  296. j *= 2;
  297. } else
  298. j >>= ffz(j) + 1;
  299. return j;
  300. }
  301. /*
  302. * return array index previous to j when does in-order traverse
  303. * of a binary tree which is stored in a linear array
  304. */
  305. static unsigned int inorder_prev(unsigned int j, unsigned int size)
  306. {
  307. if (j * 2 < size) {
  308. j = j * 2;
  309. while (j * 2 + 1 < size)
  310. j = j * 2 + 1;
  311. } else
  312. j >>= ffs(j);
  313. return j;
  314. }
  315. /*
  316. * I have no idea why this code works... and I'm the one who wrote it
  317. *
  318. * However, I do know what it does:
  319. * Given a binary tree constructed in an array (i.e. how you normally implement
  320. * a heap), it converts a node in the tree - referenced by array index - to the
  321. * index it would have if you did an inorder traversal.
  322. *
  323. * Also tested for every j, size up to size somewhere around 6 million.
  324. *
  325. * The binary tree starts at array index 1, not 0
  326. * extra is a function of size:
  327. * extra = (size - rounddown_pow_of_two(size - 1)) << 1;
  328. */
  329. static unsigned int __to_inorder(unsigned int j,
  330. unsigned int size,
  331. unsigned int extra)
  332. {
  333. unsigned int b = fls(j);
  334. unsigned int shift = fls(size - 1) - b;
  335. j ^= 1U << (b - 1);
  336. j <<= 1;
  337. j |= 1;
  338. j <<= shift;
  339. if (j > extra)
  340. j -= (j - extra) >> 1;
  341. return j;
  342. }
  343. /*
  344. * Return the cacheline index in bset_tree->data, where j is index
  345. * from a linear array which stores the auxiliar binary tree
  346. */
  347. static unsigned int to_inorder(unsigned int j, struct bset_tree *t)
  348. {
  349. return __to_inorder(j, t->size, t->extra);
  350. }
  351. static unsigned int __inorder_to_tree(unsigned int j,
  352. unsigned int size,
  353. unsigned int extra)
  354. {
  355. unsigned int shift;
  356. if (j > extra)
  357. j += j - extra;
  358. shift = ffs(j);
  359. j >>= shift;
  360. j |= roundup_pow_of_two(size) >> shift;
  361. return j;
  362. }
  363. /*
  364. * Return an index from a linear array which stores the auxiliar binary
  365. * tree, j is the cacheline index of t->data.
  366. */
  367. static unsigned int inorder_to_tree(unsigned int j, struct bset_tree *t)
  368. {
  369. return __inorder_to_tree(j, t->size, t->extra);
  370. }
  371. #if 0
  372. void inorder_test(void)
  373. {
  374. unsigned long done = 0;
  375. ktime_t start = ktime_get();
  376. for (unsigned int size = 2;
  377. size < 65536000;
  378. size++) {
  379. unsigned int extra =
  380. (size - rounddown_pow_of_two(size - 1)) << 1;
  381. unsigned int i = 1, j = rounddown_pow_of_two(size - 1);
  382. if (!(size % 4096))
  383. pr_notice("loop %u, %llu per us\n", size,
  384. done / ktime_us_delta(ktime_get(), start));
  385. while (1) {
  386. if (__inorder_to_tree(i, size, extra) != j)
  387. panic("size %10u j %10u i %10u", size, j, i);
  388. if (__to_inorder(j, size, extra) != i)
  389. panic("size %10u j %10u i %10u", size, j, i);
  390. if (j == rounddown_pow_of_two(size) - 1)
  391. break;
  392. BUG_ON(inorder_prev(inorder_next(j, size), size) != j);
  393. j = inorder_next(j, size);
  394. i++;
  395. }
  396. done += size - 1;
  397. }
  398. }
  399. #endif
  400. /*
  401. * Cacheline/offset <-> bkey pointer arithmetic:
  402. *
  403. * t->tree is a binary search tree in an array; each node corresponds to a key
  404. * in one cacheline in t->set (BSET_CACHELINE bytes).
  405. *
  406. * This means we don't have to store the full index of the key that a node in
  407. * the binary tree points to; to_inorder() gives us the cacheline, and then
  408. * bkey_float->m gives us the offset within that cacheline, in units of 8 bytes.
  409. *
  410. * cacheline_to_bkey() and friends abstract out all the pointer arithmetic to
  411. * make this work.
  412. *
  413. * To construct the bfloat for an arbitrary key we need to know what the key
  414. * immediately preceding it is: we have to check if the two keys differ in the
  415. * bits we're going to store in bkey_float->mantissa. t->prev[j] stores the size
  416. * of the previous key so we can walk backwards to it from t->tree[j]'s key.
  417. */
  418. static struct bkey *cacheline_to_bkey(struct bset_tree *t,
  419. unsigned int cacheline,
  420. unsigned int offset)
  421. {
  422. return ((void *) t->data) + cacheline * BSET_CACHELINE + offset * 8;
  423. }
  424. static unsigned int bkey_to_cacheline(struct bset_tree *t, struct bkey *k)
  425. {
  426. return ((void *) k - (void *) t->data) / BSET_CACHELINE;
  427. }
  428. static unsigned int bkey_to_cacheline_offset(struct bset_tree *t,
  429. unsigned int cacheline,
  430. struct bkey *k)
  431. {
  432. return (u64 *) k - (u64 *) cacheline_to_bkey(t, cacheline, 0);
  433. }
  434. static struct bkey *tree_to_bkey(struct bset_tree *t, unsigned int j)
  435. {
  436. return cacheline_to_bkey(t, to_inorder(j, t), t->tree[j].m);
  437. }
  438. static struct bkey *tree_to_prev_bkey(struct bset_tree *t, unsigned int j)
  439. {
  440. return (void *) (((uint64_t *) tree_to_bkey(t, j)) - t->prev[j]);
  441. }
  442. /*
  443. * For the write set - the one we're currently inserting keys into - we don't
  444. * maintain a full search tree, we just keep a simple lookup table in t->prev.
  445. */
  446. static struct bkey *table_to_bkey(struct bset_tree *t, unsigned int cacheline)
  447. {
  448. return cacheline_to_bkey(t, cacheline, t->prev[cacheline]);
  449. }
  450. static inline uint64_t shrd128(uint64_t high, uint64_t low, uint8_t shift)
  451. {
  452. low >>= shift;
  453. low |= (high << 1) << (63U - shift);
  454. return low;
  455. }
  456. /*
  457. * Calculate mantissa value for struct bkey_float.
  458. * If most significant bit of f->exponent is not set, then
  459. * - f->exponent >> 6 is 0
  460. * - p[0] points to bkey->low
  461. * - p[-1] borrows bits from KEY_INODE() of bkey->high
  462. * if most isgnificant bits of f->exponent is set, then
  463. * - f->exponent >> 6 is 1
  464. * - p[0] points to bits from KEY_INODE() of bkey->high
  465. * - p[-1] points to other bits from KEY_INODE() of
  466. * bkey->high too.
  467. * See make_bfloat() to check when most significant bit of f->exponent
  468. * is set or not.
  469. */
  470. static inline unsigned int bfloat_mantissa(const struct bkey *k,
  471. struct bkey_float *f)
  472. {
  473. const uint64_t *p = &k->low - (f->exponent >> 6);
  474. return shrd128(p[-1], p[0], f->exponent & 63) & BKEY_MANTISSA_MASK;
  475. }
  476. static void make_bfloat(struct bset_tree *t, unsigned int j)
  477. {
  478. struct bkey_float *f = &t->tree[j];
  479. struct bkey *m = tree_to_bkey(t, j);
  480. struct bkey *p = tree_to_prev_bkey(t, j);
  481. struct bkey *l = is_power_of_2(j)
  482. ? t->data->start
  483. : tree_to_prev_bkey(t, j >> ffs(j));
  484. struct bkey *r = is_power_of_2(j + 1)
  485. ? bset_bkey_idx(t->data, t->data->keys - bkey_u64s(&t->end))
  486. : tree_to_bkey(t, j >> (ffz(j) + 1));
  487. BUG_ON(m < l || m > r);
  488. BUG_ON(bkey_next(p) != m);
  489. /*
  490. * If l and r have different KEY_INODE values (different backing
  491. * device), f->exponent records how many least significant bits
  492. * are different in KEY_INODE values and sets most significant
  493. * bits to 1 (by +64).
  494. * If l and r have same KEY_INODE value, f->exponent records
  495. * how many different bits in least significant bits of bkey->low.
  496. * See bfloat_mantiss() how the most significant bit of
  497. * f->exponent is used to calculate bfloat mantissa value.
  498. */
  499. if (KEY_INODE(l) != KEY_INODE(r))
  500. f->exponent = fls64(KEY_INODE(r) ^ KEY_INODE(l)) + 64;
  501. else
  502. f->exponent = fls64(r->low ^ l->low);
  503. f->exponent = max_t(int, f->exponent - BKEY_MANTISSA_BITS, 0);
  504. /*
  505. * Setting f->exponent = 127 flags this node as failed, and causes the
  506. * lookup code to fall back to comparing against the original key.
  507. */
  508. if (bfloat_mantissa(m, f) != bfloat_mantissa(p, f))
  509. f->mantissa = bfloat_mantissa(m, f) - 1;
  510. else
  511. f->exponent = 127;
  512. }
  513. static void bset_alloc_tree(struct btree_keys *b, struct bset_tree *t)
  514. {
  515. if (t != b->set) {
  516. unsigned int j = roundup(t[-1].size,
  517. 64 / sizeof(struct bkey_float));
  518. t->tree = t[-1].tree + j;
  519. t->prev = t[-1].prev + j;
  520. }
  521. while (t < b->set + MAX_BSETS)
  522. t++->size = 0;
  523. }
  524. static void bch_bset_build_unwritten_tree(struct btree_keys *b)
  525. {
  526. struct bset_tree *t = bset_tree_last(b);
  527. BUG_ON(b->last_set_unwritten);
  528. b->last_set_unwritten = 1;
  529. bset_alloc_tree(b, t);
  530. if (t->tree != b->set->tree + btree_keys_cachelines(b)) {
  531. t->prev[0] = bkey_to_cacheline_offset(t, 0, t->data->start);
  532. t->size = 1;
  533. }
  534. }
  535. void bch_bset_init_next(struct btree_keys *b, struct bset *i, uint64_t magic)
  536. {
  537. if (i != b->set->data) {
  538. b->set[++b->nsets].data = i;
  539. i->seq = b->set->data->seq;
  540. } else
  541. get_random_bytes(&i->seq, sizeof(uint64_t));
  542. i->magic = magic;
  543. i->version = 0;
  544. i->keys = 0;
  545. bch_bset_build_unwritten_tree(b);
  546. }
  547. /*
  548. * Build auxiliary binary tree 'struct bset_tree *t', this tree is used to
  549. * accelerate bkey search in a btree node (pointed by bset_tree->data in
  550. * memory). After search in the auxiliar tree by calling bset_search_tree(),
  551. * a struct bset_search_iter is returned which indicates range [l, r] from
  552. * bset_tree->data where the searching bkey might be inside. Then a followed
  553. * linear comparison does the exact search, see __bch_bset_search() for how
  554. * the auxiliary tree is used.
  555. */
  556. void bch_bset_build_written_tree(struct btree_keys *b)
  557. {
  558. struct bset_tree *t = bset_tree_last(b);
  559. struct bkey *prev = NULL, *k = t->data->start;
  560. unsigned int j, cacheline = 1;
  561. b->last_set_unwritten = 0;
  562. bset_alloc_tree(b, t);
  563. t->size = min_t(unsigned int,
  564. bkey_to_cacheline(t, bset_bkey_last(t->data)),
  565. b->set->tree + btree_keys_cachelines(b) - t->tree);
  566. if (t->size < 2) {
  567. t->size = 0;
  568. return;
  569. }
  570. t->extra = (t->size - rounddown_pow_of_two(t->size - 1)) << 1;
  571. /* First we figure out where the first key in each cacheline is */
  572. for (j = inorder_next(0, t->size);
  573. j;
  574. j = inorder_next(j, t->size)) {
  575. while (bkey_to_cacheline(t, k) < cacheline)
  576. prev = k, k = bkey_next(k);
  577. t->prev[j] = bkey_u64s(prev);
  578. t->tree[j].m = bkey_to_cacheline_offset(t, cacheline++, k);
  579. }
  580. while (bkey_next(k) != bset_bkey_last(t->data))
  581. k = bkey_next(k);
  582. t->end = *k;
  583. /* Then we build the tree */
  584. for (j = inorder_next(0, t->size);
  585. j;
  586. j = inorder_next(j, t->size))
  587. make_bfloat(t, j);
  588. }
  589. /* Insert */
  590. void bch_bset_fix_invalidated_key(struct btree_keys *b, struct bkey *k)
  591. {
  592. struct bset_tree *t;
  593. unsigned int inorder, j = 1;
  594. for (t = b->set; t <= bset_tree_last(b); t++)
  595. if (k < bset_bkey_last(t->data))
  596. goto found_set;
  597. BUG();
  598. found_set:
  599. if (!t->size || !bset_written(b, t))
  600. return;
  601. inorder = bkey_to_cacheline(t, k);
  602. if (k == t->data->start)
  603. goto fix_left;
  604. if (bkey_next(k) == bset_bkey_last(t->data)) {
  605. t->end = *k;
  606. goto fix_right;
  607. }
  608. j = inorder_to_tree(inorder, t);
  609. if (j &&
  610. j < t->size &&
  611. k == tree_to_bkey(t, j))
  612. fix_left: do {
  613. make_bfloat(t, j);
  614. j = j * 2;
  615. } while (j < t->size);
  616. j = inorder_to_tree(inorder + 1, t);
  617. if (j &&
  618. j < t->size &&
  619. k == tree_to_prev_bkey(t, j))
  620. fix_right: do {
  621. make_bfloat(t, j);
  622. j = j * 2 + 1;
  623. } while (j < t->size);
  624. }
  625. static void bch_bset_fix_lookup_table(struct btree_keys *b,
  626. struct bset_tree *t,
  627. struct bkey *k)
  628. {
  629. unsigned int shift = bkey_u64s(k);
  630. unsigned int j = bkey_to_cacheline(t, k);
  631. /* We're getting called from btree_split() or btree_gc, just bail out */
  632. if (!t->size)
  633. return;
  634. /*
  635. * k is the key we just inserted; we need to find the entry in the
  636. * lookup table for the first key that is strictly greater than k:
  637. * it's either k's cacheline or the next one
  638. */
  639. while (j < t->size &&
  640. table_to_bkey(t, j) <= k)
  641. j++;
  642. /*
  643. * Adjust all the lookup table entries, and find a new key for any that
  644. * have gotten too big
  645. */
  646. for (; j < t->size; j++) {
  647. t->prev[j] += shift;
  648. if (t->prev[j] > 7) {
  649. k = table_to_bkey(t, j - 1);
  650. while (k < cacheline_to_bkey(t, j, 0))
  651. k = bkey_next(k);
  652. t->prev[j] = bkey_to_cacheline_offset(t, j, k);
  653. }
  654. }
  655. if (t->size == b->set->tree + btree_keys_cachelines(b) - t->tree)
  656. return;
  657. /* Possibly add a new entry to the end of the lookup table */
  658. for (k = table_to_bkey(t, t->size - 1);
  659. k != bset_bkey_last(t->data);
  660. k = bkey_next(k))
  661. if (t->size == bkey_to_cacheline(t, k)) {
  662. t->prev[t->size] =
  663. bkey_to_cacheline_offset(t, t->size, k);
  664. t->size++;
  665. }
  666. }
  667. /*
  668. * Tries to merge l and r: l should be lower than r
  669. * Returns true if we were able to merge. If we did merge, l will be the merged
  670. * key, r will be untouched.
  671. */
  672. bool bch_bkey_try_merge(struct btree_keys *b, struct bkey *l, struct bkey *r)
  673. {
  674. if (!b->ops->key_merge)
  675. return false;
  676. /*
  677. * Generic header checks
  678. * Assumes left and right are in order
  679. * Left and right must be exactly aligned
  680. */
  681. if (!bch_bkey_equal_header(l, r) ||
  682. bkey_cmp(l, &START_KEY(r)))
  683. return false;
  684. return b->ops->key_merge(b, l, r);
  685. }
  686. void bch_bset_insert(struct btree_keys *b, struct bkey *where,
  687. struct bkey *insert)
  688. {
  689. struct bset_tree *t = bset_tree_last(b);
  690. BUG_ON(!b->last_set_unwritten);
  691. BUG_ON(bset_byte_offset(b, t->data) +
  692. __set_bytes(t->data, t->data->keys + bkey_u64s(insert)) >
  693. PAGE_SIZE << b->page_order);
  694. memmove((uint64_t *) where + bkey_u64s(insert),
  695. where,
  696. (void *) bset_bkey_last(t->data) - (void *) where);
  697. t->data->keys += bkey_u64s(insert);
  698. bkey_copy(where, insert);
  699. bch_bset_fix_lookup_table(b, t, where);
  700. }
  701. unsigned int bch_btree_insert_key(struct btree_keys *b, struct bkey *k,
  702. struct bkey *replace_key)
  703. {
  704. unsigned int status = BTREE_INSERT_STATUS_NO_INSERT;
  705. struct bset *i = bset_tree_last(b)->data;
  706. struct bkey *m, *prev = NULL;
  707. struct btree_iter iter;
  708. struct bkey preceding_key_on_stack = ZERO_KEY;
  709. struct bkey *preceding_key_p = &preceding_key_on_stack;
  710. BUG_ON(b->ops->is_extents && !KEY_SIZE(k));
  711. /*
  712. * If k has preceding key, preceding_key_p will be set to address
  713. * of k's preceding key; otherwise preceding_key_p will be set
  714. * to NULL inside preceding_key().
  715. */
  716. if (b->ops->is_extents)
  717. preceding_key(&START_KEY(k), &preceding_key_p);
  718. else
  719. preceding_key(k, &preceding_key_p);
  720. m = bch_btree_iter_init(b, &iter, preceding_key_p);
  721. if (b->ops->insert_fixup(b, k, &iter, replace_key))
  722. return status;
  723. status = BTREE_INSERT_STATUS_INSERT;
  724. while (m != bset_bkey_last(i) &&
  725. bkey_cmp(k, b->ops->is_extents ? &START_KEY(m) : m) > 0)
  726. prev = m, m = bkey_next(m);
  727. /* prev is in the tree, if we merge we're done */
  728. status = BTREE_INSERT_STATUS_BACK_MERGE;
  729. if (prev &&
  730. bch_bkey_try_merge(b, prev, k))
  731. goto merged;
  732. #if 0
  733. status = BTREE_INSERT_STATUS_OVERWROTE;
  734. if (m != bset_bkey_last(i) &&
  735. KEY_PTRS(m) == KEY_PTRS(k) && !KEY_SIZE(m))
  736. goto copy;
  737. #endif
  738. status = BTREE_INSERT_STATUS_FRONT_MERGE;
  739. if (m != bset_bkey_last(i) &&
  740. bch_bkey_try_merge(b, k, m))
  741. goto copy;
  742. bch_bset_insert(b, m, k);
  743. copy: bkey_copy(m, k);
  744. merged:
  745. return status;
  746. }
  747. /* Lookup */
  748. struct bset_search_iter {
  749. struct bkey *l, *r;
  750. };
  751. static struct bset_search_iter bset_search_write_set(struct bset_tree *t,
  752. const struct bkey *search)
  753. {
  754. unsigned int li = 0, ri = t->size;
  755. while (li + 1 != ri) {
  756. unsigned int m = (li + ri) >> 1;
  757. if (bkey_cmp(table_to_bkey(t, m), search) > 0)
  758. ri = m;
  759. else
  760. li = m;
  761. }
  762. return (struct bset_search_iter) {
  763. table_to_bkey(t, li),
  764. ri < t->size ? table_to_bkey(t, ri) : bset_bkey_last(t->data)
  765. };
  766. }
  767. static struct bset_search_iter bset_search_tree(struct bset_tree *t,
  768. const struct bkey *search)
  769. {
  770. struct bkey *l, *r;
  771. struct bkey_float *f;
  772. unsigned int inorder, j, n = 1;
  773. do {
  774. unsigned int p = n << 4;
  775. if (p < t->size)
  776. prefetch(&t->tree[p]);
  777. j = n;
  778. f = &t->tree[j];
  779. if (likely(f->exponent != 127)) {
  780. if (f->mantissa >= bfloat_mantissa(search, f))
  781. n = j * 2;
  782. else
  783. n = j * 2 + 1;
  784. } else {
  785. if (bkey_cmp(tree_to_bkey(t, j), search) > 0)
  786. n = j * 2;
  787. else
  788. n = j * 2 + 1;
  789. }
  790. } while (n < t->size);
  791. inorder = to_inorder(j, t);
  792. /*
  793. * n would have been the node we recursed to - the low bit tells us if
  794. * we recursed left or recursed right.
  795. */
  796. if (n & 1) {
  797. l = cacheline_to_bkey(t, inorder, f->m);
  798. if (++inorder != t->size) {
  799. f = &t->tree[inorder_next(j, t->size)];
  800. r = cacheline_to_bkey(t, inorder, f->m);
  801. } else
  802. r = bset_bkey_last(t->data);
  803. } else {
  804. r = cacheline_to_bkey(t, inorder, f->m);
  805. if (--inorder) {
  806. f = &t->tree[inorder_prev(j, t->size)];
  807. l = cacheline_to_bkey(t, inorder, f->m);
  808. } else
  809. l = t->data->start;
  810. }
  811. return (struct bset_search_iter) {l, r};
  812. }
  813. struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t,
  814. const struct bkey *search)
  815. {
  816. struct bset_search_iter i;
  817. /*
  818. * First, we search for a cacheline, then lastly we do a linear search
  819. * within that cacheline.
  820. *
  821. * To search for the cacheline, there's three different possibilities:
  822. * * The set is too small to have a search tree, so we just do a linear
  823. * search over the whole set.
  824. * * The set is the one we're currently inserting into; keeping a full
  825. * auxiliary search tree up to date would be too expensive, so we
  826. * use a much simpler lookup table to do a binary search -
  827. * bset_search_write_set().
  828. * * Or we use the auxiliary search tree we constructed earlier -
  829. * bset_search_tree()
  830. */
  831. if (unlikely(!t->size)) {
  832. i.l = t->data->start;
  833. i.r = bset_bkey_last(t->data);
  834. } else if (bset_written(b, t)) {
  835. /*
  836. * Each node in the auxiliary search tree covers a certain range
  837. * of bits, and keys above and below the set it covers might
  838. * differ outside those bits - so we have to special case the
  839. * start and end - handle that here:
  840. */
  841. if (unlikely(bkey_cmp(search, &t->end) >= 0))
  842. return bset_bkey_last(t->data);
  843. if (unlikely(bkey_cmp(search, t->data->start) < 0))
  844. return t->data->start;
  845. i = bset_search_tree(t, search);
  846. } else {
  847. BUG_ON(!b->nsets &&
  848. t->size < bkey_to_cacheline(t, bset_bkey_last(t->data)));
  849. i = bset_search_write_set(t, search);
  850. }
  851. if (btree_keys_expensive_checks(b)) {
  852. BUG_ON(bset_written(b, t) &&
  853. i.l != t->data->start &&
  854. bkey_cmp(tree_to_prev_bkey(t,
  855. inorder_to_tree(bkey_to_cacheline(t, i.l), t)),
  856. search) > 0);
  857. BUG_ON(i.r != bset_bkey_last(t->data) &&
  858. bkey_cmp(i.r, search) <= 0);
  859. }
  860. while (likely(i.l != i.r) &&
  861. bkey_cmp(i.l, search) <= 0)
  862. i.l = bkey_next(i.l);
  863. return i.l;
  864. }
  865. /* Btree iterator */
  866. typedef bool (btree_iter_cmp_fn)(struct btree_iter_set,
  867. struct btree_iter_set);
  868. static inline bool btree_iter_cmp(struct btree_iter_set l,
  869. struct btree_iter_set r)
  870. {
  871. return bkey_cmp(l.k, r.k) > 0;
  872. }
  873. static inline bool btree_iter_end(struct btree_iter *iter)
  874. {
  875. return !iter->used;
  876. }
  877. void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k,
  878. struct bkey *end)
  879. {
  880. if (k != end)
  881. BUG_ON(!heap_add(iter,
  882. ((struct btree_iter_set) { k, end }),
  883. btree_iter_cmp));
  884. }
  885. static struct bkey *__bch_btree_iter_init(struct btree_keys *b,
  886. struct btree_iter *iter,
  887. struct bkey *search,
  888. struct bset_tree *start)
  889. {
  890. struct bkey *ret = NULL;
  891. iter->size = ARRAY_SIZE(iter->data);
  892. iter->used = 0;
  893. #ifdef CONFIG_BCACHE_DEBUG
  894. iter->b = b;
  895. #endif
  896. for (; start <= bset_tree_last(b); start++) {
  897. ret = bch_bset_search(b, start, search);
  898. bch_btree_iter_push(iter, ret, bset_bkey_last(start->data));
  899. }
  900. return ret;
  901. }
  902. struct bkey *bch_btree_iter_init(struct btree_keys *b,
  903. struct btree_iter *iter,
  904. struct bkey *search)
  905. {
  906. return __bch_btree_iter_init(b, iter, search, b->set);
  907. }
  908. static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter,
  909. btree_iter_cmp_fn *cmp)
  910. {
  911. struct btree_iter_set b __maybe_unused;
  912. struct bkey *ret = NULL;
  913. if (!btree_iter_end(iter)) {
  914. bch_btree_iter_next_check(iter);
  915. ret = iter->data->k;
  916. iter->data->k = bkey_next(iter->data->k);
  917. if (iter->data->k > iter->data->end) {
  918. WARN_ONCE(1, "bset was corrupt!\n");
  919. iter->data->k = iter->data->end;
  920. }
  921. if (iter->data->k == iter->data->end)
  922. heap_pop(iter, b, cmp);
  923. else
  924. heap_sift(iter, 0, cmp);
  925. }
  926. return ret;
  927. }
  928. struct bkey *bch_btree_iter_next(struct btree_iter *iter)
  929. {
  930. return __bch_btree_iter_next(iter, btree_iter_cmp);
  931. }
  932. struct bkey *bch_btree_iter_next_filter(struct btree_iter *iter,
  933. struct btree_keys *b, ptr_filter_fn fn)
  934. {
  935. struct bkey *ret;
  936. do {
  937. ret = bch_btree_iter_next(iter);
  938. } while (ret && fn(b, ret));
  939. return ret;
  940. }
  941. /* Mergesort */
  942. void bch_bset_sort_state_free(struct bset_sort_state *state)
  943. {
  944. mempool_exit(&state->pool);
  945. }
  946. int bch_bset_sort_state_init(struct bset_sort_state *state,
  947. unsigned int page_order)
  948. {
  949. spin_lock_init(&state->time.lock);
  950. state->page_order = page_order;
  951. state->crit_factor = int_sqrt(1 << page_order);
  952. return mempool_init_page_pool(&state->pool, 1, page_order);
  953. }
  954. static void btree_mergesort(struct btree_keys *b, struct bset *out,
  955. struct btree_iter *iter,
  956. bool fixup, bool remove_stale)
  957. {
  958. int i;
  959. struct bkey *k, *last = NULL;
  960. BKEY_PADDED(k) tmp;
  961. bool (*bad)(struct btree_keys *, const struct bkey *) = remove_stale
  962. ? bch_ptr_bad
  963. : bch_ptr_invalid;
  964. /* Heapify the iterator, using our comparison function */
  965. for (i = iter->used / 2 - 1; i >= 0; --i)
  966. heap_sift(iter, i, b->ops->sort_cmp);
  967. while (!btree_iter_end(iter)) {
  968. if (b->ops->sort_fixup && fixup)
  969. k = b->ops->sort_fixup(iter, &tmp.k);
  970. else
  971. k = NULL;
  972. if (!k)
  973. k = __bch_btree_iter_next(iter, b->ops->sort_cmp);
  974. if (bad(b, k))
  975. continue;
  976. if (!last) {
  977. last = out->start;
  978. bkey_copy(last, k);
  979. } else if (!bch_bkey_try_merge(b, last, k)) {
  980. last = bkey_next(last);
  981. bkey_copy(last, k);
  982. }
  983. }
  984. out->keys = last ? (uint64_t *) bkey_next(last) - out->d : 0;
  985. pr_debug("sorted %i keys\n", out->keys);
  986. }
  987. static void __btree_sort(struct btree_keys *b, struct btree_iter *iter,
  988. unsigned int start, unsigned int order, bool fixup,
  989. struct bset_sort_state *state)
  990. {
  991. uint64_t start_time;
  992. bool used_mempool = false;
  993. struct bset *out = (void *) __get_free_pages(__GFP_NOWARN|GFP_NOWAIT,
  994. order);
  995. if (!out) {
  996. struct page *outp;
  997. BUG_ON(order > state->page_order);
  998. outp = mempool_alloc(&state->pool, GFP_NOIO);
  999. out = page_address(outp);
  1000. used_mempool = true;
  1001. order = state->page_order;
  1002. }
  1003. start_time = local_clock();
  1004. btree_mergesort(b, out, iter, fixup, false);
  1005. b->nsets = start;
  1006. if (!start && order == b->page_order) {
  1007. /*
  1008. * Our temporary buffer is the same size as the btree node's
  1009. * buffer, we can just swap buffers instead of doing a big
  1010. * memcpy()
  1011. *
  1012. * Don't worry event 'out' is allocated from mempool, it can
  1013. * still be swapped here. Because state->pool is a page mempool
  1014. * creaated by by mempool_init_page_pool(), which allocates
  1015. * pages by alloc_pages() indeed.
  1016. */
  1017. out->magic = b->set->data->magic;
  1018. out->seq = b->set->data->seq;
  1019. out->version = b->set->data->version;
  1020. swap(out, b->set->data);
  1021. } else {
  1022. b->set[start].data->keys = out->keys;
  1023. memcpy(b->set[start].data->start, out->start,
  1024. (void *) bset_bkey_last(out) - (void *) out->start);
  1025. }
  1026. if (used_mempool)
  1027. mempool_free(virt_to_page(out), &state->pool);
  1028. else
  1029. free_pages((unsigned long) out, order);
  1030. bch_bset_build_written_tree(b);
  1031. if (!start)
  1032. bch_time_stats_update(&state->time, start_time);
  1033. }
  1034. void bch_btree_sort_partial(struct btree_keys *b, unsigned int start,
  1035. struct bset_sort_state *state)
  1036. {
  1037. size_t order = b->page_order, keys = 0;
  1038. struct btree_iter iter;
  1039. int oldsize = bch_count_data(b);
  1040. __bch_btree_iter_init(b, &iter, NULL, &b->set[start]);
  1041. if (start) {
  1042. unsigned int i;
  1043. for (i = start; i <= b->nsets; i++)
  1044. keys += b->set[i].data->keys;
  1045. order = get_order(__set_bytes(b->set->data, keys));
  1046. }
  1047. __btree_sort(b, &iter, start, order, false, state);
  1048. EBUG_ON(oldsize >= 0 && bch_count_data(b) != oldsize);
  1049. }
  1050. void bch_btree_sort_and_fix_extents(struct btree_keys *b,
  1051. struct btree_iter *iter,
  1052. struct bset_sort_state *state)
  1053. {
  1054. __btree_sort(b, iter, 0, b->page_order, true, state);
  1055. }
  1056. void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new,
  1057. struct bset_sort_state *state)
  1058. {
  1059. uint64_t start_time = local_clock();
  1060. struct btree_iter iter;
  1061. bch_btree_iter_init(b, &iter, NULL);
  1062. btree_mergesort(b, new->set->data, &iter, false, true);
  1063. bch_time_stats_update(&state->time, start_time);
  1064. new->set->size = 0; // XXX: why?
  1065. }
  1066. #define SORT_CRIT (4096 / sizeof(uint64_t))
  1067. void bch_btree_sort_lazy(struct btree_keys *b, struct bset_sort_state *state)
  1068. {
  1069. unsigned int crit = SORT_CRIT;
  1070. int i;
  1071. /* Don't sort if nothing to do */
  1072. if (!b->nsets)
  1073. goto out;
  1074. for (i = b->nsets - 1; i >= 0; --i) {
  1075. crit *= state->crit_factor;
  1076. if (b->set[i].data->keys < crit) {
  1077. bch_btree_sort_partial(b, i, state);
  1078. return;
  1079. }
  1080. }
  1081. /* Sort if we'd overflow */
  1082. if (b->nsets + 1 == MAX_BSETS) {
  1083. bch_btree_sort(b, state);
  1084. return;
  1085. }
  1086. out:
  1087. bch_bset_build_written_tree(b);
  1088. }
  1089. void bch_btree_keys_stats(struct btree_keys *b, struct bset_stats *stats)
  1090. {
  1091. unsigned int i;
  1092. for (i = 0; i <= b->nsets; i++) {
  1093. struct bset_tree *t = &b->set[i];
  1094. size_t bytes = t->data->keys * sizeof(uint64_t);
  1095. size_t j;
  1096. if (bset_written(b, t)) {
  1097. stats->sets_written++;
  1098. stats->bytes_written += bytes;
  1099. stats->floats += t->size - 1;
  1100. for (j = 1; j < t->size; j++)
  1101. if (t->tree[j].exponent == 127)
  1102. stats->failed++;
  1103. } else {
  1104. stats->sets_unwritten++;
  1105. stats->bytes_unwritten += bytes;
  1106. }
  1107. }
  1108. }