4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 only,
8 * as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License version 2 for more details (a copy is included
14 * in the LICENSE file that accompanied this code).
16 * You should have received a copy of the GNU General Public License
17 * version 2 along with this program; If not, see
18 * http://www.gnu.org/licenses/gpl-2.0.html
23 * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
24 * Use is subject to license terms.
26 * Copyright (c) 2012, 2015, Intel Corporation.
29 * This file is part of Lustre, http://www.lustre.org/
30 * Lustre is a trademark of Sun Microsystems, Inc.
33 * implementation of iam format for fixed size records.
35 * Author: Wang Di <wangdi@clusterfs.com>
36 * Author: Nikita Danilov <nikita@clusterfs.com>
39 #include <linux/types.h>
40 #include "osd_internal.h"
47 IAM_LEAF_HEADER_MAGIC = 0x1976 /* This is duplicated in
48 * lustre/utils/create_iam.c */
51 /* This is duplicated in lustre/utils/create_iam.c */
52 struct iam_leaf_head {
57 static inline int iam_lfix_entry_size(const struct iam_leaf *l)
59 return iam_leaf_descr(l)->id_key_size + iam_leaf_descr(l)->id_rec_size;
62 static inline struct iam_lentry *
63 iam_lfix_shift(const struct iam_leaf *l, struct iam_lentry *entry, int shift)
65 return (void *)entry + shift * iam_lfix_entry_size(l);
68 static inline struct iam_key *iam_leaf_key_at(struct iam_lentry *entry)
70 return (struct iam_key *)entry;
73 static inline int lfix_keycmp(const struct iam_container *c,
74 const struct iam_key *k1,
75 const struct iam_key *k2)
77 return memcmp(k1, k2, c->ic_descr->id_key_size);
80 static struct iam_leaf_head *iam_get_head(const struct iam_leaf *l)
82 return (struct iam_leaf_head *)l->il_bh->b_data;
85 static struct iam_lentry *iam_entries(const struct buffer_head *bh)
87 return (void *)bh->b_data + sizeof(struct iam_leaf_head);
90 static struct iam_lentry *iam_get_lentries(const struct iam_leaf *l)
92 return iam_entries(l->il_bh);
95 static int leaf_count_limit(const struct iam_leaf *leaf)
99 free_space = iam_leaf_container(leaf)->ic_object->i_sb->s_blocksize;
100 free_space -= sizeof(struct iam_leaf_head);
101 return free_space / iam_lfix_entry_size(leaf);
104 static int lentry_count_get(const struct iam_leaf *leaf)
106 return le16_to_cpu(iam_get_head(leaf)->ill_count);
109 static void lentry_count_set(struct iam_leaf *leaf, unsigned count)
111 assert_corr(0 <= count && count <= leaf_count_limit(leaf));
112 iam_get_head(leaf)->ill_count = cpu_to_le16(count);
115 static struct iam_lentry *iam_lfix_get_end(const struct iam_leaf *l);
117 #if LDISKFS_CORRECTNESS_ON || LDISKFS_INVARIANT_ON
118 static int iam_leaf_at_rec(const struct iam_leaf *folio)
121 iam_get_lentries(folio) <= folio->il_at &&
122 folio->il_at < iam_lfix_get_end(folio);
126 static struct iam_ikey *iam_lfix_ikey(const struct iam_leaf *l,
127 struct iam_ikey *key)
130 assert_corr(iam_leaf_at_rec(l));
131 return (struct iam_ikey*)ie;
134 static struct iam_key *iam_lfix_key(const struct iam_leaf *l)
137 assert_corr(iam_leaf_at_rec(l));
138 return (struct iam_key*)ie;
141 static int iam_lfix_key_size(const struct iam_leaf *l)
143 return iam_leaf_descr(l)->id_key_size;
146 static void iam_lfix_start(struct iam_leaf *l)
148 l->il_at = iam_get_lentries(l);
151 static inline ptrdiff_t iam_lfix_diff(const struct iam_leaf *l,
152 const struct iam_lentry *e1,
153 const struct iam_lentry *e2)
158 esize = iam_lfix_entry_size(l);
159 diff = (void *)e1 - (void *)e2;
160 assert_corr(diff / esize * esize == diff);
164 static int iam_lfix_init(struct iam_leaf *l)
167 struct iam_leaf_head *ill;
170 assert_corr(l->il_bh != NULL);
172 ill = iam_get_head(l);
173 count = le16_to_cpu(ill->ill_count);
174 if (le16_to_cpu(ill->ill_magic) == IAM_LEAF_HEADER_MAGIC &&
175 0 <= count && count <= leaf_count_limit(l)) {
176 l->il_at = l->il_entries = iam_get_lentries(l);
181 obj = iam_leaf_container(l)->ic_object;
182 CERROR("Wrong magic in node %llu (#%lu): %#x != %#x or "
183 "wrong count: %d (%d)\n",
184 (unsigned long long)l->il_bh->b_blocknr, obj->i_ino,
185 le16_to_cpu(ill->ill_magic), IAM_LEAF_HEADER_MAGIC,
186 count, leaf_count_limit(l));
192 static void iam_lfix_fini(struct iam_leaf *l)
194 l->il_entries = l->il_at = NULL;
197 static struct iam_lentry *iam_lfix_get_end(const struct iam_leaf *l)
199 int count = lentry_count_get(l);
200 struct iam_lentry *ile = iam_lfix_shift(l, l->il_entries, count);
205 static struct iam_rec *iam_lfix_rec(const struct iam_leaf *l)
208 assert_corr(iam_leaf_at_rec(l));
209 return e + iam_leaf_descr(l)->id_key_size;
212 static void iam_lfix_next(struct iam_leaf *l)
214 assert_corr(iam_leaf_at_rec(l));
215 l->il_at = iam_lfix_shift(l, l->il_at, 1);
223 static char hdigit(char ch)
225 static char d[] = "0123456789abcdef";
229 static char *hex(char ch, char *area)
231 area[0] = hdigit(ch >> 4);
232 area[1] = hdigit(ch);
237 static void l_print(struct iam_leaf *leaf, struct iam_lentry *entry)
243 area = (char *)entry;
244 printk(KERN_EMERG "[");
245 for (i = iam_lfix_key_size(leaf); i > 0; --i, ++area)
246 printk("%s", hex(*area, h));
248 for (i = iam_leaf_descr(leaf)->id_rec_size; i > 0; --i, ++area)
249 printk("%s", hex(*area, h));
253 static void lfix_print(struct iam_leaf *leaf)
255 struct iam_lentry *entry;
259 entry = leaf->il_entries;
260 count = lentry_count_get(leaf);
261 printk(KERN_EMERG "lfix: %p %p %d\n", leaf, leaf->il_at, count);
262 for (i = 0; i < count; ++i, entry = iam_lfix_shift(leaf, entry, 1))
263 l_print(leaf, entry);
266 static int iam_lfix_lookup(struct iam_leaf *l, const struct iam_key *k)
268 struct iam_lentry *p, *q, *m, *t;
269 struct iam_container *c;
273 count = lentry_count_get(l);
275 return IAM_LOOKUP_EMPTY;
277 result = IAM_LOOKUP_OK;
278 c = iam_leaf_container(l);
281 q = iam_lfix_shift(l, p, count - 1);
282 if (lfix_keycmp(c, k, iam_leaf_key_at(p)) < 0) {
284 * @k is less than the least key in the leaf
287 result = IAM_LOOKUP_BEFORE;
288 } else if (lfix_keycmp(c, iam_leaf_key_at(q), k) <= 0) {
294 while (iam_lfix_shift(l, p, 1) != q) {
295 m = iam_lfix_shift(l, p, iam_lfix_diff(l, q, p) / 2);
296 assert_corr(p < m && m < q);
297 if (lfix_keycmp(c, iam_leaf_key_at(m), k) <= 0)
302 assert_corr(lfix_keycmp(c, iam_leaf_key_at(p), k) <= 0 &&
303 lfix_keycmp(c, k, iam_leaf_key_at(q)) < 0);
305 * skip over records with duplicate keys.
307 while (p > l->il_entries) {
308 t = iam_lfix_shift(l, p, -1);
309 if (lfix_keycmp(c, iam_leaf_key_at(t), k) == 0)
316 assert_corr(iam_leaf_at_rec(l));
318 if (lfix_keycmp(c, iam_leaf_key_at(l->il_at), k) == 0)
319 result = IAM_LOOKUP_EXACT;
327 static int iam_lfix_ilookup(struct iam_leaf *l, const struct iam_ikey *ik)
329 return iam_lfix_lookup(l, (const struct iam_key *)ik);
332 static void iam_lfix_key_set(struct iam_leaf *l, const struct iam_key *k)
334 assert_corr(iam_leaf_at_rec(l));
335 memcpy(iam_leaf_key_at(l->il_at), k, iam_leaf_descr(l)->id_key_size);
338 static int iam_lfix_key_cmp(const struct iam_leaf *l, const struct iam_key *k)
340 return lfix_keycmp(iam_leaf_container(l), iam_leaf_key_at(l->il_at), k);
343 static int iam_lfix_key_eq(const struct iam_leaf *l, const struct iam_key *k)
345 return !lfix_keycmp(iam_leaf_container(l),
346 iam_leaf_key_at(l->il_at), k);
349 static void iam_lfix_rec_set(struct iam_leaf *l, const struct iam_rec *r)
351 assert_corr(iam_leaf_at_rec(l));
352 memcpy(iam_lfix_rec(l), r, iam_leaf_descr(l)->id_rec_size);
355 static inline int lfix_reccmp(const struct iam_container *c,
356 const struct iam_rec *r1,
357 const struct iam_rec *r2)
359 return memcmp(r1, r2, c->ic_descr->id_rec_size);
362 static int iam_lfix_rec_eq(const struct iam_leaf *l, const struct iam_rec *r)
364 return !lfix_reccmp(iam_leaf_container(l), iam_lfix_rec(l), r);
367 static void iam_lfix_rec_get(const struct iam_leaf *l, struct iam_rec *r)
369 assert_corr(iam_leaf_at_rec(l));
370 memcpy(r, iam_lfix_rec(l), iam_leaf_descr(l)->id_rec_size);
373 static void iam_lfix_rec_add(struct iam_leaf *leaf,
374 const struct iam_key *k, const struct iam_rec *r)
376 struct iam_lentry *end;
377 struct iam_lentry *cur;
378 struct iam_lentry *start;
382 assert_corr(iam_leaf_can_add(leaf, k, r));
384 count = lentry_count_get(leaf);
386 * This branch handles two exceptional cases:
388 * - leaf positioned beyond last record, and
392 if (!iam_leaf_at_end(leaf)) {
393 end = iam_lfix_get_end(leaf);
395 if (lfix_keycmp(iam_leaf_container(leaf),
396 k, iam_leaf_key_at(cur)) >= 0)
400 * Another exceptional case: insertion with the key
401 * less than least key in the leaf.
403 assert_corr(cur == leaf->il_entries);
406 diff = (void *)end - (void *)start;
407 assert_corr(diff >= 0);
408 memmove(iam_lfix_shift(leaf, start, 1), start, diff);
410 lentry_count_set(leaf, count + 1);
411 iam_lfix_key_set(leaf, k);
412 iam_lfix_rec_set(leaf, r);
413 assert_corr(iam_leaf_at_rec(leaf));
416 static void iam_lfix_rec_del(struct iam_leaf *leaf, int shift)
418 struct iam_lentry *next, *end;
422 assert_corr(iam_leaf_at_rec(leaf));
424 count = lentry_count_get(leaf);
425 end = iam_lfix_get_end(leaf);
426 next = iam_lfix_shift(leaf, leaf->il_at, 1);
427 diff = (void *)end - (void *)next;
428 memmove(leaf->il_at, next, diff);
430 lentry_count_set(leaf, count - 1);
433 static int iam_lfix_can_add(const struct iam_leaf *l,
434 const struct iam_key *k, const struct iam_rec *r)
436 return lentry_count_get(l) < leaf_count_limit(l);
439 static int iam_lfix_at_end(const struct iam_leaf *folio)
441 return folio->il_at == iam_lfix_get_end(folio);
444 static void iam_lfix_init_new(struct iam_container *c, struct buffer_head *bh)
446 struct iam_leaf_head *hdr;
448 hdr = (struct iam_leaf_head*)bh->b_data;
449 hdr->ill_magic = cpu_to_le16(IAM_LEAF_HEADER_MAGIC);
450 hdr->ill_count = cpu_to_le16(0);
453 static void iam_lfix_split(struct iam_leaf *l, struct buffer_head **bh,
456 struct iam_path *path;
457 struct iam_leaf_head *hdr;
458 const struct iam_ikey *pivot;
459 struct buffer_head *new_leaf;
468 path = iam_leaf_path(l);
470 hdr = (void *)new_leaf->b_data;
472 count = lentry_count_get(l);
475 start = iam_lfix_shift(l, iam_get_lentries(l), split);
476 finis = iam_lfix_shift(l, iam_get_lentries(l), count);
478 pivot = (const struct iam_ikey *)iam_leaf_key_at(start);
480 memmove(iam_entries(new_leaf), start, finis - start);
481 hdr->ill_count = cpu_to_le16(count - split);
482 lentry_count_set(l, split);
483 if ((void *)l->il_at >= start) {
485 * insertion point moves into new leaf.
490 shift = iam_lfix_diff(l, l->il_at, start);
493 l->il_curidx = new_blknr;
494 result = iam_lfix_init(l);
496 * init cannot fail, as node was just initialized.
498 assert_corr(result == 0);
499 l->il_at = iam_lfix_shift(l, iam_get_lentries(l), shift);
502 * Insert pointer to the new node (together with the least key in
503 * the node) into index node.
505 iam_insert_key_lock(path, path->ip_frame, pivot, new_blknr);
508 static int iam_lfix_leaf_empty(struct iam_leaf *leaf)
510 return lentry_count_get(leaf) == 0;
513 static struct iam_leaf_operations iam_lfix_leaf_ops = {
514 .init = iam_lfix_init,
515 .init_new = iam_lfix_init_new,
516 .fini = iam_lfix_fini,
517 .start = iam_lfix_start,
518 .next = iam_lfix_next,
520 .ikey = iam_lfix_ikey,
522 .key_set = iam_lfix_key_set,
523 .key_cmp = iam_lfix_key_cmp,
524 .key_eq = iam_lfix_key_eq,
525 .key_size = iam_lfix_key_size,
526 .rec_set = iam_lfix_rec_set,
527 .rec_eq = iam_lfix_rec_eq,
528 .rec_get = iam_lfix_rec_get,
529 .lookup = iam_lfix_lookup,
530 .ilookup = iam_lfix_ilookup,
531 .at_end = iam_lfix_at_end,
532 .rec_add = iam_lfix_rec_add,
533 .rec_del = iam_lfix_rec_del,
534 .can_add = iam_lfix_can_add,
535 .split = iam_lfix_split,
536 .leaf_empty = iam_lfix_leaf_empty,
544 /* This is duplicated in lustre/utils/create_iam.c */
546 * Then shalt thou see the dew-BEDABBLED wretch
547 * Turn, and return, indenting with the way;
548 * Each envious brier his weary legs doth scratch,
549 * Each shadow makes him stop, each murmur stay:
550 * For misery is trodden on by many,
551 * And being low never relieved by any.
553 IAM_LFIX_ROOT_MAGIC = 0xbedabb1edULL // d01efull
556 /* This is duplicated in lustre/utils/create_iam.c */
557 struct iam_lfix_root {
562 u8 ilr_indirect_levels;
566 static __u32 iam_lfix_root_ptr(struct iam_container *c)
571 static int iam_lfix_node_init(struct iam_container *c, struct buffer_head *bh,
577 static struct iam_entry *iam_lfix_root_inc(struct iam_container *c,
578 struct iam_path *path,
579 struct iam_frame *frame)
581 struct iam_lfix_root *root;
582 struct iam_entry *entries;
584 entries = frame->entries;
586 dx_set_count(entries, 2);
587 assert_corr(dx_get_limit(entries) == dx_root_limit(path));
589 root = (void *)frame->bh->b_data;
590 assert_corr(le64_to_cpu(root->ilr_magic) == IAM_LFIX_ROOT_MAGIC);
591 root->ilr_indirect_levels ++;
592 frame->at = entries = iam_entry_shift(path, entries, 1);
593 memset(iam_ikey_at(path, entries), 0,
594 iam_path_descr(path)->id_ikey_size);
598 static int iam_lfix_node_check(struct iam_path *path, struct iam_frame *frame)
602 unsigned limit_correct;
603 struct iam_entry *entries;
605 entries = dx_node_get_entries(path, frame);
607 if (frame == path->ip_frames) {
608 struct iam_lfix_root *root;
610 root = (void *)frame->bh->b_data;
611 if (le64_to_cpu(root->ilr_magic) != IAM_LFIX_ROOT_MAGIC) {
614 limit_correct = dx_root_limit(path);
616 limit_correct = dx_node_limit(path);
617 count = dx_get_count(entries);
618 limit = dx_get_limit(entries);
622 if (limit != limit_correct) {
628 static int iam_lfix_node_load(struct iam_path *path, struct iam_frame *frame)
630 struct iam_entry *entries;
632 entries = dx_node_get_entries(path, frame);
634 data = frame->bh->b_data;
636 if (frame == path->ip_frames) {
637 struct iam_lfix_root *root;
640 path->ip_indirect = root->ilr_indirect_levels;
641 if (path->ip_ikey_target == NULL)
642 path->ip_ikey_target =
643 (struct iam_ikey *)path->ip_key_target;
645 frame->entries = frame->at = entries;
649 static int iam_lfix_ikeycmp(const struct iam_container *c,
650 const struct iam_ikey *k1,
651 const struct iam_ikey *k2)
653 return memcmp(k1, k2, c->ic_descr->id_ikey_size);
656 static struct iam_path_descr *iam_lfix_ipd_alloc(const struct iam_container *c,
659 return iam_ipd_alloc(area, c->ic_descr->id_ikey_size);
662 static struct iam_operations iam_lfix_ops = {
663 .id_root_ptr = iam_lfix_root_ptr,
664 .id_node_read = iam_node_read,
665 .id_node_init = iam_lfix_node_init,
666 .id_node_check = iam_lfix_node_check,
667 .id_node_load = iam_lfix_node_load,
668 .id_ikeycmp = iam_lfix_ikeycmp,
669 .id_root_inc = iam_lfix_root_inc,
670 .id_ipd_alloc = iam_lfix_ipd_alloc,
671 .id_ipd_free = iam_ipd_free,
675 static int iam_lfix_guess(struct iam_container *c)
678 struct buffer_head *bh;
679 const struct iam_lfix_root *root;
681 assert_corr(c->ic_object != NULL);
683 result = iam_node_read(c, iam_lfix_root_ptr(c), NULL, &bh);
685 root = (void *)bh->b_data;
686 if (le64_to_cpu(root->ilr_magic) == IAM_LFIX_ROOT_MAGIC) {
687 struct iam_descr *descr;
690 descr->id_key_size = le16_to_cpu(root->ilr_keysize);
691 descr->id_ikey_size = le16_to_cpu(root->ilr_keysize);
692 descr->id_rec_size = le16_to_cpu(root->ilr_recsize);
693 descr->id_ptr_size = le16_to_cpu(root->ilr_ptrsize);
694 descr->id_root_gap = sizeof(struct iam_lfix_root);
695 descr->id_node_gap = 0;
696 descr->id_ops = &iam_lfix_ops;
697 descr->id_leaf_ops = &iam_lfix_leaf_ops;
708 static struct iam_format iam_lfix_format = {
709 .if_guess = iam_lfix_guess
712 void iam_lfix_format_init(void)
714 iam_format_register(&iam_lfix_format);
725 #define LFIX_ROOT_RECNO \
726 ((4096 - sizeof(struct iam_lfix_root)) / (KEYSIZE + PTRSIZE))
728 #define LFIX_INDEX_RECNO (4096 / (KEYSIZE + PTRSIZE))
730 #define LFIX_LEAF_RECNO \
731 ((4096 - sizeof(struct iam_leaf_head)) / (KEYSIZE + RECSIZE))
734 struct iam_lfix_root lr_root;
738 } lr_entry[LFIX_ROOT_RECNO];
742 struct dx_countlimit li_cl;
743 char li_padding[KEYSIZE + PTRSIZE - sizeof(struct dx_countlimit)];
747 } li_entry[LFIX_INDEX_RECNO - 1];
751 struct iam_leaf_head ll_head;
755 } ll_entry[LFIX_LEAF_RECNO];
758 #define STORE_UNALIGNED(val, dst) \
760 typeof(val) __val = (val); \
761 CLASSERT(sizeof(val) == sizeof(*(dst))); \
762 memcpy(dst, &__val, sizeof(*(dst))); \
765 static void lfix_root(void *buf,
766 int blocksize, int keysize, int ptrsize, int recsize)
768 struct iam_lfix_root *root;
769 struct dx_countlimit *limit;
773 *root = (typeof(*root)) {
774 .ilr_magic = cpu_to_le64(IAM_LFIX_ROOT_MAGIC),
775 .ilr_keysize = cpu_to_le16(keysize),
776 .ilr_recsize = cpu_to_le16(recsize),
777 .ilr_ptrsize = cpu_to_le16(ptrsize),
778 .ilr_indirect_levels = 0
781 limit = (void *)(root + 1);
782 *limit = (typeof(*limit)){
784 * limit itself + one pointer to the leaf.
786 .count = cpu_to_le16(2),
787 .limit = iam_root_limit(sizeof(struct iam_lfix_root),
788 blocksize, keysize + ptrsize)
791 /* To guarantee that the padding "keysize + ptrsize"
792 * covers the "dx_countlimit" and the "idle_blocks". */
793 LASSERT((keysize + ptrsize) >=
794 (sizeof(struct dx_countlimit) + sizeof(__u32)));
796 entry = (void *)(limit + 1);
797 /* Put "idle_blocks" just after the limit. There was padding after
798 * the limit, the "idle_blocks" re-uses part of the padding, so no
799 * compatibility issues with old layout.
806 entry = (void *)(root + 1) + keysize + ptrsize;
809 * Entry format is <key> followed by <ptr>. In the minimal tree
810 * consisting of a root and single node, <key> is a minimal possible
813 * XXX: this key is hard-coded to be a sequence of 0's.
816 memset(entry, 0, keysize);
818 /* now @entry points to <ptr> */
820 STORE_UNALIGNED(cpu_to_le32(1), (u_int32_t *)entry);
822 STORE_UNALIGNED(cpu_to_le64(1), (u_int64_t *)entry);
825 static void lfix_leaf(void *buf,
826 int blocksize, int keysize, int ptrsize, int recsize)
828 struct iam_leaf_head *head;
833 *head = (struct iam_leaf_head) {
834 .ill_magic = cpu_to_le16(IAM_LEAF_HEADER_MAGIC),
836 * Leaf contains an entry with the smallest possible key
837 * (created by zeroing).
839 .ill_count = cpu_to_le16(1),
842 entry = (void *)(head + 1);
843 memset(entry, 0, keysize + recsize);
846 int iam_lfix_create(struct inode *obj,
847 int keysize, int ptrsize, int recsize, handle_t *handle)
849 struct buffer_head *root_node;
850 struct buffer_head *leaf_node;
851 struct super_block *sb;
857 assert_corr(obj->i_size == 0);
860 bsize = sb->s_blocksize;
861 root_node = osd_ldiskfs_append(handle, obj, &blknr);
862 if (IS_ERR(root_node))
863 GOTO(out, result = PTR_ERR(root_node));
865 leaf_node = osd_ldiskfs_append(handle, obj, &blknr);
866 if (IS_ERR(leaf_node))
867 GOTO(out_root, result = PTR_ERR(leaf_node));
869 lfix_root(root_node->b_data, bsize, keysize, ptrsize, recsize);
870 lfix_leaf(leaf_node->b_data, bsize, keysize, ptrsize, recsize);
871 ldiskfs_mark_inode_dirty(handle, obj);
872 result = ldiskfs_handle_dirty_metadata(handle, NULL, root_node);
874 result = ldiskfs_handle_dirty_metadata(handle, NULL, leaf_node);
876 ldiskfs_std_error(sb, result);
880 GOTO(out_root, result);