lustre/osd-ldiskfs/osd_iam_lfix.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  *
  31  * iam_lfix.c
  32  * implementation of iam format for fixed size records.
  33  *
  34  * Author: Wang Di <wangdi@clusterfs.com>
  35  * Author: Nikita Danilov <nikita@clusterfs.com>
  36  */
  37
  38 #include <linux/types.h>
  39 #include "osd_internal.h"
  40
  41 /*
  42  * Leaf operations.
  43  */
  44
  45 enum {
  46         IAM_LEAF_HEADER_MAGIC = 0x1976 /* This is duplicated in
  47                                         * lustre/utils/create_iam.c */
  48 };
  49
  50 /* This is duplicated in lustre/utils/create_iam.c */
  51 struct iam_leaf_head {
  52         __le16 ill_magic;
  53         __le16 ill_count;
  54 };
  55
  56 static inline int iam_lfix_entry_size(const struct iam_leaf *l)
  57 {
  58         return iam_leaf_descr(l)->id_key_size + iam_leaf_descr(l)->id_rec_size;
  59 }
  60
  61 static inline struct iam_lentry *
  62 iam_lfix_shift(const struct iam_leaf *l, struct iam_lentry *entry, int shift)
  63 {
  64         return (void *)entry + shift * iam_lfix_entry_size(l);
  65 }
  66
  67 static inline struct iam_key *iam_leaf_key_at(struct iam_lentry *entry)
  68 {
  69         return (struct iam_key *)entry;
  70 }
  71
  72 static inline int lfix_keycmp(const struct iam_container *c,
  73                               const struct iam_key *k1,
  74                               const struct iam_key *k2)
  75 {
  76         return memcmp(k1, k2, c->ic_descr->id_key_size);
  77 }
  78
  79 static struct iam_leaf_head *iam_get_head(const struct iam_leaf *l)
  80 {
  81         return (struct iam_leaf_head *)l->il_bh->b_data;
  82 }
  83
  84 static struct iam_lentry *iam_entries(const struct buffer_head *bh)
  85 {
  86         return (void *)bh->b_data + sizeof(struct iam_leaf_head);
  87 }
  88
  89 static struct iam_lentry *iam_get_lentries(const struct iam_leaf *l)
  90 {
  91         return iam_entries(l->il_bh);
  92 }
  93
  94 static int leaf_count_limit(const struct iam_leaf *leaf)
  95 {
  96         int free_space;
  97
  98         free_space = iam_leaf_container(leaf)->ic_object->i_sb->s_blocksize;
  99         free_space -= sizeof(struct iam_leaf_head);
 100         return free_space / iam_lfix_entry_size(leaf);
 101 }
 102
 103 static int lentry_count_get(const struct iam_leaf *leaf)
 104 {
 105         return le16_to_cpu(iam_get_head(leaf)->ill_count);
 106 }
 107
 108 static void lentry_count_set(struct iam_leaf *leaf, unsigned count)
 109 {
 110         assert_corr(0 <= count && count <= leaf_count_limit(leaf));
 111         iam_get_head(leaf)->ill_count = cpu_to_le16(count);
 112 }
 113
 114 static struct iam_lentry *iam_lfix_get_end(const struct iam_leaf *l);
 115
 116 #if LDISKFS_CORRECTNESS_ON || LDISKFS_INVARIANT_ON
 117 static int iam_leaf_at_rec(const struct iam_leaf *folio)
 118 {
 119         return iam_get_lentries(folio) <= folio->il_at &&
 120                 folio->il_at < iam_lfix_get_end(folio);
 121 }
 122 #endif
 123
 124 static struct iam_ikey *iam_lfix_ikey(const struct iam_leaf *l,
 125                                       struct iam_ikey *key)
 126 {
 127         void *ie = l->il_at;
 128
 129         assert_corr(iam_leaf_at_rec(l));
 130         return (struct iam_ikey *)ie;
 131 }
 132
 133 static struct iam_key *iam_lfix_key(const struct iam_leaf *l)
 134 {
 135         void *ie = l->il_at;
 136
 137         assert_corr(iam_leaf_at_rec(l));
 138         return (struct iam_key *)ie;
 139 }
 140
 141 static int iam_lfix_key_size(const struct iam_leaf *l)
 142 {
 143         return iam_leaf_descr(l)->id_key_size;
 144 }
 145
 146 static void iam_lfix_start(struct iam_leaf *l)
 147 {
 148         l->il_at = iam_get_lentries(l);
 149 }
 150
 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)
 154 {
 155         ptrdiff_t diff;
 156         int esize;
 157
 158         esize = iam_lfix_entry_size(l);
 159         diff = (void *)e1 - (void *)e2;
 160         assert_corr(diff / esize * esize == diff);
 161         return diff / esize;
 162 }
 163
 164 static int iam_lfix_init(struct iam_leaf *l)
 165 {
 166         int result;
 167         struct iam_leaf_head *ill;
 168         int count;
 169
 170         assert_corr(l->il_bh != NULL);
 171
 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);
 177                 result = 0;
 178         } else {
 179                 struct inode *obj;
 180
 181                 result = -EIO;
 182                 obj = iam_leaf_container(l)->ic_object;
 183                 CERROR(
 184                 "Bad magic in node %llu #%lu: %#x != %#x or bad cnt: %d %d: rc = %d\n",
 185                         (unsigned long long)l->il_bh->b_blocknr, obj->i_ino,
 186                         le16_to_cpu(ill->ill_magic), IAM_LEAF_HEADER_MAGIC,
 187                         count, leaf_count_limit(l), result);
 188         }
 189         return result;
 190 }
 191
 192 static void iam_lfix_fini(struct iam_leaf *l)
 193 {
 194         l->il_entries = l->il_at = NULL;
 195 }
 196
 197 static struct iam_lentry *iam_lfix_get_end(const struct iam_leaf *l)
 198 {
 199         int count = lentry_count_get(l);
 200         struct iam_lentry *ile = iam_lfix_shift(l, l->il_entries, count);
 201
 202         return ile;
 203 }
 204
 205 static struct iam_rec *iam_lfix_rec(const struct iam_leaf *l)
 206 {
 207         void *e = l->il_at;
 208
 209         assert_corr(iam_leaf_at_rec(l));
 210         return e + iam_leaf_descr(l)->id_key_size;
 211 }
 212
 213 static void iam_lfix_next(struct iam_leaf *l)
 214 {
 215         assert_corr(iam_leaf_at_rec(l));
 216         l->il_at = iam_lfix_shift(l, l->il_at, 1);
 217 }
 218
 219 /*
 220  * Bug chasing.
 221  */
 222 int lfix_dump = 0;
 223
 224 static char hdigit(char ch)
 225 {
 226         static const char d[] = "0123456789abcdef";
 227
 228         return d[ch & 0xf];
 229 }
 230
 231 static char *hex(char ch, char *area)
 232 {
 233         area[0] = hdigit(ch >> 4);
 234         area[1] = hdigit(ch);
 235         area[2] = 0;
 236         return area;
 237 }
 238
 239 static void l_print(struct iam_leaf *leaf, struct iam_lentry *entry)
 240 {
 241         int i;
 242         char *area;
 243         char h[3];
 244
 245         area = (char *)entry;
 246         printk(KERN_EMERG "[");
 247         for (i = iam_lfix_key_size(leaf); i > 0; --i, ++area)
 248                 printk("%s", hex(*area, h));
 249         printk("]-(");
 250         for (i = iam_leaf_descr(leaf)->id_rec_size; i > 0; --i, ++area)
 251                 printk("%s", hex(*area, h));
 252         printk(")\n");
 253 }
 254
 255 static void lfix_print(struct iam_leaf *leaf)
 256 {
 257         struct iam_lentry *entry;
 258         int count;
 259         int i;
 260
 261         entry = leaf->il_entries;
 262         count = lentry_count_get(leaf);
 263         printk(KERN_EMERG "lfix: %p %p %d\n", leaf, leaf->il_at, count);
 264         for (i = 0; i < count; ++i, entry = iam_lfix_shift(leaf, entry, 1))
 265                 l_print(leaf, entry);
 266 }
 267
 268 static int iam_lfix_lookup(struct iam_leaf *l, const struct iam_key *k)
 269 {
 270         struct iam_lentry *p, *q, *m, *t;
 271         struct iam_container *c;
 272         int count;
 273         int result;
 274
 275         count = lentry_count_get(l);
 276         if (count == 0)
 277                 return IAM_LOOKUP_EMPTY;
 278
 279         result = IAM_LOOKUP_OK;
 280         c = iam_leaf_container(l);
 281
 282         p = l->il_entries;
 283         q = iam_lfix_shift(l, p, count - 1);
 284         if (lfix_keycmp(c, k, iam_leaf_key_at(p)) < 0) {
 285                 /*
 286                  * @k is less than the least key in the leaf
 287                  */
 288                 l->il_at = p;
 289                 result = IAM_LOOKUP_BEFORE;
 290         } else if (lfix_keycmp(c, iam_leaf_key_at(q), k) <= 0) {
 291                 l->il_at = q;
 292         } else {
 293                 /*
 294                  * EWD1293
 295                  */
 296                 while (iam_lfix_shift(l, p, 1) != q) {
 297                         m = iam_lfix_shift(l, p, iam_lfix_diff(l, q, p) / 2);
 298                         assert_corr(p < m && m < q);
 299                         if (lfix_keycmp(c, iam_leaf_key_at(m), k) <= 0)
 300                                 p = m;
 301                         else
 302                                 q = m;
 303                 }
 304                 assert_corr(lfix_keycmp(c, iam_leaf_key_at(p), k) <= 0 &&
 305                             lfix_keycmp(c, k, iam_leaf_key_at(q)) < 0);
 306                 /*
 307                  * skip over records with duplicate keys.
 308                  */
 309                 while (p > l->il_entries) {
 310                         t = iam_lfix_shift(l, p, -1);
 311                         if (lfix_keycmp(c, iam_leaf_key_at(t), k) == 0)
 312                                 p = t;
 313                         else
 314                                 break;
 315                 }
 316                 l->il_at = p;
 317         }
 318         assert_corr(iam_leaf_at_rec(l));
 319
 320         if (lfix_keycmp(c, iam_leaf_key_at(l->il_at), k) == 0)
 321                 result = IAM_LOOKUP_EXACT;
 322
 323         if (lfix_dump)
 324                 lfix_print(l);
 325
 326         return result;
 327 }
 328
 329 static int iam_lfix_ilookup(struct iam_leaf *l, const struct iam_ikey *ik)
 330 {
 331         return iam_lfix_lookup(l, (const struct iam_key *)ik);
 332 }
 333
 334 static void iam_lfix_key_set(struct iam_leaf *l, const struct iam_key *k)
 335 {
 336         assert_corr(iam_leaf_at_rec(l));
 337         memcpy(iam_leaf_key_at(l->il_at), k, iam_leaf_descr(l)->id_key_size);
 338 }
 339
 340 static int iam_lfix_key_cmp(const struct iam_leaf *l, const struct iam_key *k)
 341 {
 342         return lfix_keycmp(iam_leaf_container(l), iam_leaf_key_at(l->il_at), k);
 343 }
 344
 345 static int iam_lfix_key_eq(const struct iam_leaf *l, const struct iam_key *k)
 346 {
 347         return !lfix_keycmp(iam_leaf_container(l),
 348                             iam_leaf_key_at(l->il_at), k);
 349 }
 350
 351 static void iam_lfix_rec_set(struct iam_leaf *l, const struct iam_rec *r)
 352 {
 353         assert_corr(iam_leaf_at_rec(l));
 354         memcpy(iam_lfix_rec(l), r, iam_leaf_descr(l)->id_rec_size);
 355 }
 356
 357 static inline int lfix_reccmp(const struct iam_container *c,
 358                               const struct iam_rec *r1,
 359                               const struct iam_rec *r2)
 360 {
 361         return memcmp(r1, r2, c->ic_descr->id_rec_size);
 362 }
 363
 364 static int iam_lfix_rec_eq(const struct iam_leaf *l, const struct iam_rec *r)
 365 {
 366         return !lfix_reccmp(iam_leaf_container(l), iam_lfix_rec(l), r);
 367 }
 368
 369 static void iam_lfix_rec_get(const struct iam_leaf *l, struct iam_rec *r)
 370 {
 371         assert_corr(iam_leaf_at_rec(l));
 372         memcpy(r, iam_lfix_rec(l), iam_leaf_descr(l)->id_rec_size);
 373 }
 374
 375 static void iam_lfix_rec_add(struct iam_leaf *leaf,
 376                              const struct iam_key *k, const struct iam_rec *r)
 377 {
 378         struct iam_lentry *end;
 379         struct iam_lentry *cur;
 380         struct iam_lentry *start;
 381         ptrdiff_t diff;
 382         int count;
 383
 384         assert_corr(iam_leaf_can_add(leaf, k, r));
 385
 386         count = lentry_count_get(leaf);
 387         /*
 388          * This branch handles two exceptional cases:
 389          *
 390          *   - leaf positioned beyond last record, and
 391          *
 392          *   - empty leaf.
 393          */
 394         if (!iam_leaf_at_end(leaf)) {
 395                 end   = iam_lfix_get_end(leaf);
 396                 cur   = leaf->il_at;
 397                 if (lfix_keycmp(iam_leaf_container(leaf),
 398                                 k, iam_leaf_key_at(cur)) >= 0)
 399                         iam_lfix_next(leaf);
 400                 else
 401                         /*
 402                          * Another exceptional case: insertion with the key
 403                          * less than least key in the leaf.
 404                          */
 405                         assert_corr(cur == leaf->il_entries);
 406
 407                 start = leaf->il_at;
 408                 diff  = (void *)end - (void *)start;
 409                 assert_corr(diff >= 0);
 410                 memmove(iam_lfix_shift(leaf, start, 1), start, diff);
 411         }
 412         lentry_count_set(leaf, count + 1);
 413         iam_lfix_key_set(leaf, k);
 414         iam_lfix_rec_set(leaf, r);
 415         assert_corr(iam_leaf_at_rec(leaf));
 416 }
 417
 418 static void iam_lfix_rec_del(struct iam_leaf *leaf, int shift)
 419 {
 420         struct iam_lentry *next, *end;
 421         int count;
 422         ptrdiff_t diff;
 423
 424         assert_corr(iam_leaf_at_rec(leaf));
 425
 426         count = lentry_count_get(leaf);
 427         end = iam_lfix_get_end(leaf);
 428         next = iam_lfix_shift(leaf, leaf->il_at, 1);
 429         diff = (void *)end - (void *)next;
 430         memmove(leaf->il_at, next, diff);
 431
 432         lentry_count_set(leaf, count - 1);
 433 }
 434
 435 static int iam_lfix_can_add(const struct iam_leaf *l,
 436                             const struct iam_key *k, const struct iam_rec *r)
 437 {
 438         return lentry_count_get(l) < leaf_count_limit(l);
 439 }
 440
 441 static int iam_lfix_at_end(const struct iam_leaf *folio)
 442 {
 443         return folio->il_at == iam_lfix_get_end(folio);
 444 }
 445
 446 static void iam_lfix_init_new(struct iam_container *c, struct buffer_head *bh)
 447 {
 448         struct iam_leaf_head *hdr;
 449
 450         hdr = (struct iam_leaf_head *)bh->b_data;
 451         hdr->ill_magic = cpu_to_le16(IAM_LEAF_HEADER_MAGIC);
 452         hdr->ill_count = cpu_to_le16(0);
 453 }
 454
 455 static void iam_lfix_split(struct iam_leaf *l, struct buffer_head **bh,
 456                            iam_ptr_t new_blknr)
 457 {
 458         struct iam_path *path;
 459         struct iam_leaf_head *hdr;
 460         const struct iam_ikey *pivot;
 461         struct buffer_head *new_leaf;
 462
 463         unsigned int count;
 464         unsigned int split;
 465
 466         void *start;
 467         void *finis;
 468
 469         new_leaf = *bh;
 470         path = iam_leaf_path(l);
 471
 472         hdr = (void *)new_leaf->b_data;
 473
 474         count = lentry_count_get(l);
 475         split = count / 2;
 476
 477         start = iam_lfix_shift(l, iam_get_lentries(l), split);
 478         finis = iam_lfix_shift(l, iam_get_lentries(l), count);
 479
 480         pivot = (const struct iam_ikey *)iam_leaf_key_at(start);
 481
 482         memmove(iam_entries(new_leaf), start, finis - start);
 483         hdr->ill_count = cpu_to_le16(count - split);
 484         lentry_count_set(l, split);
 485         if ((void *)l->il_at >= start) {
 486                 /*
 487                  * insertion point moves into new leaf.
 488                  */
 489                 int shift;
 490
 491                 shift = iam_lfix_diff(l, l->il_at, start);
 492                 *bh = l->il_bh;
 493                 l->il_bh = new_leaf;
 494                 l->il_curidx = new_blknr;
 495                 iam_lfix_init(l);
 496                 /*
 497                  * init cannot fail, as node was just initialized.
 498                  */
 499                 assert_corr(result == 0);
 500                 l->il_at = iam_lfix_shift(l, iam_get_lentries(l), shift);
 501         }
 502         /*
 503          * Insert pointer to the new node (together with the least key in
 504          * the node) into index node.
 505          */
 506         iam_insert_key_lock(path, path->ip_frame, pivot, new_blknr);
 507 }
 508
 509 static int iam_lfix_leaf_empty(struct iam_leaf *leaf)
 510 {
 511         return lentry_count_get(leaf) == 0;
 512 }
 513
 514 static const struct iam_leaf_operations iam_lfix_leaf_ops = {
 515         .init           = iam_lfix_init,
 516         .init_new       = iam_lfix_init_new,
 517         .fini           = iam_lfix_fini,
 518         .start          = iam_lfix_start,
 519         .next           = iam_lfix_next,
 520         .key            = iam_lfix_key,
 521         .ikey           = iam_lfix_ikey,
 522         .rec            = iam_lfix_rec,
 523         .key_set        = iam_lfix_key_set,
 524         .key_cmp        = iam_lfix_key_cmp,
 525         .key_eq         = iam_lfix_key_eq,
 526         .key_size       = iam_lfix_key_size,
 527         .rec_set        = iam_lfix_rec_set,
 528         .rec_eq         = iam_lfix_rec_eq,
 529         .rec_get        = iam_lfix_rec_get,
 530         .lookup         = iam_lfix_lookup,
 531         .ilookup        = iam_lfix_ilookup,
 532         .at_end         = iam_lfix_at_end,
 533         .rec_add        = iam_lfix_rec_add,
 534         .rec_del        = iam_lfix_rec_del,
 535         .can_add        = iam_lfix_can_add,
 536         .split          = iam_lfix_split,
 537         .leaf_empty     = iam_lfix_leaf_empty,
 538 };
 539
 540 /*
 541  * Index operations.
 542  */
 543
 544 enum {
 545         /* This is duplicated in lustre/utils/create_iam.c */
 546         /*
 547          * Then shalt thou see the dew-BEDABBLED wretch
 548          * Turn, and return, indenting with the way;
 549          * Each envious brier his weary legs doth scratch,
 550          * Each shadow makes him stop, each murmur stay:
 551          * For misery is trodden on by many,
 552          * And being low never relieved by any.
 553          */
 554         IAM_LFIX_ROOT_MAGIC = 0xbedabb1edULL /* d01efull */
 555 };
 556
 557 /* This is duplicated in lustre/utils/create_iam.c */
 558 struct iam_lfix_root {
 559         __le64  ilr_magic;
 560         __le16  ilr_keysize;
 561         __le16  ilr_recsize;
 562         __le16  ilr_ptrsize;
 563         u8      ilr_indirect_levels;
 564         u8      ilr_padding;
 565 };
 566
 567 static __u32 iam_lfix_root_ptr(struct iam_container *c)
 568 {
 569         return 0;
 570 }
 571
 572 static int iam_lfix_node_init(struct iam_container *c, struct buffer_head *bh,
 573                               int root)
 574 {
 575         return 0;
 576 }
 577
 578 static struct iam_entry *iam_lfix_root_inc(struct iam_container *c,
 579                                            struct iam_path *path,
 580                                            struct iam_frame *frame)
 581 {
 582         struct iam_lfix_root *root;
 583         struct iam_entry *entries;
 584
 585         entries = frame->entries;
 586
 587         dx_set_count(entries, 2);
 588         assert_corr(dx_get_limit(entries) == dx_root_limit(path));
 589
 590         root = (void *)frame->bh->b_data;
 591         assert_corr(le64_to_cpu(root->ilr_magic) == IAM_LFIX_ROOT_MAGIC);
 592         root->ilr_indirect_levels++;
 593         frame->at = entries = iam_entry_shift(path, entries, 1);
 594         memset(iam_ikey_at(path, entries), 0,
 595                iam_path_descr(path)->id_ikey_size);
 596         return entries;
 597 }
 598
 599 static int iam_lfix_node_check(struct iam_path *path, struct iam_frame *frame)
 600 {
 601         unsigned int count;
 602         unsigned int limit;
 603         unsigned int limit_correct;
 604         struct iam_entry *entries;
 605
 606         entries = dx_node_get_entries(path, frame);
 607
 608         if (frame == path->ip_frames) {
 609                 struct iam_lfix_root *root;
 610
 611                 root = (void *)frame->bh->b_data;
 612                 if (le64_to_cpu(root->ilr_magic) != IAM_LFIX_ROOT_MAGIC)
 613                         return -EIO;
 614                 limit_correct = dx_root_limit(path);
 615         } else {
 616                 limit_correct = dx_node_limit(path);
 617         }
 618         count = dx_get_count(entries);
 619         limit = dx_get_limit(entries);
 620         if (count > limit)
 621                 return -EIO;
 622         if (limit != limit_correct)
 623                 return -EIO;
 624         return 0;
 625 }
 626
 627 static int iam_lfix_node_load(struct iam_path *path, struct iam_frame *frame)
 628 {
 629         struct iam_entry *entries;
 630         void *data;
 631
 632         entries = dx_node_get_entries(path, frame);
 633         data = frame->bh->b_data;
 634
 635         if (frame == path->ip_frames) {
 636                 struct iam_lfix_root *root;
 637
 638                 root = data;
 639                 path->ip_indirect = root->ilr_indirect_levels;
 640                 if (path->ip_ikey_target == NULL)
 641                         path->ip_ikey_target =
 642                                 (struct iam_ikey *)path->ip_key_target;
 643         }
 644         frame->entries = frame->at = entries;
 645         return 0;
 646 }
 647
 648 static int iam_lfix_ikeycmp(const struct iam_container *c,
 649                             const struct iam_ikey *k1,
 650                             const struct iam_ikey *k2)
 651 {
 652         return memcmp(k1, k2, c->ic_descr->id_ikey_size);
 653 }
 654
 655 static struct iam_path_descr *iam_lfix_ipd_alloc(const struct iam_container *c,
 656                                                  void *area)
 657 {
 658         return iam_ipd_alloc(area, c->ic_descr->id_ikey_size);
 659 }
 660
 661 static const struct iam_operations iam_lfix_ops = {
 662         .id_root_ptr    = iam_lfix_root_ptr,
 663         .id_node_read   = iam_node_read,
 664         .id_node_init   = iam_lfix_node_init,
 665         .id_node_check  = iam_lfix_node_check,
 666         .id_node_load   = iam_lfix_node_load,
 667         .id_ikeycmp     = iam_lfix_ikeycmp,
 668         .id_root_inc    = iam_lfix_root_inc,
 669         .id_ipd_alloc   = iam_lfix_ipd_alloc,
 670         .id_ipd_free    = iam_ipd_free,
 671         .id_name        = "lfix"
 672 };
 673
 674 int iam_lfix_guess(struct iam_container *c)
 675 {
 676         int result;
 677         struct buffer_head *bh;
 678         const struct iam_lfix_root *root;
 679
 680         assert_corr(c->ic_object != NULL);
 681
 682         result = iam_node_read(c, iam_lfix_root_ptr(c), NULL, &bh);
 683         if (result == 0) {
 684                 root = (void *)bh->b_data;
 685                 if (le64_to_cpu(root->ilr_magic) == IAM_LFIX_ROOT_MAGIC) {
 686                         struct iam_descr *descr;
 687
 688                         descr = c->ic_descr;
 689                         descr->id_key_size  = le16_to_cpu(root->ilr_keysize);
 690                         descr->id_ikey_size = le16_to_cpu(root->ilr_keysize);
 691                         descr->id_rec_size  = le16_to_cpu(root->ilr_recsize);
 692                         descr->id_ptr_size  = le16_to_cpu(root->ilr_ptrsize);
 693                         descr->id_root_gap  = sizeof(struct iam_lfix_root);
 694                         descr->id_node_gap  = 0;
 695                         descr->id_ops       = &iam_lfix_ops;
 696                         descr->id_leaf_ops  = &iam_lfix_leaf_ops;
 697                         c->ic_root_bh = bh;
 698                 } else {
 699                         result = -EBADF;
 700                         brelse(bh);
 701                 }
 702         }
 703         return result;
 704 }
 705
 706 /*
 707  * Debugging aid.
 708  */
 709
 710 #define KEYSIZE (8)
 711 #define RECSIZE (8)
 712 #define PTRSIZE (4)
 713
 714 #define LFIX_ROOT_RECNO \
 715         ((4096 - sizeof(struct iam_lfix_root)) / (KEYSIZE + PTRSIZE))
 716
 717 #define LFIX_INDEX_RECNO (4096 / (KEYSIZE + PTRSIZE))
 718
 719 #define LFIX_LEAF_RECNO \
 720         ((4096 - sizeof(struct iam_leaf_head)) / (KEYSIZE + RECSIZE))
 721
 722         struct lfix_root {
 723         struct iam_lfix_root lr_root;
 724         struct {
 725                 char key[KEYSIZE];
 726                 char ptr[PTRSIZE];
 727         } lr_entry[LFIX_ROOT_RECNO];
 728 };
 729
 730         struct lfix_index {
 731         struct dx_countlimit li_cl;
 732         char   li_padding[KEYSIZE + PTRSIZE - sizeof(struct dx_countlimit)];
 733         struct {
 734                 char key[KEYSIZE];
 735                 char ptr[PTRSIZE];
 736         } li_entry[LFIX_INDEX_RECNO - 1];
 737 };
 738
 739         struct lfix_leaf {
 740                 struct iam_leaf_head ll_head;
 741                 struct {
 742                         char key[KEYSIZE];
 743                         char rec[RECSIZE];
 744                 } ll_entry[LFIX_LEAF_RECNO];
 745         };
 746
 747 #define STORE_UNALIGNED(val, dst)                       \
 748 ({                                                      \
 749         typeof(val) __val = (val);                      \
 750         BUILD_BUG_ON(sizeof(val) != sizeof(*(dst)));    \
 751         memcpy(dst, &__val, sizeof(*(dst)));            \
 752 })
 753
 754 static void lfix_root(void *buf,
 755                       int blocksize, int keysize, int ptrsize, int recsize)
 756 {
 757         struct iam_lfix_root *root;
 758         struct dx_countlimit *limit;
 759         void *entry;
 760
 761         root = buf;
 762         *root = (typeof(*root)) {
 763                 .ilr_magic           = cpu_to_le64(IAM_LFIX_ROOT_MAGIC),
 764                 .ilr_keysize         = cpu_to_le16(keysize),
 765                 .ilr_recsize         = cpu_to_le16(recsize),
 766                 .ilr_ptrsize         = cpu_to_le16(ptrsize),
 767                 .ilr_indirect_levels = 0
 768         };
 769
 770         limit = (void *)(root + 1);
 771         *limit = (typeof(*limit)){
 772                 /*
 773                  * limit itself + one pointer to the leaf.
 774                  */
 775                 .count = cpu_to_le16(2),
 776                 .limit = iam_root_limit(sizeof(struct iam_lfix_root),
 777                                         blocksize, keysize + ptrsize)
 778         };
 779
 780         /* To guarantee that the padding "keysize + ptrsize"
 781          * covers the "dx_countlimit" and the "idle_blocks". */
 782         LASSERT((keysize + ptrsize) >=
 783                 (sizeof(struct dx_countlimit) + sizeof(__u32)));
 784
 785         entry = (void *)(limit + 1);
 786         /* Put "idle_blocks" just after the limit. There was padding after
 787          * the limit, the "idle_blocks" re-uses part of the padding, so no
 788          * compatibility issues with old layout.
 789          */
 790         *(__u32 *)entry = 0;
 791
 792         /*
 793          * Skip over @limit.
 794          */
 795         entry = (void *)(root + 1) + keysize + ptrsize;
 796
 797         /*
 798          * Entry format is <key> followed by <ptr>. In the minimal tree
 799          * consisting of a root and single node, <key> is a minimal possible
 800          * key.
 801          *
 802          * XXX: this key is hard-coded to be a sequence of 0's.
 803          */
 804
 805         memset(entry, 0, keysize);
 806         entry += keysize;
 807         /* now @entry points to <ptr> */
 808         if (ptrsize == 4)
 809                 STORE_UNALIGNED(cpu_to_le32(1), (u_int32_t *)entry);
 810         else
 811                 STORE_UNALIGNED(cpu_to_le64(1), (u_int64_t *)entry);
 812 }
 813
 814 static void lfix_leaf(void *buf,
 815                       int blocksize, int keysize, int ptrsize, int recsize)
 816 {
 817         struct iam_leaf_head *head;
 818         void *entry;
 819
 820         /* form leaf */
 821         head = buf;
 822         *head = (struct iam_leaf_head) {
 823                 .ill_magic = cpu_to_le16(IAM_LEAF_HEADER_MAGIC),
 824                 /*
 825                  * Leaf contains an entry with the smallest possible key
 826                  * (created by zeroing).
 827                  */
 828                 .ill_count = cpu_to_le16(1),
 829         };
 830
 831         entry = (void *)(head + 1);
 832         memset(entry, 0, keysize + recsize);
 833 }
 834
 835 int iam_lfix_create(struct inode *obj,
 836                     int keysize, int ptrsize, int recsize, handle_t *handle)
 837 {
 838         struct buffer_head *root_node;
 839         struct buffer_head *leaf_node;
 840         struct super_block *sb;
 841         u32 blknr;
 842         int result = 0;
 843         unsigned long bsize;
 844
 845         assert_corr(obj->i_size == 0);
 846
 847         sb = obj->i_sb;
 848         bsize = sb->s_blocksize;
 849         root_node = osd_ldiskfs_append(handle, obj, &blknr);
 850         if (IS_ERR(root_node))
 851                 GOTO(out, result = PTR_ERR(root_node));
 852
 853         leaf_node = osd_ldiskfs_append(handle, obj, &blknr);
 854         if (IS_ERR(leaf_node))
 855                 GOTO(out_root, result = PTR_ERR(leaf_node));
 856
 857         lfix_root(root_node->b_data, bsize, keysize, ptrsize, recsize);
 858         lfix_leaf(leaf_node->b_data, bsize, keysize, ptrsize, recsize);
 859         ldiskfs_mark_inode_dirty(handle, obj);
 860         result = ldiskfs_handle_dirty_metadata(handle, NULL, root_node);
 861         if (result == 0)
 862                 result = ldiskfs_handle_dirty_metadata(handle, NULL, leaf_node);
 863         if (result != 0)
 864                 ldiskfs_std_error(sb, result);
 865
 866         brelse(leaf_node);
 867
 868         GOTO(out_root, result);
 869
 870 out_root:
 871         brelse(root_node);
 872 out:
 873         return result;
 874 }