Whamcloud - gitweb
b36683f6a95302af1d01a644b51ac9b1acb85ad5
[fs/lustre-release.git] / 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 Whamcloud, Inc.
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 (ill->ill_magic == le16_to_cpu(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                        ill->ill_magic, le16_to_cpu(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 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(CFS_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(CFS_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         assert(0);
335         return IAM_LOOKUP_OK;
336 }
337
338 static void iam_lfix_key_set(struct iam_leaf *l, const struct iam_key *k)
339 {
340         assert_corr(iam_leaf_at_rec(l));
341         memcpy(iam_leaf_key_at(l->il_at), k, iam_leaf_descr(l)->id_key_size);
342 }
343
344 static int iam_lfix_key_cmp(const struct iam_leaf *l, const struct iam_key *k)
345 {
346         return lfix_keycmp(iam_leaf_container(l), iam_leaf_key_at(l->il_at), k);
347 }
348
349 static int iam_lfix_key_eq(const struct iam_leaf *l, const struct iam_key *k)
350 {
351         return !lfix_keycmp(iam_leaf_container(l),
352                             iam_leaf_key_at(l->il_at), k);
353 }
354
355 static void iam_lfix_rec_set(struct iam_leaf *l, const struct iam_rec *r)
356 {
357         assert_corr(iam_leaf_at_rec(l));
358         memcpy(iam_lfix_rec(l), r, iam_leaf_descr(l)->id_rec_size);
359 }
360
361 static inline int lfix_reccmp(const struct iam_container *c,
362                               const struct iam_rec *r1,
363                               const struct iam_rec *r2)
364 {
365         return memcmp(r1, r2, c->ic_descr->id_rec_size);
366 }
367
368 static int iam_lfix_rec_eq(const struct iam_leaf *l, const struct iam_rec *r)
369 {
370         return !lfix_reccmp(iam_leaf_container(l), iam_lfix_rec(l), r);
371 }
372
373 static void iam_lfix_rec_get(const struct iam_leaf *l, struct iam_rec *r)
374 {
375         assert_corr(iam_leaf_at_rec(l));
376         memcpy(r, iam_lfix_rec(l), iam_leaf_descr(l)->id_rec_size);
377 }
378
379 static void iam_lfix_rec_add(struct iam_leaf *leaf,
380                              const struct iam_key *k, const struct iam_rec *r)
381 {
382         struct iam_lentry *end;
383         struct iam_lentry *cur;
384         struct iam_lentry *start;
385         ptrdiff_t diff;
386         int count;
387
388         assert_corr(iam_leaf_can_add(leaf, k, r));
389
390         count = lentry_count_get(leaf);
391         /*
392          * This branch handles two exceptional cases:
393          *
394          *   - leaf positioned beyond last record, and
395          *
396          *   - empty leaf.
397          */
398         if (!iam_leaf_at_end(leaf)) {
399                 end   = iam_lfix_get_end(leaf);
400                 cur   = leaf->il_at;
401                 if (lfix_keycmp(iam_leaf_container(leaf),
402                                k, iam_leaf_key_at(cur)) >= 0)
403                         iam_lfix_next(leaf);
404                 else
405                         /*
406                          * Another exceptional case: insertion with the key
407                          * less than least key in the leaf.
408                          */
409                         assert_corr(cur == leaf->il_entries);
410
411                 start = leaf->il_at;
412                 diff  = (void *)end - (void *)start;
413                 assert_corr(diff >= 0);
414                 memmove(iam_lfix_shift(leaf, start, 1), start, diff);
415         }
416         lentry_count_set(leaf, count + 1);
417         iam_lfix_key_set(leaf, k);
418         iam_lfix_rec_set(leaf, r);
419         assert_corr(iam_leaf_at_rec(leaf));
420 }
421
422 static void iam_lfix_rec_del(struct iam_leaf *leaf, int shift)
423 {
424         struct iam_lentry *next, *end;
425         int count;
426         ptrdiff_t diff;
427
428         assert_corr(iam_leaf_at_rec(leaf));
429
430         count = lentry_count_get(leaf);
431         end = iam_lfix_get_end(leaf);
432         next = iam_lfix_shift(leaf, leaf->il_at, 1);
433         diff = (void *)end - (void *)next;
434         memmove(leaf->il_at, next, diff);
435
436         lentry_count_set(leaf, count - 1);
437 }
438
439 static int iam_lfix_can_add(const struct iam_leaf *l,
440                             const struct iam_key *k, const struct iam_rec *r)
441 {
442         return lentry_count_get(l) < leaf_count_limit(l);
443 }
444
445 static int iam_lfix_at_end(const struct iam_leaf *folio)
446 {
447         return folio->il_at == iam_lfix_get_end(folio);
448 }
449
450 static void iam_lfix_init_new(struct iam_container *c, struct buffer_head *bh)
451 {
452         struct iam_leaf_head *hdr;
453
454         hdr = (struct iam_leaf_head*)bh->b_data;
455         hdr->ill_magic = cpu_to_le16(IAM_LEAF_HEADER_MAGIC);
456         hdr->ill_count = cpu_to_le16(0);
457 }
458
459 static void iam_lfix_split(struct iam_leaf *l, struct buffer_head **bh,
460                            iam_ptr_t new_blknr)
461 {
462         struct iam_path       *path;
463         struct iam_leaf_head  *hdr;
464         const struct iam_ikey *pivot;
465         struct buffer_head    *new_leaf;
466
467         unsigned count;
468         unsigned split;
469
470         void *start;
471         void *finis;
472
473         new_leaf = *bh;
474         path = iam_leaf_path(l);
475
476         hdr = (void *)new_leaf->b_data;
477
478         count = lentry_count_get(l);
479         split = count / 2;
480
481         start = iam_lfix_shift(l, iam_get_lentries(l), split);
482         finis = iam_lfix_shift(l, iam_get_lentries(l), count);
483
484         pivot = (const struct iam_ikey *)iam_leaf_key_at(start);
485
486         memmove(iam_entries(new_leaf), start, finis - start);
487         hdr->ill_count = count - split;
488         lentry_count_set(l, split);
489         if ((void *)l->il_at >= start) {
490                 /*
491                  * insertion point moves into new leaf.
492                  */
493                 int shift;
494                 int result;
495
496                 shift = iam_lfix_diff(l, l->il_at, start);
497                 *bh = l->il_bh;
498                 l->il_bh = new_leaf;
499                 l->il_curidx = new_blknr;
500                 result = iam_lfix_init(l);
501                 /*
502                  * init cannot fail, as node was just initialized.
503                  */
504                 assert_corr(result == 0);
505                 l->il_at = iam_lfix_shift(l, iam_get_lentries(l), shift);
506         }
507         /*
508          * Insert pointer to the new node (together with the least key in
509          * the node) into index node.
510          */
511         iam_insert_key_lock(path, path->ip_frame, pivot, new_blknr);
512 }
513
514 static int iam_lfix_leaf_empty(struct iam_leaf *leaf)
515 {
516         return lentry_count_get(leaf) == 0;
517 }
518
519 static struct iam_leaf_operations iam_lfix_leaf_ops = {
520         .init           = iam_lfix_init,
521         .init_new       = iam_lfix_init_new,
522         .fini           = iam_lfix_fini,
523         .start          = iam_lfix_start,
524         .next           = iam_lfix_next,
525         .key            = iam_lfix_key,
526         .ikey           = iam_lfix_ikey,
527         .rec            = iam_lfix_rec,
528         .key_set        = iam_lfix_key_set,
529         .key_cmp        = iam_lfix_key_cmp,
530         .key_eq         = iam_lfix_key_eq,
531         .key_size       = iam_lfix_key_size,
532         .rec_set        = iam_lfix_rec_set,
533         .rec_eq         = iam_lfix_rec_eq,
534         .rec_get        = iam_lfix_rec_get,
535         .lookup         = iam_lfix_lookup,
536         .ilookup        = iam_lfix_ilookup,
537         .at_end         = iam_lfix_at_end,
538         .rec_add        = iam_lfix_rec_add,
539         .rec_del        = iam_lfix_rec_del,
540         .can_add        = iam_lfix_can_add,
541         .split          = iam_lfix_split,
542         .leaf_empty     = iam_lfix_leaf_empty,
543 };
544
545 /*
546  * Index operations.
547  */
548
549 enum {
550         /* This is duplicated in lustre/utils/create_iam.c */
551         /*
552          * Then shalt thou see the dew-BEDABBLED wretch
553          * Turn, and return, indenting with the way;
554          * Each envious brier his weary legs doth scratch,
555          * Each shadow makes him stop, each murmur stay:
556          * For misery is trodden on by many,
557          * And being low never relieved by any.
558          */
559         IAM_LFIX_ROOT_MAGIC = 0xbedabb1edULL // d01efull
560 };
561
562 /* This is duplicated in lustre/utils/create_iam.c */
563 struct iam_lfix_root {
564         __le64  ilr_magic;
565         __le16  ilr_keysize;
566         __le16  ilr_recsize;
567         __le16  ilr_ptrsize;
568         u8      ilr_indirect_levels;
569         u8      ilr_padding;
570 };
571
572 static __u32 iam_lfix_root_ptr(struct iam_container *c)
573 {
574         return 0;
575 }
576
577 static int iam_lfix_node_init(struct iam_container *c, struct buffer_head *bh,
578                               int root)
579 {
580         return 0;
581 }
582
583 static struct iam_entry *iam_lfix_root_inc(struct iam_container *c,
584                                            struct iam_path *path,
585                                            struct iam_frame *frame)
586 {
587         struct iam_lfix_root *root;
588         struct iam_entry     *entries;
589
590         entries = frame->entries;
591
592         dx_set_count(entries, 2);
593         assert_corr(dx_get_limit(entries) == dx_root_limit(path));
594
595         root = (void *)frame->bh->b_data;
596         assert_corr(le64_to_cpu(root->ilr_magic) == IAM_LFIX_ROOT_MAGIC);
597         root->ilr_indirect_levels ++;
598         frame->at = entries = iam_entry_shift(path, entries, 1);
599         memset(iam_ikey_at(path, entries), 0,
600                iam_path_descr(path)->id_ikey_size);
601         return entries;
602 }
603
604 static int iam_lfix_node_check(struct iam_path *path, struct iam_frame *frame)
605 {
606         unsigned count;
607         unsigned limit;
608         unsigned limit_correct;
609         struct iam_entry *entries;
610
611         entries = dx_node_get_entries(path, frame);
612
613         if (frame == path->ip_frames) {
614                 struct iam_lfix_root *root;
615
616                 root = (void *)frame->bh->b_data;
617                 if (le64_to_cpu(root->ilr_magic) != IAM_LFIX_ROOT_MAGIC) {
618                         return -EIO;
619                 }
620                 limit_correct = dx_root_limit(path);
621         } else
622                 limit_correct = dx_node_limit(path);
623         count = dx_get_count(entries);
624         limit = dx_get_limit(entries);
625         if (count > limit) {
626                 return -EIO;
627         }
628         if (limit != limit_correct) {
629                 return -EIO;
630         }
631         return 0;
632 }
633
634 static int iam_lfix_node_load(struct iam_path *path, struct iam_frame *frame)
635 {
636         struct iam_entry *entries;
637         void *data;
638         entries = dx_node_get_entries(path, frame);
639
640         data = frame->bh->b_data;
641
642         if (frame == path->ip_frames) {
643                 struct iam_lfix_root *root;
644
645                 root = data;
646                 path->ip_indirect = root->ilr_indirect_levels;
647                 if (path->ip_ikey_target == NULL)
648                         path->ip_ikey_target =
649                                 (struct iam_ikey *)path->ip_key_target;
650         }
651         frame->entries = frame->at = entries;
652         return 0;
653 }
654
655 static int iam_lfix_ikeycmp(const struct iam_container *c,
656                             const struct iam_ikey *k1,
657                             const struct iam_ikey *k2)
658 {
659         return memcmp(k1, k2, c->ic_descr->id_ikey_size);
660 }
661
662 static struct iam_path_descr *iam_lfix_ipd_alloc(const struct iam_container *c,
663                                                  void *area)
664 {
665         return iam_ipd_alloc(area, c->ic_descr->id_ikey_size);
666 }
667
668 static struct iam_operations iam_lfix_ops = {
669         .id_root_ptr    = iam_lfix_root_ptr,
670         .id_node_read   = iam_node_read,
671         .id_node_init   = iam_lfix_node_init,
672         .id_node_check  = iam_lfix_node_check,
673         .id_node_load   = iam_lfix_node_load,
674         .id_ikeycmp     = iam_lfix_ikeycmp,
675         .id_root_inc    = iam_lfix_root_inc,
676         .id_ipd_alloc   = iam_lfix_ipd_alloc,
677         .id_ipd_free    = iam_ipd_free,
678         .id_name        = "lfix"
679 };
680
681 static int iam_lfix_guess(struct iam_container *c)
682 {
683         int result;
684         struct buffer_head *bh;
685         const struct iam_lfix_root *root;
686
687         assert_corr(c->ic_object != NULL);
688
689         result = iam_node_read(c, iam_lfix_root_ptr(c), NULL, &bh);
690         if (result == 0) {
691                 root = (void *)bh->b_data;
692                 if (le64_to_cpu(root->ilr_magic) == IAM_LFIX_ROOT_MAGIC) {
693                         struct iam_descr *descr;
694
695                         descr = c->ic_descr;
696                         descr->id_key_size  = le16_to_cpu(root->ilr_keysize);
697                         descr->id_ikey_size = le16_to_cpu(root->ilr_keysize);
698                         descr->id_rec_size  = le16_to_cpu(root->ilr_recsize);
699                         descr->id_ptr_size  = le16_to_cpu(root->ilr_ptrsize);
700                         descr->id_root_gap  = sizeof(struct iam_lfix_root);
701                         descr->id_node_gap  = 0;
702                         descr->id_ops       = &iam_lfix_ops;
703                         descr->id_leaf_ops  = &iam_lfix_leaf_ops;
704
705                         c->ic_root_bh = bh;
706                 } else {
707                         result = -EBADF;
708                         brelse(bh);
709                 }
710         }
711         return result;
712 }
713
714 static struct iam_format iam_lfix_format = {
715         .if_guess = iam_lfix_guess
716 };
717
718 void iam_lfix_format_init(void)
719 {
720         iam_format_register(&iam_lfix_format);
721 }
722
723 /*
724  * Debugging aid.
725  */
726
727 #define KEYSIZE (8)
728 #define RECSIZE (8)
729 #define PTRSIZE (4)
730
731 #define LFIX_ROOT_RECNO \
732         ((4096 - sizeof(struct iam_lfix_root)) / (KEYSIZE + PTRSIZE))
733
734 #define LFIX_INDEX_RECNO (4096 / (KEYSIZE + PTRSIZE))
735
736 #define LFIX_LEAF_RECNO \
737         ((4096 - sizeof(struct iam_leaf_head)) / (KEYSIZE + RECSIZE))
738
739 struct lfix_root {
740         struct iam_lfix_root lr_root;
741         struct {
742                 char key[KEYSIZE];
743                 char ptr[PTRSIZE];
744         } lr_entry[LFIX_ROOT_RECNO];
745 };
746
747 struct lfix_index {
748         struct dx_countlimit li_cl;
749         char   li_padding[KEYSIZE + PTRSIZE - sizeof(struct dx_countlimit)];
750         struct {
751                 char key[KEYSIZE];
752                 char ptr[PTRSIZE];
753         } li_entry[LFIX_INDEX_RECNO - 1];
754 };
755
756 struct lfix_leaf {
757         struct iam_leaf_head ll_head;
758         struct {
759                 char key[KEYSIZE];
760                 char rec[RECSIZE];
761         } ll_entry[LFIX_LEAF_RECNO];
762 };
763
764 #define STORE_UNALIGNED(val, dst)                       \
765 ({                                                      \
766         typeof(val) __val = (val);                      \
767         CLASSERT(sizeof(val) == sizeof(*(dst)));        \
768         memcpy(dst, &__val, sizeof(*(dst)));            \
769 })
770
771 static void lfix_root(void *buf,
772                       int blocksize, int keysize, int ptrsize, int recsize)
773 {
774         struct iam_lfix_root *root;
775         struct dx_countlimit *limit;
776         void                 *entry;
777
778         root = buf;
779         *root = (typeof(*root)) {
780                 .ilr_magic           = cpu_to_le64(IAM_LFIX_ROOT_MAGIC),
781                 .ilr_keysize         = cpu_to_le16(keysize),
782                 .ilr_recsize         = cpu_to_le16(recsize),
783                 .ilr_ptrsize         = cpu_to_le16(ptrsize),
784                 .ilr_indirect_levels = 0
785         };
786
787         limit = (void *)(root + 1);
788         *limit = (typeof(*limit)){
789                 /*
790                  * limit itself + one pointer to the leaf.
791                  */
792                 .count = cpu_to_le16(2),
793                 .limit = iam_root_limit(sizeof(struct iam_lfix_root),
794                                         blocksize, keysize + ptrsize)
795         };
796
797         /* To guarantee that the padding "keysize + ptrsize"
798          * covers the "dx_countlimit" and the "idle_blocks". */
799         LASSERT((keysize + ptrsize) >=
800                 (sizeof(struct dx_countlimit) + sizeof(__u32)));
801
802         entry = (void *)(limit + 1);
803         /* Put "idle_blocks" just after the limit. There was padding after
804          * the limit, the "idle_blocks" re-uses part of the padding, so no
805          * compatibility issues with old layout.
806          */
807         *(__u32 *)entry = 0;
808
809         /*
810          * Skip over @limit.
811          */
812         entry = (void *)(root + 1) + keysize + ptrsize;
813
814         /*
815          * Entry format is <key> followed by <ptr>. In the minimal tree
816          * consisting of a root and single node, <key> is a minimal possible
817          * key.
818          *
819          * XXX: this key is hard-coded to be a sequence of 0's.
820          */
821
822         memset(entry, 0, keysize);
823         entry += keysize;
824         /* now @entry points to <ptr> */
825         if (ptrsize == 4)
826                 STORE_UNALIGNED(cpu_to_le32(1), (u_int32_t *)entry);
827         else
828                 STORE_UNALIGNED(cpu_to_le64(1), (u_int64_t *)entry);
829 }
830
831 static void lfix_leaf(void *buf,
832                       int blocksize, int keysize, int ptrsize, int recsize)
833 {
834         struct iam_leaf_head *head;
835         void *entry;
836
837         /* form leaf */
838         head = buf;
839         *head = (struct iam_leaf_head) {
840                 .ill_magic = cpu_to_le16(IAM_LEAF_HEADER_MAGIC),
841                 /*
842                  * Leaf contains an entry with the smallest possible key
843                  * (created by zeroing).
844                  */
845                 .ill_count = cpu_to_le16(1),
846         };
847
848         entry = (void *)(head + 1);
849         memset(entry, 0, keysize + recsize);
850 }
851
852 int iam_lfix_create(struct inode *obj,
853                     int keysize, int ptrsize, int recsize, handle_t *handle)
854 {
855         struct buffer_head *root_node;
856         struct buffer_head *leaf_node;
857         struct super_block *sb;
858
859         u32 blknr;
860         int result;
861         unsigned long bsize;
862
863         assert_corr(obj->i_size == 0);
864
865         sb = obj->i_sb;
866         bsize = sb->s_blocksize;
867         root_node = ldiskfs_append(handle, obj, &blknr, &result);
868         leaf_node = ldiskfs_append(handle, obj, &blknr, &result);
869         if (root_node != NULL && leaf_node != NULL) {
870                 lfix_root(root_node->b_data, bsize, keysize, ptrsize, recsize);
871                 lfix_leaf(leaf_node->b_data, bsize, keysize, ptrsize, recsize);
872                 ldiskfs_mark_inode_dirty(handle, obj);
873                 result = ldiskfs_journal_dirty_metadata(handle, root_node);
874                 if (result == 0)
875                         result = ldiskfs_journal_dirty_metadata(handle, leaf_node);
876                 if (result != 0)
877                         ldiskfs_std_error(sb, result);
878         }
879         brelse(leaf_node);
880         brelse(root_node);
881         return result;
882 }
883 EXPORT_SYMBOL(iam_lfix_create);