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