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