lustre/osd/osd_iam_lfix.c

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