lustre/osd-ldiskfs/osd_iam_lvar.c

   1 /*
   2  * GPL HEADER START
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   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.
   9  *
  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).
  15  *
  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
  19  *
  20  * GPL HEADER END
  21  */
  22 /*
  23  * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
  24  * Use is subject to license terms.
  25  *
  26  * Copyright (c) 2012, 2015, Intel Corporation.
  27  */
  28 /*
  29  * This file is part of Lustre, http://www.lustre.org/
  30  * Lustre is a trademark of Sun Microsystems, Inc.
  31  *
  32  * iam_lvar.c
  33  *
  34  * implementation of iam format for fixed size records, variable sized keys.
  35  *
  36  * Author: Nikita Danilov <nikita@clusterfs.com>
  37  */
  38
  39 #include <linux/types.h>
  40 #include "osd_internal.h"
  41
  42 /*
  43  * Leaf operations.
  44  */
  45
  46 enum {
  47         IAM_LVAR_LEAF_MAGIC = 0x1973 /* This is duplicated in
  48                                       * lustre/utils/create_iam.c */
  49 };
  50
  51 /* This is duplicated in lustre/utils/create_iam.c */
  52 struct lvar_leaf_header {
  53         __le16 vlh_magic; /* magic number IAM_LVAR_LEAF_MAGIC */
  54         __le16 vlh_used;  /* used bytes, including header */
  55 };
  56
  57 /*
  58  * Format of leaf entry:
  59  *
  60  * __le16 keysize
  61  *     u8 key[keysize]
  62  *     u8 record[rec_size]
  63  *
  64  * Entries are ordered in key order.
  65  */
  66
  67 /* This is duplicated in lustre/utils/create_iam.c */
  68 typedef __u32 lvar_hash_t;
  69
  70 /* This is duplicated in lustre/utils/create_iam.c */
  71 struct lvar_leaf_entry {
  72         __le32 vle_hash;
  73         __le16 vle_keysize;
  74         u8     vle_key[0];
  75 };
  76
  77 #define PDIFF(ptr0, ptr1) (((char *)(ptr0)) - ((char *)(ptr1)))
  78
  79
  80 static inline int blocksize(const struct iam_leaf *leaf)
  81 {
  82         return iam_leaf_container(leaf)->ic_object->i_sb->s_blocksize;
  83 }
  84
  85 static inline const char *kchar(const struct iam_key *key)
  86 {
  87         return (void *)key;
  88 }
  89
  90 static inline struct iam_lentry *lvar_lentry(const struct lvar_leaf_entry *ent)
  91 {
  92         return (struct iam_lentry *)ent;
  93 }
  94
  95 static inline struct lvar_leaf_entry *lentry_lvar(const struct iam_lentry *lent)
  96 {
  97         return (struct lvar_leaf_entry *)lent;
  98 }
  99
 100
 101 static inline int e_keysize(const struct lvar_leaf_entry *ent)
 102 {
 103         return le16_to_cpu(ent->vle_keysize);
 104 }
 105
 106 /* This is duplicated in lustre/utils/create_iam.c */
 107 enum {
 108         LVAR_PAD   = 4,
 109         LVAR_ROUND = LVAR_PAD - 1
 110 };
 111
 112 static inline int getsize(const struct iam_leaf *leaf, int namelen, int recsize)
 113 {
 114         CLASSERT(!(LVAR_PAD & (LVAR_PAD - 1)));
 115
 116         return (offsetof(struct lvar_leaf_entry, vle_key) +
 117                 namelen + recsize + LVAR_ROUND) & ~LVAR_ROUND;
 118 }
 119
 120 static inline int rec_size(const struct iam_rec *rec)
 121 {
 122         return *(const char *)rec;
 123 }
 124
 125 static inline struct iam_rec *e_rec(const struct lvar_leaf_entry *ent)
 126 {
 127         return ((void *)ent) +
 128                 offsetof(struct lvar_leaf_entry, vle_key) + e_keysize(ent);
 129 }
 130
 131 static inline int e_size(const struct iam_leaf *leaf,
 132                          const struct lvar_leaf_entry *ent)
 133 {
 134         return getsize(leaf, e_keysize(ent), rec_size(e_rec(ent)));
 135 }
 136
 137 static inline char *e_char(const struct lvar_leaf_entry *ent)
 138 {
 139         return (char *)&ent->vle_key;
 140 }
 141
 142 static inline struct iam_key *e_key(const struct lvar_leaf_entry *ent)
 143 {
 144         return (struct iam_key *)e_char(ent);
 145 }
 146
 147 static inline lvar_hash_t e_hash(const struct lvar_leaf_entry *ent)
 148 {
 149         return le32_to_cpu(ent->vle_hash);
 150 }
 151
 152 static void e_print(const struct lvar_leaf_entry *ent)
 153 {
 154         printk("        %p %8.8x \"%*.*s\"\n", ent, e_hash(ent),
 155                e_keysize(ent), e_keysize(ent), e_char(ent));
 156 }
 157
 158 static inline struct lvar_leaf_entry *e_next(const struct iam_leaf *leaf,
 159                                              const struct lvar_leaf_entry *ent)
 160 {
 161         return ((void *)ent) + e_size(leaf, ent);
 162 }
 163
 164 #define LVAR_HASH_SANDWICH  (0)
 165 #define LVAR_HASH_TEA       (1)
 166 #define LVAR_HASH_R5        (0)
 167 #define LVAR_HASH_PREFIX    (0)
 168
 169 static __u32 hash_build0(const char *name, int namelen)
 170 {
 171         __u32 result;
 172
 173         if (namelen == 0)
 174                 return 0;
 175         if (strncmp(name, ".", 1) == 0 && namelen == 1)
 176                 return 1;
 177         if (strncmp(name, "..", 2) == 0 && namelen == 2)
 178                 return 2;
 179
 180         if (LVAR_HASH_PREFIX) {
 181                 result = 0;
 182                 strncpy((void *)&result,
 183                         name, min(namelen, (int)sizeof result));
 184         } else {
 185                 struct ldiskfs_dx_hash_info hinfo;
 186
 187                 hinfo.hash_version = LDISKFS_DX_HASH_TEA;
 188                 hinfo.seed = NULL;
 189                 ldiskfsfs_dirhash(name, namelen, &hinfo);
 190                 result = hinfo.hash;
 191                 if (LVAR_HASH_SANDWICH) {
 192                         __u32 result2;
 193
 194                         hinfo.hash_version = LDISKFS_DX_HASH_TEA;
 195                         hinfo.seed = NULL;
 196                         ldiskfsfs_dirhash(name, namelen, &hinfo);
 197                         result2 = hinfo.hash;
 198                         result = (0xfc000000 & result2) | (0x03ffffff & result);
 199                 }
 200         }
 201         return result;
 202 }
 203
 204 enum {
 205         HASH_GRAY_AREA = 1024,
 206         HASH_MAX_SIZE  = 0x7fffffffUL
 207 };
 208
 209 static __u32 hash_build(const char *name, int namelen)
 210 {
 211         __u32 hash;
 212
 213         hash = (hash_build0(name, namelen) << 1) & HASH_MAX_SIZE;
 214         if (hash > HASH_MAX_SIZE - HASH_GRAY_AREA)
 215                 hash &= HASH_GRAY_AREA - 1;
 216         return hash;
 217 }
 218
 219 static inline lvar_hash_t get_hash(const struct iam_container *bag,
 220                                    const char *name, int namelen)
 221 {
 222         return hash_build(name, namelen);
 223 }
 224
 225 static inline int e_eq(const struct lvar_leaf_entry *ent,
 226                        const char *name, int namelen)
 227 {
 228         return namelen == e_keysize(ent) && !memcmp(e_char(ent), name, namelen);
 229 }
 230
 231 static inline int e_cmp(const struct iam_leaf *leaf,
 232                         const struct lvar_leaf_entry *ent, lvar_hash_t hash)
 233 {
 234         lvar_hash_t ehash;
 235
 236         ehash = e_hash(ent);
 237         return ehash == hash ? 0 : (ehash < hash ? -1 : +1);
 238 }
 239
 240 static struct lvar_leaf_header *n_head(const struct iam_leaf *l)
 241 {
 242         return (struct lvar_leaf_header *)l->il_bh->b_data;
 243 }
 244
 245 static int h_used(const struct lvar_leaf_header *hdr)
 246 {
 247         return le16_to_cpu(hdr->vlh_used);
 248 }
 249
 250 static void h_used_adj(const struct iam_leaf *leaf,
 251                        struct lvar_leaf_header *hdr, int adj)
 252 {
 253         int used;
 254
 255         used = h_used(hdr) + adj;
 256         assert_corr(sizeof *hdr <= used && used <= blocksize(leaf));
 257         hdr->vlh_used = cpu_to_le16(used);
 258 }
 259
 260 static struct lvar_leaf_entry *n_start(const struct iam_leaf *leaf)
 261 {
 262         return (void *)leaf->il_bh->b_data + sizeof(struct lvar_leaf_header);
 263 }
 264
 265 static struct lvar_leaf_entry *n_end(const struct iam_leaf *l)
 266 {
 267         return (void *)l->il_bh->b_data + h_used(n_head(l));
 268 }
 269
 270 static struct lvar_leaf_entry *n_cur(const struct iam_leaf *l)
 271 {
 272         return lentry_lvar(l->il_at);
 273 }
 274
 275 void n_print(const struct iam_leaf *l)
 276 {
 277         struct lvar_leaf_entry *scan;
 278
 279         printk(KERN_EMERG "used: %d\n", h_used(n_head(l)));
 280         for (scan = n_start(l); scan < n_end(l); scan = e_next(l, scan))
 281                 e_print(scan);
 282 }
 283
 284 #if LDISKFS_CORRECTNESS_ON
 285 static int n_at_rec(const struct iam_leaf *folio)
 286 {
 287         return
 288                 n_start(folio) <= lentry_lvar(folio->il_at) &&
 289                 lentry_lvar(folio->il_at) < n_end(folio);
 290 }
 291
 292 #if LDISKFS_INVARIANT_ON
 293 static int n_invariant(const struct iam_leaf *leaf)
 294 {
 295         struct iam_path        *path;
 296         struct lvar_leaf_entry *scan;
 297         struct lvar_leaf_entry *end;
 298         lvar_hash_t             hash;
 299         lvar_hash_t             nexthash;
 300         lvar_hash_t             starthash;
 301
 302         end  = n_end(leaf);
 303         hash = 0;
 304         path = leaf->il_path;
 305
 306         if (h_used(n_head(leaf)) > blocksize(leaf))
 307                 return 0;
 308
 309         /*
 310          * Delimiting key in the parent index node. Clear least bit to account
 311          * for hash collision marker.
 312          */
 313         starthash = *(lvar_hash_t *)iam_ikey_at(path, path->ip_frame->at) & ~1;
 314         for (scan = n_start(leaf); scan < end; scan = e_next(leaf, scan)) {
 315                 nexthash = e_hash(scan);
 316                 if (nexthash != get_hash(iam_leaf_container(leaf),
 317                                          e_char(scan), e_keysize(scan))) {
 318                         BREAKPOINT();
 319                         return 0;
 320                 }
 321                 if (0 && nexthash < starthash) {
 322                         /*
 323                          * Unfortunately this useful invariant cannot be
 324                          * reliably checked as parent node is nor necessarily
 325                          * locked.
 326                          */
 327                         n_print(leaf);
 328                         printk("%#x < %#x\n", nexthash, starthash);
 329                         dump_stack();
 330                         return 0;
 331                 }
 332                 if (nexthash < hash) {
 333                         BREAKPOINT();
 334                         return 0;
 335                 }
 336                 hash = nexthash;
 337         }
 338         if (scan != end) {
 339                 BREAKPOINT();
 340                 return 0;
 341         }
 342         return 1;
 343 }
 344 /* LDISKFS_INVARIANT_ON */
 345 #endif
 346
 347 /* LDISKFS_CORRECTNESS_ON */
 348 #endif
 349
 350 static struct iam_ikey *lvar_ikey(const struct iam_leaf *l,
 351                                   struct iam_ikey *key)
 352 {
 353         lvar_hash_t *hash;
 354
 355         assert_corr(n_at_rec(l));
 356
 357         hash = (void *)key;
 358         *hash = e_hash(n_cur(l));
 359         return key;
 360 }
 361
 362 static struct iam_key *lvar_key(const struct iam_leaf *l)
 363 {
 364         return e_key(n_cur(l));
 365 }
 366
 367 static int lvar_key_size(const struct iam_leaf *l)
 368 {
 369         return e_keysize(n_cur(l));
 370 }
 371
 372 static void lvar_start(struct iam_leaf *l)
 373 {
 374         l->il_at = lvar_lentry(n_start(l));
 375 }
 376
 377 static int lvar_init(struct iam_leaf *l)
 378 {
 379         int result;
 380         int used;
 381         struct lvar_leaf_header *head;
 382
 383         assert_corr(l->il_bh != NULL);
 384
 385         head = n_head(l);
 386         used = h_used(head);
 387         if (le16_to_cpu(head->vlh_magic) == IAM_LVAR_LEAF_MAGIC &&
 388             used <= blocksize(l)) {
 389                 l->il_at = l->il_entries = lvar_lentry(n_start(l));
 390                 result = 0;
 391         } else {
 392                 struct inode *obj;
 393
 394                 obj = iam_leaf_container(l)->ic_object;
 395                 CERROR("Wrong magic in node %llu (#%lu): %#x != %#x or "
 396                        "wrong used: %d\n",
 397                        (unsigned long long)l->il_bh->b_blocknr, obj->i_ino,
 398                        le16_to_cpu(head->vlh_magic), IAM_LVAR_LEAF_MAGIC,
 399                        used);
 400                 result = -EIO;
 401         }
 402         return result;
 403 }
 404
 405 static void lvar_fini(struct iam_leaf *l)
 406 {
 407         l->il_entries = l->il_at = NULL;
 408 }
 409
 410 static struct iam_rec *lvar_rec(const struct iam_leaf *l)
 411 {
 412         assert_corr(n_at_rec(l));
 413         return e_rec(n_cur(l));
 414 }
 415
 416 static void lvar_next(struct iam_leaf *l)
 417 {
 418         assert_corr(n_at_rec(l));
 419         assert_corr(iam_leaf_is_locked(l));
 420         l->il_at = lvar_lentry(e_next(l, n_cur(l)));
 421 }
 422
 423 static int lvar_lookup(struct iam_leaf *leaf, const struct iam_key *k)
 424 {
 425         struct lvar_leaf_entry *found;
 426         struct lvar_leaf_entry *scan;
 427         struct lvar_leaf_entry *end;
 428         int                     result;
 429         const char             *name;
 430         int                     namelen;
 431         int                     found_equal;
 432         lvar_hash_t             hash;
 433         int                     last;
 434
 435         assert_inv(n_invariant(leaf));
 436         end = n_end(leaf);
 437
 438         name = kchar(k);
 439         namelen = strlen(name);
 440         hash = get_hash(iam_leaf_container(leaf), name, namelen);
 441         found = NULL;
 442         found_equal = 0;
 443         last = 1;
 444
 445         for (scan = n_start(leaf); scan < end; scan = e_next(leaf, scan)) {
 446                 lvar_hash_t scan_hash;
 447
 448                 scan_hash = e_hash(scan);
 449                 if (scan_hash < hash)
 450                         found = scan;
 451                 else if (scan_hash == hash) {
 452                         if (e_eq(scan, name, namelen)) {
 453                                 /*
 454                                  * perfect match
 455                                  */
 456                                 leaf->il_at = lvar_lentry(scan);
 457                                 return IAM_LOOKUP_EXACT;
 458                         } else if (!found_equal) {
 459                                         found = scan;
 460                                         found_equal = 1;
 461                         }
 462                 } else {
 463                         last = 0;
 464                         break;
 465                 }
 466         }
 467         if (found == NULL) {
 468                 /*
 469                  * @k is less than all hashes in the leaf.
 470                  */
 471                 lvar_start(leaf);
 472                 result = IAM_LOOKUP_BEFORE;
 473         } else {
 474                 leaf->il_at = lvar_lentry(found);
 475                 result = IAM_LOOKUP_OK;
 476                 assert_corr(n_at_rec(leaf));
 477         }
 478         if (last)
 479                 result |= IAM_LOOKUP_LAST;
 480         assert_inv(n_invariant(leaf));
 481
 482         return result;
 483 }
 484
 485 static int lvar_ilookup(struct iam_leaf *leaf, const struct iam_ikey *ik)
 486 {
 487         struct lvar_leaf_entry *scan;
 488         struct lvar_leaf_entry *end;
 489         lvar_hash_t             hash;
 490
 491         assert_inv(n_invariant(leaf));
 492         end  = n_end(leaf);
 493         hash = *(const lvar_hash_t *)ik;
 494
 495         lvar_start(leaf);
 496         for (scan = n_start(leaf); scan < end; scan = e_next(leaf, scan)) {
 497                 lvar_hash_t scan_hash;
 498
 499                 scan_hash = e_hash(scan);
 500                 if (scan_hash > hash)
 501                         return scan == n_start(leaf) ?
 502                                 IAM_LOOKUP_BEFORE : IAM_LOOKUP_OK;
 503                 leaf->il_at = lvar_lentry(scan);
 504                 if (scan_hash == hash)
 505                         return IAM_LOOKUP_EXACT;
 506         }
 507         assert_inv(n_invariant(leaf));
 508         /*
 509          * @ik is greater than any key in the node. Return last record in the
 510          * node.
 511          */
 512         return IAM_LOOKUP_OK;
 513 }
 514
 515 static void __lvar_key_set(struct iam_leaf *l, const struct iam_key *k)
 516 {
 517         memcpy(e_key(n_cur(l)), k, e_keysize(n_cur(l)));
 518 }
 519
 520 static void lvar_key_set(struct iam_leaf *l, const struct iam_key *k)
 521 {
 522         assert_corr(n_at_rec(l));
 523         assert_corr(strlen(kchar(k)) == e_keysize(n_cur(l)));
 524         assert_corr(iam_leaf_is_locked(l));
 525         __lvar_key_set(l, k);
 526         assert_inv(n_invariant(l));
 527 }
 528
 529 static int lvar_key_cmp(const struct iam_leaf *l, const struct iam_key *k)
 530 {
 531         lvar_hash_t hash;
 532         const char *name;
 533
 534         name = kchar(k);
 535
 536         hash = get_hash(iam_leaf_container(l), name, strlen(name));
 537         return e_cmp(l, n_cur(l), hash);
 538 }
 539
 540 static int lvar_key_eq(const struct iam_leaf *l, const struct iam_key *k)
 541 {
 542         const char *name;
 543
 544         name = kchar(k);
 545         return e_eq(n_cur(l), name, strlen(name));
 546 }
 547
 548 static void __lvar_rec_set(struct iam_leaf *l, const struct iam_rec *r)
 549 {
 550         memcpy(e_rec(n_cur(l)), r, rec_size(r));
 551 }
 552
 553 static void lvar_rec_set(struct iam_leaf *l, const struct iam_rec *r)
 554 {
 555         assert_corr(n_at_rec(l));
 556         assert_corr(iam_leaf_is_locked(l));
 557         __lvar_rec_set(l, r);
 558         assert_inv(n_invariant(l));
 559 }
 560
 561 static int lvar_rec_eq(const struct iam_leaf *l, const struct iam_rec *r)
 562 {
 563         struct iam_rec *rec = e_rec(n_cur(l));
 564
 565         if (rec_size(rec) != rec_size(r))
 566                 return 0;
 567         return !memcmp(rec, r, rec_size(r));
 568 }
 569
 570 static void lvar_rec_get(const struct iam_leaf *l, struct iam_rec *r)
 571 {
 572         struct iam_rec *rec;
 573
 574         rec = e_rec(n_cur(l));
 575         assert_corr(n_at_rec(l));
 576         assert_corr(iam_leaf_is_locked(l));
 577         memcpy(r, rec, rec_size(rec));
 578         assert_inv(n_invariant(l));
 579 }
 580
 581 static int lvar_can_add(const struct iam_leaf *l,
 582                         const struct iam_key *k, const struct iam_rec *r)
 583 {
 584         assert_corr(iam_leaf_is_locked(l));
 585         return
 586                 h_used(n_head(l)) +
 587                 getsize(l, strlen(kchar(k)), rec_size(r)) <= blocksize(l);
 588 }
 589
 590 static int lvar_at_end(const struct iam_leaf *folio)
 591 {
 592         assert_corr(iam_leaf_is_locked(folio));
 593         return n_cur(folio) == n_end(folio);
 594 }
 595
 596 static void lvar_rec_add(struct iam_leaf *leaf,
 597                          const struct iam_key *k, const struct iam_rec *r)
 598 {
 599         const char *key;
 600         int   ksize;
 601         int   shift;
 602         void *end;
 603         void *start;
 604         ptrdiff_t diff;
 605
 606         assert_corr(lvar_can_add(leaf, k, r));
 607         assert_inv(n_invariant(leaf));
 608         assert_corr(iam_leaf_is_locked(leaf));
 609
 610         key   = kchar(k);
 611         ksize = strlen(key);
 612         shift = getsize(leaf, ksize, rec_size(r));
 613
 614         if (!lvar_at_end(leaf)) {
 615                 assert_corr(n_cur(leaf) < n_end(leaf));
 616                 end = n_end(leaf);
 617                 if (lvar_key_cmp(leaf, k) <= 0)
 618                         lvar_next(leaf);
 619                 else
 620                         /*
 621                          * Another exceptional case: insertion with the key
 622                          * less than least key in the leaf.
 623                          */
 624                         assert_corr(leaf->il_at == leaf->il_entries);
 625
 626                 start = leaf->il_at;
 627                 diff  = PDIFF(end, start);
 628                 assert_corr(diff >= 0);
 629                 memmove(start + shift, start, diff);
 630         }
 631         h_used_adj(leaf, n_head(leaf), shift);
 632         n_cur(leaf)->vle_keysize = cpu_to_le16(ksize);
 633         n_cur(leaf)->vle_hash = cpu_to_le32(get_hash(iam_leaf_container(leaf),
 634                                                      key, ksize));
 635         __lvar_key_set(leaf, k);
 636         __lvar_rec_set(leaf, r);
 637         assert_corr(n_at_rec(leaf));
 638         assert_inv(n_invariant(leaf));
 639 }
 640
 641 static void lvar_rec_del(struct iam_leaf *leaf, int shift)
 642 {
 643         void *next;
 644         void *end;
 645         int nob;
 646
 647         assert_corr(n_at_rec(leaf));
 648         assert_inv(n_invariant(leaf));
 649         assert_corr(iam_leaf_is_locked(leaf));
 650
 651         end  = n_end(leaf);
 652         next = e_next(leaf, n_cur(leaf));
 653         nob  = e_size(leaf, n_cur(leaf));
 654         memmove(leaf->il_at, next, end - next);
 655         h_used_adj(leaf, n_head(leaf), -nob);
 656         assert_inv(n_invariant(leaf));
 657 }
 658
 659 static void lvar_init_new(struct iam_container *c, struct buffer_head *bh)
 660 {
 661         struct lvar_leaf_header *hdr;
 662
 663         hdr = (struct lvar_leaf_header *)bh->b_data;
 664         hdr->vlh_magic = cpu_to_le16(IAM_LVAR_LEAF_MAGIC);
 665         hdr->vlh_used  = sizeof *hdr;
 666 }
 667
 668 static struct lvar_leaf_entry *find_pivot(const struct iam_leaf *leaf,
 669                                           struct lvar_leaf_entry **prev)
 670 {
 671         void *scan;
 672         void *start;
 673         int threshold;
 674
 675         *prev = NULL;
 676         threshold = blocksize(leaf) / 2;
 677         for (scan = start = n_start(leaf); scan - start <= threshold;
 678              *prev = scan, scan = e_next(leaf, scan)) {
 679                 ;
 680         }
 681         return scan;
 682 }
 683
 684 static void lvar_split(struct iam_leaf *leaf, struct buffer_head **bh,
 685                        iam_ptr_t new_blknr)
 686 {
 687         struct lvar_leaf_entry  *first_to_move;
 688         struct lvar_leaf_entry  *last_to_stay;
 689         struct iam_path         *path;
 690         struct lvar_leaf_header *hdr;
 691         struct buffer_head      *new_leaf;
 692
 693         ptrdiff_t   tomove;
 694         lvar_hash_t hash;
 695
 696         assert_inv(n_invariant(leaf));
 697         assert_corr(iam_leaf_is_locked(leaf));
 698
 699         new_leaf = *bh;
 700         path = iam_leaf_path(leaf);
 701
 702         hdr = (void *)new_leaf->b_data;
 703
 704         first_to_move = find_pivot(leaf, &last_to_stay);
 705         assert_corr(last_to_stay != NULL);
 706         assert_corr(e_next(leaf, last_to_stay) == first_to_move);
 707
 708         hash = e_hash(first_to_move);
 709         if (hash == e_hash(last_to_stay))
 710                 /*
 711                  * Duplicate hash.
 712                  */
 713                 hash |= 1;
 714
 715         tomove = PDIFF(n_end(leaf), first_to_move);
 716         memmove(hdr + 1, first_to_move, tomove);
 717
 718         h_used_adj(leaf, hdr, tomove);
 719         h_used_adj(leaf, n_head(leaf), -tomove);
 720
 721         assert_corr(n_end(leaf) == first_to_move);
 722
 723         if (n_cur(leaf) >= first_to_move) {
 724                 /*
 725                  * insertion point moves into new leaf.
 726                  */
 727                 ptrdiff_t shift;
 728                 int result;
 729
 730                 shift = PDIFF(leaf->il_at, first_to_move);
 731                 *bh = leaf->il_bh;
 732                 leaf->il_bh = new_leaf;
 733                 leaf->il_curidx = new_blknr;
 734
 735                 assert_corr(iam_leaf_is_locked(leaf));
 736                 result = lvar_init(leaf);
 737                 /*
 738                  * init cannot fail, as node was just initialized.
 739                  */
 740                 assert_corr(result == 0);
 741                 leaf->il_at = ((void *)leaf->il_at) + shift;
 742         }
 743         /*
 744          * Insert pointer to the new node (together with the least key in
 745          * the node) into index node.
 746          */
 747         iam_insert_key_lock(path, path->ip_frame, (struct iam_ikey *)&hash,
 748                             new_blknr);
 749         assert_corr(n_cur(leaf) < n_end(leaf));
 750         assert_inv(n_invariant(leaf));
 751 }
 752
 753 static int lvar_leaf_empty(struct iam_leaf *leaf)
 754 {
 755         return h_used(n_head(leaf)) == sizeof(struct lvar_leaf_header);
 756 }
 757
 758 static struct iam_leaf_operations lvar_leaf_ops = {
 759         .init           = lvar_init,
 760         .init_new       = lvar_init_new,
 761         .fini           = lvar_fini,
 762         .start          = lvar_start,
 763         .next           = lvar_next,
 764         .key            = lvar_key,
 765         .ikey           = lvar_ikey,
 766         .rec            = lvar_rec,
 767         .key_set        = lvar_key_set,
 768         .key_cmp        = lvar_key_cmp,
 769         .key_eq         = lvar_key_eq,
 770         .key_size       = lvar_key_size,
 771         .rec_set        = lvar_rec_set,
 772         .rec_eq         = lvar_rec_eq,
 773         .rec_get        = lvar_rec_get,
 774         .lookup         = lvar_lookup,
 775         .ilookup        = lvar_ilookup,
 776         .at_end         = lvar_at_end,
 777         .rec_add        = lvar_rec_add,
 778         .rec_del        = lvar_rec_del,
 779         .can_add        = lvar_can_add,
 780         .split          = lvar_split,
 781         .leaf_empty     = lvar_leaf_empty,
 782 };
 783
 784 /*
 785  * Index operations.
 786  */
 787
 788 enum {
 789         /* This is duplicated in lustre/utils/create_iam.c */
 790         /* egrep -i '^o?x?[olabcdef]*$' /usr/share/dict/words */
 791         IAM_LVAR_ROOT_MAGIC = 0xb01dface
 792 };
 793
 794 /* This is duplicated in lustre/utils/create_iam.c */
 795 struct lvar_root {
 796         __le32 vr_magic;
 797         __le16 vr_recsize;
 798         __le16 vr_ptrsize;
 799         u8     vr_indirect_levels;
 800         u8     vr_padding0;
 801         __le16 vr_padding1;
 802 };
 803
 804 static __u32 lvar_root_ptr(struct iam_container *c)
 805 {
 806         return 0;
 807 }
 808
 809 static int lvar_node_init(struct iam_container *c, struct buffer_head *bh,
 810                           int root)
 811 {
 812         return 0;
 813 }
 814
 815 static struct iam_entry *lvar_root_inc(struct iam_container *c,
 816                                        struct iam_path *path,
 817                                        struct iam_frame *frame)
 818 {
 819         struct lvar_root *root;
 820         struct iam_entry *entries;
 821
 822         assert_corr(iam_frame_is_locked(path, frame));
 823         entries = frame->entries;
 824
 825         dx_set_count(entries, 2);
 826         assert_corr(dx_get_limit(entries) == dx_root_limit(path));
 827
 828         root = (void *)frame->bh->b_data;
 829         assert_corr(le64_to_cpu(root->vr_magic) == IAM_LVAR_ROOT_MAGIC);
 830         root->vr_indirect_levels ++;
 831         frame->at = entries = iam_entry_shift(path, entries, 1);
 832         memset(iam_ikey_at(path, entries), 0,
 833                iam_path_descr(path)->id_ikey_size);
 834         return entries;
 835 }
 836
 837 static int lvar_node_check(struct iam_path *path, struct iam_frame *frame)
 838 {
 839         unsigned count;
 840         unsigned limit;
 841         unsigned limit_correct;
 842         struct iam_entry *entries;
 843
 844         entries = dx_node_get_entries(path, frame);
 845
 846         if (frame == path->ip_frames) {
 847                 struct lvar_root *root;
 848
 849                 root = (void *)frame->bh->b_data;
 850                 if (le32_to_cpu(root->vr_magic) != IAM_LVAR_ROOT_MAGIC)
 851                         return -EIO;
 852                 limit_correct = dx_root_limit(path);
 853         } else
 854                 limit_correct = dx_node_limit(path);
 855         count = dx_get_count(entries);
 856         limit = dx_get_limit(entries);
 857         if (count > limit)
 858                 return -EIO;
 859         if (limit != limit_correct)
 860                 return -EIO;
 861         return 0;
 862 }
 863
 864 static int lvar_node_load(struct iam_path *path, struct iam_frame *frame)
 865 {
 866         struct iam_entry *entries;
 867         void *data;
 868         entries = dx_node_get_entries(path, frame);
 869
 870         data = frame->bh->b_data;
 871
 872         if (frame == path->ip_frames) {
 873                 struct lvar_root *root;
 874                 const char *name;
 875
 876                 root = data;
 877                 name = kchar(path->ip_key_target);
 878                 path->ip_indirect = root->vr_indirect_levels;
 879                 if (path->ip_ikey_target == NULL) {
 880                         path->ip_ikey_target = iam_path_ikey(path, 4);
 881                         *(lvar_hash_t *)path->ip_ikey_target =
 882                                 get_hash(path->ip_container, name,
 883                                          strlen(name));
 884                 }
 885         }
 886         frame->entries = frame->at = entries;
 887         return 0;
 888 }
 889
 890 static int lvar_ikeycmp(const struct iam_container *c,
 891                         const struct iam_ikey *k1, const struct iam_ikey *k2)
 892 {
 893         lvar_hash_t p1 = le32_to_cpu(*(lvar_hash_t *)k1);
 894         lvar_hash_t p2 = le32_to_cpu(*(lvar_hash_t *)k2);
 895
 896         return p1 > p2 ? +1 : (p1 < p2 ? -1 : 0);
 897 }
 898
 899 static struct iam_path_descr *lvar_ipd_alloc(const struct iam_container *c,
 900                                              void *area)
 901 {
 902         return iam_ipd_alloc(area, c->ic_descr->id_ikey_size);
 903 }
 904
 905 static void lvar_root(void *buf,
 906                       int blocksize, int keysize, int ptrsize, int recsize)
 907 {
 908         struct lvar_root *root;
 909         struct dx_countlimit *limit;
 910         void                 *entry;
 911         int isize;
 912
 913         isize = sizeof(lvar_hash_t) + ptrsize;
 914         root = buf;
 915         *root = (typeof(*root)) {
 916                 .vr_magic            = cpu_to_le32(IAM_LVAR_ROOT_MAGIC),
 917                 .vr_recsize          = cpu_to_le16(recsize),
 918                 .vr_ptrsize          = cpu_to_le16(ptrsize),
 919                 .vr_indirect_levels  = 0
 920         };
 921
 922         limit = (void *)(root + 1);
 923         *limit = (typeof(*limit)){
 924                 /*
 925                  * limit itself + one pointer to the leaf.
 926                  */
 927                 .count = cpu_to_le16(2),
 928                 .limit = iam_root_limit(sizeof(struct lvar_root), blocksize,
 929                                         sizeof (lvar_hash_t) + ptrsize)
 930         };
 931
 932         /* To guarantee that the padding "keysize + ptrsize"
 933          * covers the "dx_countlimit" and the "idle_blocks". */
 934         LASSERT((keysize + ptrsize) >=
 935                 (sizeof(struct dx_countlimit) + sizeof(__u32)));
 936
 937         entry = (void *)(limit + 1);
 938         /* Put "idle_blocks" just after the limit. There was padding after
 939          * the limit, the "idle_blocks" re-uses part of the padding, so no
 940          * compatibility issues with old layout.
 941          */
 942         *(__u32 *)entry = 0;
 943
 944         /*
 945          * Skip over @limit.
 946          */
 947         entry = (void *)(root + 1) + isize;
 948
 949         /*
 950          * Entry format is <key> followed by <ptr>. In the minimal tree
 951          * consisting of a root and single node, <key> is a minimal possible
 952          * key.
 953          */
 954         *(lvar_hash_t *)entry = 0;
 955         entry += sizeof(lvar_hash_t);
 956         /* now @entry points to <ptr> */
 957         if (ptrsize == 4)
 958                 *(u_int32_t *)entry = cpu_to_le32(1);
 959         else
 960                 *(u_int64_t *)entry = cpu_to_le64(1);
 961 }
 962
 963 static int lvar_esize(int namelen, int recsize)
 964 {
 965         return (offsetof(struct lvar_leaf_entry, vle_key) +
 966                 namelen + recsize + LVAR_ROUND) & ~LVAR_ROUND;
 967 }
 968
 969 static void lvar_leaf(void *buf,
 970                       int blocksize, int keysize, int ptrsize, int recsize)
 971 {
 972         struct lvar_leaf_header *head;
 973         struct lvar_leaf_entry  *entry;
 974
 975         /* form leaf */
 976         head = buf;
 977         *head = (typeof(*head)) {
 978                 .vlh_magic = cpu_to_le16(IAM_LVAR_LEAF_MAGIC),
 979                 .vlh_used  = cpu_to_le16(sizeof *head + lvar_esize(0, recsize))
 980         };
 981         entry = (void *)(head + 1);
 982         *entry = (typeof(*entry)) {
 983                 .vle_hash    = 0,
 984                 .vle_keysize = 0
 985         };
 986         memset(e_rec(entry), 0, recsize);
 987         *(char *)e_rec(entry) = recsize;
 988 }
 989
 990 int iam_lvar_create(struct inode *obj,
 991                     int keysize, int ptrsize, int recsize, handle_t *handle)
 992 {
 993         struct buffer_head *root_node;
 994         struct buffer_head *leaf_node;
 995         struct super_block *sb;
 996
 997         u32 blknr;
 998         int result = 0;
 999         unsigned long bsize;
1000
1001         assert_corr(obj->i_size == 0);
1002
1003         sb = obj->i_sb;
1004         bsize = sb->s_blocksize;
1005         root_node = osd_ldiskfs_append(handle, obj, &blknr);
1006         if (IS_ERR(root_node))
1007                 GOTO(out, result = PTR_ERR(root_node));
1008
1009         leaf_node = osd_ldiskfs_append(handle, obj, &blknr);
1010         if (IS_ERR(leaf_node))
1011                 GOTO(out_root, result = PTR_ERR(leaf_node));
1012
1013         lvar_root(root_node->b_data, bsize, keysize, ptrsize, recsize);
1014         lvar_leaf(leaf_node->b_data, bsize, keysize, ptrsize, recsize);
1015         ldiskfs_mark_inode_dirty(handle, obj);
1016         result = ldiskfs_handle_dirty_metadata(handle, NULL, root_node);
1017         if (result == 0)
1018                 result = ldiskfs_handle_dirty_metadata(handle, NULL, leaf_node);
1019         if (result != 0)
1020                 ldiskfs_std_error(sb, result);
1021
1022         brelse(leaf_node);
1023
1024         GOTO(out_root, result);
1025
1026 out_root:
1027         brelse(root_node);
1028 out:
1029         return result;
1030 }
1031
1032 static struct iam_operations lvar_ops = {
1033         .id_root_ptr    = lvar_root_ptr,
1034         .id_node_read   = iam_node_read,
1035         .id_node_init   = lvar_node_init,
1036         .id_node_check  = lvar_node_check,
1037         .id_node_load   = lvar_node_load,
1038         .id_ikeycmp     = lvar_ikeycmp,
1039         .id_root_inc    = lvar_root_inc,
1040         .id_ipd_alloc   = lvar_ipd_alloc,
1041         .id_ipd_free    = iam_ipd_free,
1042         .id_name        = "lvar"
1043 };
1044
1045 static int lvar_guess(struct iam_container *c)
1046 {
1047         int result;
1048         struct buffer_head *bh;
1049         const struct lvar_root *root;
1050
1051         assert_corr(c->ic_object != NULL);
1052
1053         result = iam_node_read(c, lvar_root_ptr(c), NULL, &bh);
1054         if (result == 0) {
1055                 root = (void *)bh->b_data;
1056                 if (le32_to_cpu(root->vr_magic) == IAM_LVAR_ROOT_MAGIC) {
1057                         struct iam_descr *descr;
1058
1059                         descr = c->ic_descr;
1060                         descr->id_key_size  = LDISKFS_NAME_LEN;
1061                         descr->id_ikey_size = sizeof (lvar_hash_t);
1062                         descr->id_rec_size  = le16_to_cpu(root->vr_recsize);
1063                         descr->id_ptr_size  = le16_to_cpu(root->vr_ptrsize);
1064                         descr->id_root_gap  = sizeof *root;
1065                         descr->id_node_gap  = 0;
1066                         descr->id_ops       = &lvar_ops;
1067                         descr->id_leaf_ops  = &lvar_leaf_ops;
1068
1069                         c->ic_root_bh = bh;
1070                 } else {
1071                         result = -EBADF;
1072                         brelse(bh);
1073                 }
1074         }
1075         return result;
1076 }
1077
1078 static struct iam_format lvar_format = {
1079         .if_guess = lvar_guess
1080 };
1081
1082 void iam_lvar_format_init(void)
1083 {
1084         iam_format_register(&lvar_format);
1085 }
1086