Whamcloud - gitweb
LU-6305 osd-ldiskfs: buffer head leak in osd
[fs/lustre-release.git] / lustre / osd-ldiskfs / osd_iam.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) 2011, 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.c
37  * Top-level entry points into iam module
38  *
39  * Author: Wang Di <wangdi@clusterfs.com>
40  * Author: Nikita Danilov <nikita@clusterfs.com>
41  */
42
43 /*
44  * iam: big theory statement.
45  *
46  * iam (Index Access Module) is a module providing abstraction of persistent
47  * transactional container on top of generalized ldiskfs htree.
48  *
49  * iam supports:
50  *
51  *     - key, pointer, and record size specifiable per container.
52  *
53  *     - trees taller than 2 index levels.
54  *
55  *     - read/write to existing ldiskfs htree directories as iam containers.
56  *
57  * iam container is a tree, consisting of leaf nodes containing keys and
58  * records stored in this container, and index nodes, containing keys and
59  * pointers to leaf or index nodes.
60  *
61  * iam does not work with keys directly, instead it calls user-supplied key
62  * comparison function (->dpo_keycmp()).
63  *
64  * Pointers are (currently) interpreted as logical offsets (measured in
65  * blocksful) within underlying flat file on top of which iam tree lives.
66  *
67  * On-disk format:
68  *
69  * iam mostly tries to reuse existing htree formats.
70  *
71  * Format of index node:
72  *
73  * +-----+-------+-------+-------+------+-------+------------+
74  * |     | count |       |       |      |       |            |
75  * | gap |   /   | entry | entry | .... | entry | free space |
76  * |     | limit |       |       |      |       |            |
77  * +-----+-------+-------+-------+------+-------+------------+
78  *
79  *       gap           this part of node is never accessed by iam code. It
80  *                     exists for binary compatibility with ldiskfs htree (that,
81  *                     in turn, stores fake struct ext2_dirent for ext2
82  *                     compatibility), and to keep some unspecified per-node
83  *                     data. Gap can be different for root and non-root index
84  *                     nodes. Gap size can be specified for each container
85  *                     (gap of 0 is allowed).
86  *
87  *       count/limit   current number of entries in this node, and the maximal
88  *                     number of entries that can fit into node. count/limit
89  *                     has the same size as entry, and is itself counted in
90  *                     count.
91  *
92  *       entry         index entry: consists of a key immediately followed by
93  *                     a pointer to a child node. Size of a key and size of a
94  *                     pointer depends on container. Entry has neither
95  *                     alignment nor padding.
96  *
97  *       free space    portion of node new entries are added to
98  *
99  * Entries in index node are sorted by their key value.
100  *
101  * Format of a leaf node is not specified. Generic iam code accesses leaf
102  * nodes through ->id_leaf methods in struct iam_descr.
103  *
104  * The IAM root block is a special node, which contains the IAM descriptor.
105  * It is on disk format:
106  *
107  * +---------+-------+--------+---------+-------+------+-------+------------+
108  * |IAM desc | count |  idle  |         |       |      |       |            |
109  * |(fix/var)|   /   | blocks | padding | entry | .... | entry | free space |
110  * |         | limit |        |         |       |      |       |            |
111  * +---------+-------+--------+---------+-------+------+-------+------------+
112  *
113  * The padding length is calculated with the parameters in the IAM descriptor.
114  *
115  * The field "idle_blocks" is used to record empty leaf nodes, which have not
116  * been released but all contained entries in them have been removed. Usually,
117  * the idle blocks in the IAM should be reused when need to allocate new leaf
118  * nodes for new entries, it depends on the IAM hash functions to map the new
119  * entries to these idle blocks. Unfortunately, it is not easy to design some
120  * hash functions for such clever mapping, especially considering the insert/
121  * lookup performance.
122  *
123  * So the IAM recycles the empty leaf nodes, and put them into a per-file based
124  * idle blocks pool. If need some new leaf node, it will try to take idle block
125  * from such pool with priority, in spite of how the IAM hash functions to map
126  * the entry.
127  *
128  * The idle blocks pool is organized as a series of tables, and each table
129  * can be described as following (on-disk format):
130  *
131  * +---------+---------+---------+---------+------+---------+-------+
132  * |  magic  |  count  |  next   |  logic  |      |  logic  | free  |
133  * |(16 bits)|(16 bits)|  table  |  blk #  | .... |  blk #  | space |
134  * |         |         |(32 bits)|(32 bits)|      |(32 bits)|       |
135  * +---------+---------+---------+---------+------+---------+-------+
136  *
137  * The logic blk# for the first table is stored in the root node "idle_blocks".
138  *
139  */
140
141 #include <linux/module.h>
142 #include <linux/fs.h>
143 #include <linux/pagemap.h>
144 #include <linux/time.h>
145 #include <linux/fcntl.h>
146 #include <linux/stat.h>
147 #include <linux/string.h>
148 #include <linux/quotaops.h>
149 #include <linux/buffer_head.h>
150
151 #include <ldiskfs/ldiskfs.h>
152 #include <ldiskfs/xattr.h>
153 #undef ENTRY
154
155 #include "osd_internal.h"
156
157 #include <ldiskfs/acl.h>
158
159 /*
160  * List of all registered formats.
161  *
162  * No locking. Callers synchronize.
163  */
164 static struct list_head iam_formats = LIST_HEAD_INIT(iam_formats);
165
166 void iam_format_register(struct iam_format *fmt)
167 {
168         list_add(&fmt->if_linkage, &iam_formats);
169 }
170
171 static struct buffer_head *
172 iam_load_idle_blocks(struct iam_container *c, iam_ptr_t blk)
173 {
174         struct inode *inode = c->ic_object;
175         struct iam_idle_head *head;
176         struct buffer_head *bh;
177         int err;
178
179         LASSERT(mutex_is_locked(&c->ic_idle_mutex));
180
181         if (blk == 0)
182                 return NULL;
183
184         bh = ldiskfs_bread(NULL, inode, blk, 0, &err);
185         if (bh == NULL) {
186                 CERROR("%.16s: cannot load idle blocks, blk = %u, err = %d\n",
187                        LDISKFS_SB(inode->i_sb)->s_es->s_volume_name, blk, err);
188                 c->ic_idle_failed = 1;
189                 return ERR_PTR(err);
190         }
191
192         head = (struct iam_idle_head *)(bh->b_data);
193         if (le16_to_cpu(head->iih_magic) != IAM_IDLE_HEADER_MAGIC) {
194                 CERROR("%.16s: invalid idle block head, blk = %u, magic = %d\n",
195                        LDISKFS_SB(inode->i_sb)->s_es->s_volume_name, blk,
196                        le16_to_cpu(head->iih_magic));
197                 brelse(bh);
198                 c->ic_idle_failed = 1;
199                 return ERR_PTR(-EBADF);
200         }
201
202         return bh;
203 }
204
205 /*
206  * Determine format of given container. This is done by scanning list of
207  * registered formats and calling ->if_guess() method of each in turn.
208  */
209 static int iam_format_guess(struct iam_container *c)
210 {
211         int result;
212         struct iam_format *fmt;
213
214         /*
215          * XXX temporary initialization hook.
216          */
217         {
218                 static int initialized = 0;
219
220                 if (!initialized) {
221                         iam_lvar_format_init();
222                         iam_lfix_format_init();
223                         initialized = 1;
224                 }
225         }
226
227         result = -ENOENT;
228         list_for_each_entry(fmt, &iam_formats, if_linkage) {
229                 result = fmt->if_guess(c);
230                 if (result == 0)
231                         break;
232         }
233
234         if (result == 0) {
235                 struct buffer_head *bh;
236                 __u32 *idle_blocks;
237
238                 LASSERT(c->ic_root_bh != NULL);
239
240                 idle_blocks = (__u32 *)(c->ic_root_bh->b_data +
241                                         c->ic_descr->id_root_gap +
242                                         sizeof(struct dx_countlimit));
243                 mutex_lock(&c->ic_idle_mutex);
244                 bh = iam_load_idle_blocks(c, le32_to_cpu(*idle_blocks));
245                 if (bh != NULL && IS_ERR(bh))
246                         result = PTR_ERR(bh);
247                 else
248                         c->ic_idle_bh = bh;
249                 mutex_unlock(&c->ic_idle_mutex);
250         }
251
252         return result;
253 }
254
255 /*
256  * Initialize container @c.
257  */
258 int iam_container_init(struct iam_container *c,
259                        struct iam_descr *descr, struct inode *inode)
260 {
261         memset(c, 0, sizeof *c);
262         c->ic_descr  = descr;
263         c->ic_object = inode;
264         init_rwsem(&c->ic_sem);
265         dynlock_init(&c->ic_tree_lock);
266         mutex_init(&c->ic_idle_mutex);
267         return 0;
268 }
269
270 /*
271  * Determine container format.
272  */
273 int iam_container_setup(struct iam_container *c)
274 {
275         return iam_format_guess(c);
276 }
277
278 /*
279  * Finalize container @c, release all resources.
280  */
281 void iam_container_fini(struct iam_container *c)
282 {
283         brelse(c->ic_idle_bh);
284         c->ic_idle_bh = NULL;
285         brelse(c->ic_root_bh);
286         c->ic_root_bh = NULL;
287 }
288
289 void iam_path_init(struct iam_path *path, struct iam_container *c,
290                    struct iam_path_descr *pd)
291 {
292         memset(path, 0, sizeof *path);
293         path->ip_container = c;
294         path->ip_frame = path->ip_frames;
295         path->ip_data = pd;
296         path->ip_leaf.il_path = path;
297 }
298
299 static void iam_leaf_fini(struct iam_leaf *leaf);
300
301 void iam_path_release(struct iam_path *path)
302 {
303         int i;
304
305         for (i = 0; i < ARRAY_SIZE(path->ip_frames); i++) {
306                 if (path->ip_frames[i].bh != NULL) {
307                         path->ip_frames[i].at_shifted = 0;
308                         brelse(path->ip_frames[i].bh);
309                         path->ip_frames[i].bh = NULL;
310                 }
311         }
312 }
313
314 void iam_path_fini(struct iam_path *path)
315 {
316         iam_leaf_fini(&path->ip_leaf);
317         iam_path_release(path);
318 }
319
320
321 void iam_path_compat_init(struct iam_path_compat *path, struct inode *inode)
322 {
323         int i;
324
325         path->ipc_hinfo = &path->ipc_hinfo_area;
326         for (i = 0; i < ARRAY_SIZE(path->ipc_scratch); ++i)
327                 path->ipc_descr.ipd_key_scratch[i] =
328                         (struct iam_ikey *)&path->ipc_scratch[i];
329
330         iam_path_init(&path->ipc_path, &path->ipc_container, &path->ipc_descr);
331 }
332
333 void iam_path_compat_fini(struct iam_path_compat *path)
334 {
335         iam_path_fini(&path->ipc_path);
336 }
337
338 /*
339  * Helper function initializing iam_path_descr and its key scratch area.
340  */
341 struct iam_path_descr *iam_ipd_alloc(void *area, int keysize)
342 {
343         struct iam_path_descr *ipd;
344         void *karea;
345         int i;
346
347         ipd = area;
348         karea = ipd + 1;
349         for (i = 0; i < ARRAY_SIZE(ipd->ipd_key_scratch); ++i, karea += keysize)
350                 ipd->ipd_key_scratch[i] = karea;
351         return ipd;
352 }
353
354 void iam_ipd_free(struct iam_path_descr *ipd)
355 {
356 }
357
358 int iam_node_read(struct iam_container *c, iam_ptr_t ptr,
359                   handle_t *h, struct buffer_head **bh)
360 {
361         int result = 0;
362
363         /* NB: it can be called by iam_lfix_guess() which is still at
364          * very early stage, c->ic_root_bh and c->ic_descr->id_ops
365          * haven't been intialized yet.
366          * Also, we don't have this for IAM dir.
367          */
368         if (c->ic_root_bh != NULL &&
369             c->ic_descr->id_ops->id_root_ptr(c) == ptr) {
370                 get_bh(c->ic_root_bh);
371                 *bh = c->ic_root_bh;
372                 return 0;
373         }
374
375         *bh = ldiskfs_bread(h, c->ic_object, (int)ptr, 0, &result);
376         if (*bh == NULL)
377                 result = -EIO;
378         return result;
379 }
380
381 /*
382  * Return pointer to current leaf record. Pointer is valid while corresponding
383  * leaf node is locked and pinned.
384  */
385 static struct iam_rec *iam_leaf_rec(const struct iam_leaf *leaf)
386 {
387         return iam_leaf_ops(leaf)->rec(leaf);
388 }
389
390 /*
391  * Return pointer to the current leaf key. This function returns pointer to
392  * the key stored in node.
393  *
394  * Caller should assume that returned pointer is only valid while leaf node is
395  * pinned and locked.
396  */
397 static struct iam_key *iam_leaf_key(const struct iam_leaf *leaf)
398 {
399         return iam_leaf_ops(leaf)->key(leaf);
400 }
401
402 static int iam_leaf_key_size(const struct iam_leaf *leaf)
403 {
404         return iam_leaf_ops(leaf)->key_size(leaf);
405 }
406
407 static struct iam_ikey *iam_leaf_ikey(const struct iam_leaf *leaf,
408                                       struct iam_ikey *key)
409 {
410         return iam_leaf_ops(leaf)->ikey(leaf, key);
411 }
412
413 static int iam_leaf_keycmp(const struct iam_leaf *leaf,
414                            const struct iam_key *key)
415 {
416         return iam_leaf_ops(leaf)->key_cmp(leaf, key);
417 }
418
419 static int iam_leaf_keyeq(const struct iam_leaf *leaf,
420                           const struct iam_key *key)
421 {
422         return iam_leaf_ops(leaf)->key_eq(leaf, key);
423 }
424
425 #if LDISKFS_INVARIANT_ON
426 static int iam_leaf_check(struct iam_leaf *leaf);
427 extern int dx_node_check(struct iam_path *p, struct iam_frame *f);
428
429 static int iam_path_check(struct iam_path *p)
430 {
431         int i;
432         int result;
433         struct iam_frame *f;
434         struct iam_descr *param;
435
436         result = 1;
437         param = iam_path_descr(p);
438         for (i = 0; result && i < ARRAY_SIZE(p->ip_frames); ++i) {
439                 f = &p->ip_frames[i];
440                 if (f->bh != NULL) {
441                         result = dx_node_check(p, f);
442                         if (result)
443                                 result = !param->id_ops->id_node_check(p, f);
444                 }
445         }
446         if (result && p->ip_leaf.il_bh != NULL)
447                 result = iam_leaf_check(&p->ip_leaf);
448         if (result == 0) {
449                 ldiskfs_std_error(iam_path_obj(p)->i_sb, result);
450         }
451         return result;
452 }
453 #endif
454
455 static int iam_leaf_load(struct iam_path *path)
456 {
457         iam_ptr_t block;
458         int err;
459         struct iam_container *c;
460         struct buffer_head   *bh;
461         struct iam_leaf      *leaf;
462         struct iam_descr     *descr;
463
464         c     = path->ip_container;
465         leaf  = &path->ip_leaf;
466         descr = iam_path_descr(path);
467         block = path->ip_frame->leaf;
468         if (block == 0) {
469                 /* XXX bug 11027 */
470                 printk(KERN_EMERG "wrong leaf: %lu %d [%p %p %p]\n",
471                        (long unsigned)path->ip_frame->leaf,
472                        dx_get_count(dx_node_get_entries(path, path->ip_frame)),
473                        path->ip_frames[0].bh, path->ip_frames[1].bh,
474                        path->ip_frames[2].bh);
475         }
476         err = descr->id_ops->id_node_read(c, block, NULL, &bh);
477         if (err == 0) {
478                 leaf->il_bh = bh;
479                 leaf->il_curidx = block;
480                 err = iam_leaf_ops(leaf)->init(leaf);
481                 assert_inv(ergo(err == 0, iam_leaf_check(leaf)));
482         }
483         return err;
484 }
485
486 static void iam_unlock_htree(struct iam_container *ic,
487                              struct dynlock_handle *lh)
488 {
489         if (lh != NULL)
490                 dynlock_unlock(&ic->ic_tree_lock, lh);
491 }
492
493
494 static void iam_leaf_unlock(struct iam_leaf *leaf)
495 {
496         if (leaf->il_lock != NULL) {
497                 iam_unlock_htree(iam_leaf_container(leaf),
498                                  leaf->il_lock);
499                 do_corr(schedule());
500                 leaf->il_lock = NULL;
501         }
502 }
503
504 static void iam_leaf_fini(struct iam_leaf *leaf)
505 {
506         if (leaf->il_path != NULL) {
507                 iam_leaf_unlock(leaf);
508                 assert_inv(ergo(leaf->il_bh != NULL, iam_leaf_check(leaf)));
509                 iam_leaf_ops(leaf)->fini(leaf);
510                 if (leaf->il_bh) {
511                         brelse(leaf->il_bh);
512                         leaf->il_bh = NULL;
513                         leaf->il_curidx = 0;
514                 }
515         }
516 }
517
518 static void iam_leaf_start(struct iam_leaf *folio)
519 {
520         iam_leaf_ops(folio)->start(folio);
521 }
522
523 void iam_leaf_next(struct iam_leaf *folio)
524 {
525         iam_leaf_ops(folio)->next(folio);
526 }
527
528 static void iam_leaf_rec_add(struct iam_leaf *leaf, const struct iam_key *key,
529                              const struct iam_rec *rec)
530 {
531         iam_leaf_ops(leaf)->rec_add(leaf, key, rec);
532 }
533
534 static void iam_rec_del(struct iam_leaf *leaf, int shift)
535 {
536         iam_leaf_ops(leaf)->rec_del(leaf, shift);
537 }
538
539 int iam_leaf_at_end(const struct iam_leaf *leaf)
540 {
541         return iam_leaf_ops(leaf)->at_end(leaf);
542 }
543
544 static void iam_leaf_split(struct iam_leaf *l, struct buffer_head **bh,
545                            iam_ptr_t nr)
546 {
547         iam_leaf_ops(l)->split(l, bh, nr);
548 }
549
550 static inline int iam_leaf_empty(struct iam_leaf *l)
551 {
552         return iam_leaf_ops(l)->leaf_empty(l);
553 }
554
555 int iam_leaf_can_add(const struct iam_leaf *l,
556                      const struct iam_key *k, const struct iam_rec *r)
557 {
558         return iam_leaf_ops(l)->can_add(l, k, r);
559 }
560
561 #if LDISKFS_INVARIANT_ON
562 static int iam_leaf_check(struct iam_leaf *leaf)
563 {
564         return 1;
565 #if 0
566         struct iam_lentry    *orig;
567         struct iam_path      *path;
568         struct iam_container *bag;
569         struct iam_ikey       *k0;
570         struct iam_ikey       *k1;
571         int result;
572         int first;
573
574         orig = leaf->il_at;
575         path = iam_leaf_path(leaf);
576         bag  = iam_leaf_container(leaf);
577
578         result = iam_leaf_ops(leaf)->init(leaf);
579         if (result != 0)
580                 return result;
581
582         first = 1;
583         iam_leaf_start(leaf);
584         k0 = iam_path_ikey(path, 0);
585         k1 = iam_path_ikey(path, 1);
586         while (!iam_leaf_at_end(leaf)) {
587                 iam_ikeycpy(bag, k0, k1);
588                 iam_ikeycpy(bag, k1, iam_leaf_ikey(leaf, k1));
589                 if (!first && iam_ikeycmp(bag, k0, k1) > 0) {
590                         return 0;
591                 }
592                 first = 0;
593                 iam_leaf_next(leaf);
594         }
595         leaf->il_at = orig;
596         return 1;
597 #endif
598 }
599 #endif
600
601 static int iam_txn_dirty(handle_t *handle,
602                          struct iam_path *path, struct buffer_head *bh)
603 {
604         int result;
605
606         result = ldiskfs_handle_dirty_metadata(handle, NULL, bh);
607         if (result != 0)
608                 ldiskfs_std_error(iam_path_obj(path)->i_sb, result);
609         return result;
610 }
611
612 static int iam_txn_add(handle_t *handle,
613                        struct iam_path *path, struct buffer_head *bh)
614 {
615         int result;
616
617         result = ldiskfs_journal_get_write_access(handle, bh);
618         if (result != 0)
619                 ldiskfs_std_error(iam_path_obj(path)->i_sb, result);
620         return result;
621 }
622
623 /***********************************************************************/
624 /* iterator interface                                                  */
625 /***********************************************************************/
626
627 static enum iam_it_state it_state(const struct iam_iterator *it)
628 {
629         return it->ii_state;
630 }
631
632 /*
633  * Helper function returning scratch key.
634  */
635 static struct iam_container *iam_it_container(const struct iam_iterator *it)
636 {
637         return it->ii_path.ip_container;
638 }
639
640 static inline int it_keycmp(const struct iam_iterator *it,
641                             const struct iam_key *k)
642 {
643         return iam_leaf_keycmp(&it->ii_path.ip_leaf, k);
644 }
645
646 static inline int it_keyeq(const struct iam_iterator *it,
647                            const struct iam_key *k)
648 {
649         return iam_leaf_keyeq(&it->ii_path.ip_leaf, k);
650 }
651
652 static int it_ikeycmp(const struct iam_iterator *it, const struct iam_ikey *ik)
653 {
654         return iam_ikeycmp(it->ii_path.ip_container,
655                            iam_leaf_ikey(&it->ii_path.ip_leaf,
656                                          iam_path_ikey(&it->ii_path, 0)), ik);
657 }
658
659 static inline int it_at_rec(const struct iam_iterator *it)
660 {
661         return !iam_leaf_at_end(&it->ii_path.ip_leaf);
662 }
663
664 static inline int it_before(const struct iam_iterator *it)
665 {
666         return it_state(it) == IAM_IT_SKEWED && it_at_rec(it);
667 }
668
669 /*
670  * Helper wrapper around iam_it_get(): returns 0 (success) only when record
671  * with exactly the same key as asked is found.
672  */
673 static int iam_it_get_exact(struct iam_iterator *it, const struct iam_key *k)
674 {
675         int result;
676
677         result = iam_it_get(it, k);
678         if (result > 0)
679                 result = 0;
680         else if (result == 0)
681                 /*
682                  * Return -ENOENT if cursor is located above record with a key
683                  * different from one specified, or in the empty leaf.
684                  *
685                  * XXX returning -ENOENT only works if iam_it_get() never
686                  * returns -ENOENT as a legitimate error.
687                  */
688                 result = -ENOENT;
689         return result;
690 }
691
692 void iam_container_write_lock(struct iam_container *ic)
693 {
694         down_write(&ic->ic_sem);
695 }
696
697 void iam_container_write_unlock(struct iam_container *ic)
698 {
699         up_write(&ic->ic_sem);
700 }
701
702 void iam_container_read_lock(struct iam_container *ic)
703 {
704         down_read(&ic->ic_sem);
705 }
706
707 void iam_container_read_unlock(struct iam_container *ic)
708 {
709         up_read(&ic->ic_sem);
710 }
711
712 /*
713  * Initialize iterator to IAM_IT_DETACHED state.
714  *
715  * postcondition: it_state(it) == IAM_IT_DETACHED
716  */
717 int  iam_it_init(struct iam_iterator *it, struct iam_container *c, __u32 flags,
718                  struct iam_path_descr *pd)
719 {
720         memset(it, 0, sizeof *it);
721         it->ii_flags  = flags;
722         it->ii_state  = IAM_IT_DETACHED;
723         iam_path_init(&it->ii_path, c, pd);
724         return 0;
725 }
726
727 /*
728  * Finalize iterator and release all resources.
729  *
730  * precondition: it_state(it) == IAM_IT_DETACHED
731  */
732 void iam_it_fini(struct iam_iterator *it)
733 {
734         assert_corr(it_state(it) == IAM_IT_DETACHED);
735         iam_path_fini(&it->ii_path);
736 }
737
738 /*
739  * this locking primitives are used to protect parts
740  * of dir's htree. protection unit is block: leaf or index
741  */
742 static struct dynlock_handle *iam_lock_htree(struct iam_container *ic,
743                                              unsigned long value,
744                                              enum dynlock_type lt)
745 {
746         return dynlock_lock(&ic->ic_tree_lock, value, lt, GFP_NOFS);
747 }
748
749 static int iam_index_lock(struct iam_path *path, struct dynlock_handle **lh)
750 {
751         struct iam_frame *f;
752
753         for (f = path->ip_frame; f >= path->ip_frames; --f, ++lh) {
754                 do_corr(schedule());
755                 *lh = iam_lock_htree(path->ip_container, f->curidx, DLT_READ);
756                 if (*lh == NULL)
757                         return -ENOMEM;
758         }
759         return 0;
760 }
761
762 /*
763  * Fast check for frame consistency.
764  */
765 static int iam_check_fast(struct iam_path *path, struct iam_frame *frame)
766 {
767         struct iam_container *bag;
768         struct iam_entry *next;
769         struct iam_entry *last;
770         struct iam_entry *entries;
771         struct iam_entry *at;
772
773         bag     = path->ip_container;
774         at      = frame->at;
775         entries = frame->entries;
776         last    = iam_entry_shift(path, entries, dx_get_count(entries) - 1);
777
778         if (unlikely(at > last))
779                 return -EAGAIN;
780
781         if (unlikely(dx_get_block(path, at) != frame->leaf))
782                 return -EAGAIN;
783
784         if (unlikely(iam_ikeycmp(bag, iam_ikey_at(path, at),
785                                  path->ip_ikey_target) > 0))
786                 return -EAGAIN;
787
788         next = iam_entry_shift(path, at, +1);
789         if (next <= last) {
790                 if (unlikely(iam_ikeycmp(bag, iam_ikey_at(path, next),
791                                          path->ip_ikey_target) <= 0))
792                         return -EAGAIN;
793         }
794         return 0;
795 }
796
797 int dx_index_is_compat(struct iam_path *path)
798 {
799         return iam_path_descr(path) == NULL;
800 }
801
802 /*
803  * dx_find_position
804  *
805  * search position of specified hash in index
806  *
807  */
808
809 static struct iam_entry *iam_find_position(struct iam_path *path,
810                                            struct iam_frame *frame)
811 {
812         int count;
813         struct iam_entry *p;
814         struct iam_entry *q;
815         struct iam_entry *m;
816
817         count = dx_get_count(frame->entries);
818         assert_corr(count && count <= dx_get_limit(frame->entries));
819         p = iam_entry_shift(path, frame->entries,
820                             dx_index_is_compat(path) ? 1 : 2);
821         q = iam_entry_shift(path, frame->entries, count - 1);
822         while (p <= q) {
823                 m = iam_entry_shift(path, p, iam_entry_diff(path, q, p) / 2);
824                 if (iam_ikeycmp(path->ip_container, iam_ikey_at(path, m),
825                                 path->ip_ikey_target) > 0)
826                         q = iam_entry_shift(path, m, -1);
827                 else
828                         p = iam_entry_shift(path, m, +1);
829         }
830         return iam_entry_shift(path, p, -1);
831 }
832
833
834
835 static iam_ptr_t iam_find_ptr(struct iam_path *path, struct iam_frame *frame)
836 {
837         return dx_get_block(path, iam_find_position(path, frame));
838 }
839
840 void iam_insert_key(struct iam_path *path, struct iam_frame *frame,
841                     const struct iam_ikey *key, iam_ptr_t ptr)
842 {
843         struct iam_entry *entries = frame->entries;
844         struct iam_entry *new = iam_entry_shift(path, frame->at, +1);
845         int count = dx_get_count(entries);
846
847         /*
848          * Unfortunately we cannot assert this, as this function is sometimes
849          * called by VFS under i_sem and without pdirops lock.
850          */
851         assert_corr(1 || iam_frame_is_locked(path, frame));
852         assert_corr(count < dx_get_limit(entries));
853         assert_corr(frame->at < iam_entry_shift(path, entries, count));
854         assert_inv(dx_node_check(path, frame));
855
856         memmove(iam_entry_shift(path, new, 1), new,
857                 (char *)iam_entry_shift(path, entries, count) - (char *)new);
858         dx_set_ikey(path, new, key);
859         dx_set_block(path, new, ptr);
860         dx_set_count(entries, count + 1);
861         assert_inv(dx_node_check(path, frame));
862 }
863
864 void iam_insert_key_lock(struct iam_path *path, struct iam_frame *frame,
865                          const struct iam_ikey *key, iam_ptr_t ptr)
866 {
867         iam_lock_bh(frame->bh);
868         iam_insert_key(path, frame, key, ptr);
869         iam_unlock_bh(frame->bh);
870 }
871 /*
872  * returns 0 if path was unchanged, -EAGAIN otherwise.
873  */
874 static int iam_check_path(struct iam_path *path, struct iam_frame *frame)
875 {
876         int equal;
877
878         iam_lock_bh(frame->bh);
879         equal = iam_check_fast(path, frame) == 0 ||
880                 frame->leaf == iam_find_ptr(path, frame);
881         DX_DEVAL(iam_lock_stats.dls_bh_again += !equal);
882         iam_unlock_bh(frame->bh);
883
884         return equal ? 0 : -EAGAIN;
885 }
886
887 static int iam_lookup_try(struct iam_path *path)
888 {
889         u32 ptr;
890         int err = 0;
891         int i;
892
893         struct iam_descr *param;
894         struct iam_frame *frame;
895         struct iam_container *c;
896
897         param = iam_path_descr(path);
898         c = path->ip_container;
899
900         ptr = param->id_ops->id_root_ptr(c);
901         for (frame = path->ip_frames, i = 0; i <= path->ip_indirect;
902              ++frame, ++i) {
903                 err = param->id_ops->id_node_read(c, (iam_ptr_t)ptr, NULL,
904                                                   &frame->bh);
905                 do_corr(schedule());
906
907                 iam_lock_bh(frame->bh);
908                 /*
909                  * node must be initialized under bh lock because concurrent
910                  * creation procedure may change it and iam_lookup_try() will
911                  * see obsolete tree height. -bzzz
912                  */
913                 if (err != 0)
914                         break;
915
916                 if (LDISKFS_INVARIANT_ON) {
917                         err = param->id_ops->id_node_check(path, frame);
918                         if (err != 0)
919                                 break;
920                 }
921
922                 err = param->id_ops->id_node_load(path, frame);
923                 if (err != 0)
924                         break;
925
926                 assert_inv(dx_node_check(path, frame));
927                 /*
928                  * splitting may change root index block and move hash we're
929                  * looking for into another index block so, we have to check
930                  * this situation and repeat from begining if path got changed
931                  * -bzzz
932                  */
933                 if (i > 0) {
934                         err = iam_check_path(path, frame - 1);
935                         if (err != 0)
936                                 break;
937                 }
938
939                 frame->at = iam_find_position(path, frame);
940                 frame->curidx = ptr;
941                 frame->leaf = ptr = dx_get_block(path, frame->at);
942
943                 iam_unlock_bh(frame->bh);
944                 do_corr(schedule());
945         }
946         if (err != 0)
947                 iam_unlock_bh(frame->bh);
948         path->ip_frame = --frame;
949         return err;
950 }
951
952 static int __iam_path_lookup(struct iam_path *path)
953 {
954         int err;
955         int i;
956
957         for (i = 0; i < DX_MAX_TREE_HEIGHT; ++ i)
958                 assert(path->ip_frames[i].bh == NULL);
959
960         do {
961                 err = iam_lookup_try(path);
962                 do_corr(schedule());
963                 if (err != 0)
964                         iam_path_fini(path);
965         } while (err == -EAGAIN);
966
967         return err;
968 }
969
970 /*
971  * returns 0 if path was unchanged, -EAGAIN otherwise.
972  */
973 static int iam_check_full_path(struct iam_path *path, int search)
974 {
975         struct iam_frame *bottom;
976         struct iam_frame *scan;
977         int i;
978         int result;
979
980         do_corr(schedule());
981
982         for (bottom = path->ip_frames, i = 0;
983              i < DX_MAX_TREE_HEIGHT && bottom->bh != NULL; ++bottom, ++i) {
984                 ; /* find last filled in frame */
985         }
986
987         /*
988          * Lock frames, bottom to top.
989          */
990         for (scan = bottom - 1; scan >= path->ip_frames; --scan)
991                 iam_lock_bh(scan->bh);
992         /*
993          * Check them top to bottom.
994          */
995         result = 0;
996         for (scan = path->ip_frames; scan < bottom; ++scan) {
997                 struct iam_entry *pos;
998
999                 if (search) {
1000                         if (iam_check_fast(path, scan) == 0)
1001                                 continue;
1002
1003                         pos = iam_find_position(path, scan);
1004                         if (scan->leaf != dx_get_block(path, pos)) {
1005                                 result = -EAGAIN;
1006                                 break;
1007                         }
1008                         scan->at = pos;
1009                 } else {
1010                         pos = iam_entry_shift(path, scan->entries,
1011                                               dx_get_count(scan->entries) - 1);
1012                         if (scan->at > pos ||
1013                             scan->leaf != dx_get_block(path, scan->at)) {
1014                                 result = -EAGAIN;
1015                                 break;
1016                         }
1017                 }
1018         }
1019
1020         /*
1021          * Unlock top to bottom.
1022          */
1023         for (scan = path->ip_frames; scan < bottom; ++scan)
1024                 iam_unlock_bh(scan->bh);
1025         DX_DEVAL(iam_lock_stats.dls_bh_full_again += !!result);
1026         do_corr(schedule());
1027
1028         return result;
1029 }
1030
1031
1032 /*
1033  * Performs path lookup and returns with found leaf (if any) locked by htree
1034  * lock.
1035  */
1036 static int iam_lookup_lock(struct iam_path *path,
1037                            struct dynlock_handle **dl, enum dynlock_type lt)
1038 {
1039         int result;
1040
1041         while ((result = __iam_path_lookup(path)) == 0) {
1042                 do_corr(schedule());
1043                 *dl = iam_lock_htree(path->ip_container, path->ip_frame->leaf,
1044                                      lt);
1045                 if (*dl == NULL) {
1046                         iam_path_fini(path);
1047                         result = -ENOMEM;
1048                         break;
1049                 }
1050                 do_corr(schedule());
1051                 /*
1052                  * while locking leaf we just found may get split so we need
1053                  * to check this -bzzz
1054                  */
1055                 if (iam_check_full_path(path, 1) == 0)
1056                         break;
1057                 iam_unlock_htree(path->ip_container, *dl);
1058                 *dl = NULL;
1059                 iam_path_fini(path);
1060         }
1061         return result;
1062 }
1063 /*
1064  * Performs tree top-to-bottom traversal starting from root, and loads leaf
1065  * node.
1066  */
1067 static int iam_path_lookup(struct iam_path *path, int index)
1068 {
1069         struct iam_container *c;
1070         struct iam_leaf  *leaf;
1071         int result;
1072
1073         c = path->ip_container;
1074         leaf = &path->ip_leaf;
1075         result = iam_lookup_lock(path, &leaf->il_lock, DLT_WRITE);
1076         assert_inv(iam_path_check(path));
1077         do_corr(schedule());
1078         if (result == 0) {
1079                 result = iam_leaf_load(path);
1080                 assert_inv(ergo(result == 0, iam_leaf_check(leaf)));
1081                 if (result == 0) {
1082                         do_corr(schedule());
1083                         if (index)
1084                                 result = iam_leaf_ops(leaf)->
1085                                         ilookup(leaf, path->ip_ikey_target);
1086                         else
1087                                 result = iam_leaf_ops(leaf)->
1088                                         lookup(leaf, path->ip_key_target);
1089                         do_corr(schedule());
1090                 }
1091                 if (result < 0)
1092                         iam_leaf_unlock(leaf);
1093         }
1094         return result;
1095 }
1096
1097 /*
1098  * Common part of iam_it_{i,}get().
1099  */
1100 static int __iam_it_get(struct iam_iterator *it, int index)
1101 {
1102         int result;
1103         assert_corr(it_state(it) == IAM_IT_DETACHED);
1104
1105         result = iam_path_lookup(&it->ii_path, index);
1106         if (result >= 0) {
1107                 int collision;
1108
1109                 collision = result & IAM_LOOKUP_LAST;
1110                 switch (result & ~IAM_LOOKUP_LAST) {
1111                 case IAM_LOOKUP_EXACT:
1112                         result = +1;
1113                         it->ii_state = IAM_IT_ATTACHED;
1114                         break;
1115                 case IAM_LOOKUP_OK:
1116                         result = 0;
1117                         it->ii_state = IAM_IT_ATTACHED;
1118                         break;
1119                 case IAM_LOOKUP_BEFORE:
1120                 case IAM_LOOKUP_EMPTY:
1121                         result = 0;
1122                         it->ii_state = IAM_IT_SKEWED;
1123                         break;
1124                 default:
1125                         assert(0);
1126                 }
1127                 result |= collision;
1128         }
1129         /*
1130          * See iam_it_get_exact() for explanation.
1131          */
1132         assert_corr(result != -ENOENT);
1133         return result;
1134 }
1135
1136 /*
1137  * Correct hash, but not the same key was found, iterate through hash
1138  * collision chain, looking for correct record.
1139  */
1140 static int iam_it_collision(struct iam_iterator *it)
1141 {
1142         int result;
1143
1144         assert(ergo(it_at_rec(it), !it_keyeq(it, it->ii_path.ip_key_target)));
1145
1146         while ((result = iam_it_next(it)) == 0) {
1147                 do_corr(schedule());
1148                 if (it_ikeycmp(it, it->ii_path.ip_ikey_target) != 0)
1149                         return -ENOENT;
1150                 if (it_keyeq(it, it->ii_path.ip_key_target))
1151                         return 0;
1152         }
1153         return result;
1154 }
1155
1156 /*
1157  * Attach iterator. After successful completion, @it points to record with
1158  * least key not larger than @k.
1159  *
1160  * Return value: 0: positioned on existing record,
1161  *             +ve: exact position found,
1162  *             -ve: error.
1163  *
1164  * precondition:  it_state(it) == IAM_IT_DETACHED
1165  * postcondition: ergo(result == 0 && it_state(it) == IAM_IT_ATTACHED,
1166  *                     it_keycmp(it, k) <= 0)
1167  */
1168 int iam_it_get(struct iam_iterator *it, const struct iam_key *k)
1169 {
1170         int result;
1171         assert_corr(it_state(it) == IAM_IT_DETACHED);
1172
1173         it->ii_path.ip_ikey_target = NULL;
1174         it->ii_path.ip_key_target  = k;
1175
1176         result = __iam_it_get(it, 0);
1177
1178         if (result == IAM_LOOKUP_LAST) {
1179                 result = iam_it_collision(it);
1180                 if (result != 0) {
1181                         iam_it_put(it);
1182                         iam_it_fini(it);
1183                         result = __iam_it_get(it, 0);
1184                 } else
1185                         result = +1;
1186         }
1187         if (result > 0)
1188                 result &= ~IAM_LOOKUP_LAST;
1189
1190         assert_corr(ergo(result > 0, it_keycmp(it, k) == 0));
1191         assert_corr(ergo(result == 0 && it_state(it) == IAM_IT_ATTACHED,
1192                          it_keycmp(it, k) <= 0));
1193         return result;
1194 }
1195
1196 /*
1197  * Attach iterator by index key.
1198  */
1199 static int iam_it_iget(struct iam_iterator *it, const struct iam_ikey *k)
1200 {
1201         assert_corr(it_state(it) == IAM_IT_DETACHED);
1202
1203         it->ii_path.ip_ikey_target = k;
1204         return __iam_it_get(it, 1) & ~IAM_LOOKUP_LAST;
1205 }
1206
1207 /*
1208  * Attach iterator, and assure it points to the record (not skewed).
1209  *
1210  * Return value: 0: positioned on existing record,
1211  *             +ve: exact position found,
1212  *             -ve: error.
1213  *
1214  * precondition:  it_state(it) == IAM_IT_DETACHED &&
1215  *                !(it->ii_flags&IAM_IT_WRITE)
1216  * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED)
1217  */
1218 int iam_it_get_at(struct iam_iterator *it, const struct iam_key *k)
1219 {
1220         int result;
1221         assert_corr(it_state(it) == IAM_IT_DETACHED &&
1222                     !(it->ii_flags&IAM_IT_WRITE));
1223         result = iam_it_get(it, k);
1224         if (result == 0) {
1225                 if (it_state(it) != IAM_IT_ATTACHED) {
1226                         assert_corr(it_state(it) == IAM_IT_SKEWED);
1227                         result = iam_it_next(it);
1228                 }
1229         }
1230         assert_corr(ergo(result >= 0, it_state(it) == IAM_IT_ATTACHED));
1231         return result;
1232 }
1233
1234 /*
1235  * Duplicates iterator.
1236  *
1237  * postcondition: it_state(dst) == it_state(src) &&
1238  *                iam_it_container(dst) == iam_it_container(src) &&
1239  *                dst->ii_flags = src->ii_flags &&
1240  *                ergo(it_state(src) == IAM_IT_ATTACHED,
1241  *                     iam_it_rec_get(dst) == iam_it_rec_get(src) &&
1242  *                     iam_it_key_get(dst) == iam_it_key_get(src))
1243  */
1244 void iam_it_dup(struct iam_iterator *dst, const struct iam_iterator *src)
1245 {
1246         dst->ii_flags     = src->ii_flags;
1247         dst->ii_state     = src->ii_state;
1248         /* XXX not yet. iam_path_dup(&dst->ii_path, &src->ii_path); */
1249         /*
1250          * XXX: duplicate lock.
1251          */
1252         assert_corr(it_state(dst) == it_state(src));
1253         assert_corr(iam_it_container(dst) == iam_it_container(src));
1254         assert_corr(dst->ii_flags = src->ii_flags);
1255         assert_corr(ergo(it_state(src) == IAM_IT_ATTACHED,
1256                     iam_it_rec_get(dst) == iam_it_rec_get(src) &&
1257                     iam_it_key_get(dst) == iam_it_key_get(src)));
1258
1259 }
1260
1261 /*
1262  * Detach iterator. Does nothing it detached state.
1263  *
1264  * postcondition: it_state(it) == IAM_IT_DETACHED
1265  */
1266 void iam_it_put(struct iam_iterator *it)
1267 {
1268         if (it->ii_state != IAM_IT_DETACHED) {
1269                 it->ii_state = IAM_IT_DETACHED;
1270                 iam_leaf_fini(&it->ii_path.ip_leaf);
1271         }
1272 }
1273
1274 static struct iam_ikey *iam_it_ikey_get(const struct iam_iterator *it,
1275                                         struct iam_ikey *ikey);
1276
1277
1278 /*
1279  * This function increments the frame pointer to search the next leaf
1280  * block, and reads in the necessary intervening nodes if the search
1281  * should be necessary.  Whether or not the search is necessary is
1282  * controlled by the hash parameter.  If the hash value is even, then
1283  * the search is only continued if the next block starts with that
1284  * hash value.  This is used if we are searching for a specific file.
1285  *
1286  * If the hash value is HASH_NB_ALWAYS, then always go to the next block.
1287  *
1288  * This function returns 1 if the caller should continue to search,
1289  * or 0 if it should not.  If there is an error reading one of the
1290  * index blocks, it will a negative error code.
1291  *
1292  * If start_hash is non-null, it will be filled in with the starting
1293  * hash of the next page.
1294  */
1295 static int iam_htree_advance(struct inode *dir, __u32 hash,
1296                               struct iam_path *path, __u32 *start_hash,
1297                               int compat)
1298 {
1299         struct iam_frame *p;
1300         struct buffer_head *bh;
1301         int err, num_frames = 0;
1302         __u32 bhash;
1303
1304         p = path->ip_frame;
1305         /*
1306          * Find the next leaf page by incrementing the frame pointer.
1307          * If we run out of entries in the interior node, loop around and
1308          * increment pointer in the parent node.  When we break out of
1309          * this loop, num_frames indicates the number of interior
1310          * nodes need to be read.
1311          */
1312         while (1) {
1313                 do_corr(schedule());
1314                 iam_lock_bh(p->bh);
1315                 if (p->at_shifted)
1316                         p->at_shifted = 0;
1317                 else
1318                         p->at = iam_entry_shift(path, p->at, +1);
1319                 if (p->at < iam_entry_shift(path, p->entries,
1320                                             dx_get_count(p->entries))) {
1321                         p->leaf = dx_get_block(path, p->at);
1322                         iam_unlock_bh(p->bh);
1323                         break;
1324                 }
1325                 iam_unlock_bh(p->bh);
1326                 if (p == path->ip_frames)
1327                         return 0;
1328                 num_frames++;
1329                 --p;
1330         }
1331
1332         if (compat) {
1333                 /*
1334                  * Htree hash magic.
1335                  */
1336         /*
1337          * If the hash is 1, then continue only if the next page has a
1338          * continuation hash of any value.  This is used for readdir
1339          * handling.  Otherwise, check to see if the hash matches the
1340          * desired contiuation hash.  If it doesn't, return since
1341          * there's no point to read in the successive index pages.
1342          */
1343                 dx_get_ikey(path, p->at, (struct iam_ikey *)&bhash);
1344         if (start_hash)
1345                 *start_hash = bhash;
1346         if ((hash & 1) == 0) {
1347                 if ((bhash & ~1) != hash)
1348                         return 0;
1349         }
1350         }
1351         /*
1352          * If the hash is HASH_NB_ALWAYS, we always go to the next
1353          * block so no check is necessary
1354          */
1355         while (num_frames--) {
1356                 iam_ptr_t idx;
1357
1358                 do_corr(schedule());
1359                 iam_lock_bh(p->bh);
1360                 idx = p->leaf = dx_get_block(path, p->at);
1361                 iam_unlock_bh(p->bh);
1362                 err = iam_path_descr(path)->id_ops->
1363                         id_node_read(path->ip_container, idx, NULL, &bh);
1364                 if (err != 0)
1365                         return err; /* Failure */
1366                 ++p;
1367                 brelse(p->bh);
1368                 assert_corr(p->bh != bh);
1369                 p->bh = bh;
1370                 p->entries = dx_node_get_entries(path, p);
1371                 p->at = iam_entry_shift(path, p->entries, !compat);
1372                 assert_corr(p->curidx != idx);
1373                 p->curidx = idx;
1374                 iam_lock_bh(p->bh);
1375                 assert_corr(p->leaf != dx_get_block(path, p->at));
1376                 p->leaf = dx_get_block(path, p->at);
1377                 iam_unlock_bh(p->bh);
1378                 assert_inv(dx_node_check(path, p));
1379         }
1380         return 1;
1381 }
1382
1383
1384 static inline int iam_index_advance(struct iam_path *path)
1385 {
1386         return iam_htree_advance(iam_path_obj(path), 0, path, NULL, 0);
1387 }
1388
1389 static void iam_unlock_array(struct iam_container *ic,
1390                              struct dynlock_handle **lh)
1391 {
1392         int i;
1393
1394         for (i = 0; i < DX_MAX_TREE_HEIGHT; ++i, ++lh) {
1395                 if (*lh != NULL) {
1396                         iam_unlock_htree(ic, *lh);
1397                         *lh = NULL;
1398                 }
1399         }
1400 }
1401 /*
1402  * Advance index part of @path to point to the next leaf. Returns 1 on
1403  * success, 0, when end of container was reached. Leaf node is locked.
1404  */
1405 int iam_index_next(struct iam_container *c, struct iam_path *path)
1406 {
1407         iam_ptr_t cursor;
1408         struct dynlock_handle *lh[DX_MAX_TREE_HEIGHT] = { NULL, };
1409         int result;
1410         struct inode *object;
1411
1412         /*
1413          * Locking for iam_index_next()... is to be described.
1414          */
1415
1416         object = c->ic_object;
1417         cursor = path->ip_frame->leaf;
1418
1419         while (1) {
1420                 result = iam_index_lock(path, lh);
1421                 do_corr(schedule());
1422                 if (result < 0)
1423                         break;
1424
1425                 result = iam_check_full_path(path, 0);
1426                 if (result == 0 && cursor == path->ip_frame->leaf) {
1427                         result = iam_index_advance(path);
1428
1429                         assert_corr(result == 0 ||
1430                                     cursor != path->ip_frame->leaf);
1431                         break;
1432                 }
1433                 do {
1434                         iam_unlock_array(c, lh);
1435
1436                         iam_path_release(path);
1437                         do_corr(schedule());
1438
1439                         result = __iam_path_lookup(path);
1440                         if (result < 0)
1441                                 break;
1442
1443                         while (path->ip_frame->leaf != cursor) {
1444                                 do_corr(schedule());
1445
1446                                 result = iam_index_lock(path, lh);
1447                                 do_corr(schedule());
1448                                 if (result < 0)
1449                                         break;
1450
1451                                 result = iam_check_full_path(path, 0);
1452                                 if (result != 0)
1453                                         break;
1454
1455                                 result = iam_index_advance(path);
1456                                 if (result == 0) {
1457                                         CERROR("cannot find cursor : %u\n",
1458                                                 cursor);
1459                                         result = -EIO;
1460                                 }
1461                                 if (result < 0)
1462                                         break;
1463                                 result = iam_check_full_path(path, 0);
1464                                 if (result != 0)
1465                                         break;
1466                                 iam_unlock_array(c, lh);
1467                         }
1468                 } while (result == -EAGAIN);
1469                 if (result < 0)
1470                         break;
1471         }
1472         iam_unlock_array(c, lh);
1473         return result;
1474 }
1475
1476 /*
1477  * Move iterator one record right.
1478  *
1479  * Return value: 0: success,
1480  *              +1: end of container reached
1481  *             -ve: error
1482  *
1483  * precondition:  (it_state(it) == IAM_IT_ATTACHED ||
1484  *                 it_state(it) == IAM_IT_SKEWED) && it->ii_flags&IAM_IT_MOVE
1485  * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED) &&
1486  *                ergo(result >  0, it_state(it) == IAM_IT_DETACHED)
1487  */
1488 int iam_it_next(struct iam_iterator *it)
1489 {
1490         int result;
1491         struct iam_path      *path;
1492         struct iam_leaf      *leaf;
1493         do_corr(struct iam_ikey *ik_orig);
1494
1495         /* assert_corr(it->ii_flags&IAM_IT_MOVE); */
1496         assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1497                     it_state(it) == IAM_IT_SKEWED);
1498
1499         path = &it->ii_path;
1500         leaf = &path->ip_leaf;
1501
1502         assert_corr(iam_leaf_is_locked(leaf));
1503
1504         result = 0;
1505         do_corr(ik_orig = it_at_rec(it) ?
1506                 iam_it_ikey_get(it, iam_path_ikey(path, 2)) : NULL);
1507         if (it_before(it)) {
1508                 assert_corr(!iam_leaf_at_end(leaf));
1509                 it->ii_state = IAM_IT_ATTACHED;
1510         } else {
1511                 if (!iam_leaf_at_end(leaf))
1512                         /* advance within leaf node */
1513                         iam_leaf_next(leaf);
1514                 /*
1515                  * multiple iterations may be necessary due to empty leaves.
1516                  */
1517                 while (result == 0 && iam_leaf_at_end(leaf)) {
1518                         do_corr(schedule());
1519                         /* advance index portion of the path */
1520                         result = iam_index_next(iam_it_container(it), path);
1521                         assert_corr(iam_leaf_is_locked(leaf));
1522                         if (result == 1) {
1523                                 struct dynlock_handle *lh;
1524                                 lh = iam_lock_htree(iam_it_container(it),
1525                                                     path->ip_frame->leaf,
1526                                                     DLT_WRITE);
1527                                 if (lh != NULL) {
1528                                         iam_leaf_fini(leaf);
1529                                         leaf->il_lock = lh;
1530                                         result = iam_leaf_load(path);
1531                                         if (result == 0)
1532                                                 iam_leaf_start(leaf);
1533                                 } else
1534                                         result = -ENOMEM;
1535                         } else if (result == 0)
1536                                 /* end of container reached */
1537                                 result = +1;
1538                         if (result != 0)
1539                                 iam_it_put(it);
1540                 }
1541                 if (result == 0)
1542                         it->ii_state = IAM_IT_ATTACHED;
1543         }
1544         assert_corr(ergo(result == 0, it_state(it) == IAM_IT_ATTACHED));
1545         assert_corr(ergo(result >  0, it_state(it) == IAM_IT_DETACHED));
1546         assert_corr(ergo(result == 0 && ik_orig != NULL,
1547                          it_ikeycmp(it, ik_orig) >= 0));
1548         return result;
1549 }
1550
1551 /*
1552  * Return pointer to the record under iterator.
1553  *
1554  * precondition:  it_state(it) == IAM_IT_ATTACHED && it_at_rec(it)
1555  * postcondition: it_state(it) == IAM_IT_ATTACHED
1556  */
1557 struct iam_rec *iam_it_rec_get(const struct iam_iterator *it)
1558 {
1559         assert_corr(it_state(it) == IAM_IT_ATTACHED);
1560         assert_corr(it_at_rec(it));
1561         return iam_leaf_rec(&it->ii_path.ip_leaf);
1562 }
1563
1564 static void iam_it_reccpy(struct iam_iterator *it, const struct iam_rec *r)
1565 {
1566         struct iam_leaf *folio;
1567
1568         folio = &it->ii_path.ip_leaf;
1569         iam_leaf_ops(folio)->rec_set(folio, r);
1570 }
1571
1572 /*
1573  * Replace contents of record under iterator.
1574  *
1575  * precondition:  it_state(it) == IAM_IT_ATTACHED &&
1576  *                it->ii_flags&IAM_IT_WRITE
1577  * postcondition: it_state(it) == IAM_IT_ATTACHED &&
1578  *                ergo(result == 0, !memcmp(iam_it_rec_get(it), r, ...))
1579  */
1580 int iam_it_rec_set(handle_t *h,
1581                    struct iam_iterator *it, const struct iam_rec *r)
1582 {
1583         int result;
1584         struct iam_path *path;
1585         struct buffer_head *bh;
1586
1587         assert_corr(it_state(it) == IAM_IT_ATTACHED &&
1588                     it->ii_flags&IAM_IT_WRITE);
1589         assert_corr(it_at_rec(it));
1590
1591         path = &it->ii_path;
1592         bh   = path->ip_leaf.il_bh;
1593         result = iam_txn_add(h, path, bh);
1594         if (result == 0) {
1595                 iam_it_reccpy(it, r);
1596                 result = iam_txn_dirty(h, path, bh);
1597         }
1598         return result;
1599 }
1600
1601 /*
1602  * Return pointer to the index key under iterator.
1603  *
1604  * precondition:  it_state(it) == IAM_IT_ATTACHED ||
1605  *                it_state(it) == IAM_IT_SKEWED
1606  */
1607 static struct iam_ikey *iam_it_ikey_get(const struct iam_iterator *it,
1608                                         struct iam_ikey *ikey)
1609 {
1610         assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1611                     it_state(it) == IAM_IT_SKEWED);
1612         assert_corr(it_at_rec(it));
1613         return iam_leaf_ikey(&it->ii_path.ip_leaf, ikey);
1614 }
1615
1616 /*
1617  * Return pointer to the key under iterator.
1618  *
1619  * precondition:  it_state(it) == IAM_IT_ATTACHED ||
1620  *                it_state(it) == IAM_IT_SKEWED
1621  */
1622 struct iam_key *iam_it_key_get(const struct iam_iterator *it)
1623 {
1624         assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1625                     it_state(it) == IAM_IT_SKEWED);
1626         assert_corr(it_at_rec(it));
1627         return iam_leaf_key(&it->ii_path.ip_leaf);
1628 }
1629
1630 /*
1631  * Return size of key under iterator (in bytes)
1632  *
1633  * precondition:  it_state(it) == IAM_IT_ATTACHED ||
1634  *                it_state(it) == IAM_IT_SKEWED
1635  */
1636 int iam_it_key_size(const struct iam_iterator *it)
1637 {
1638         assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1639                     it_state(it) == IAM_IT_SKEWED);
1640         assert_corr(it_at_rec(it));
1641         return iam_leaf_key_size(&it->ii_path.ip_leaf);
1642 }
1643
1644 static struct buffer_head *
1645 iam_new_node(handle_t *h, struct iam_container *c, iam_ptr_t *b, int *e)
1646 {
1647         struct inode *inode = c->ic_object;
1648         struct buffer_head *bh = NULL;
1649         struct iam_idle_head *head;
1650         struct buffer_head *idle;
1651         __u32 *idle_blocks;
1652         __u16 count;
1653
1654         if (c->ic_idle_bh == NULL)
1655                 goto newblock;
1656
1657         mutex_lock(&c->ic_idle_mutex);
1658         if (unlikely(c->ic_idle_bh == NULL)) {
1659                 mutex_unlock(&c->ic_idle_mutex);
1660                 goto newblock;
1661         }
1662
1663         head = (struct iam_idle_head *)(c->ic_idle_bh->b_data);
1664         count = le16_to_cpu(head->iih_count);
1665         if (count > 0) {
1666                 *e = ldiskfs_journal_get_write_access(h, c->ic_idle_bh);
1667                 if (*e != 0)
1668                         goto fail;
1669
1670                 --count;
1671                 *b = le32_to_cpu(head->iih_blks[count]);
1672                 head->iih_count = cpu_to_le16(count);
1673                 *e = ldiskfs_handle_dirty_metadata(h, inode, c->ic_idle_bh);
1674                 if (*e != 0)
1675                         goto fail;
1676
1677                 mutex_unlock(&c->ic_idle_mutex);
1678                 bh = ldiskfs_bread(NULL, inode, *b, 0, e);
1679                 if (bh == NULL)
1680                         return NULL;
1681                 goto got;
1682         }
1683
1684         /* The block itself which contains the iam_idle_head is
1685          * also an idle block, and can be used as the new node. */
1686         idle_blocks = (__u32 *)(c->ic_root_bh->b_data +
1687                                 c->ic_descr->id_root_gap +
1688                                 sizeof(struct dx_countlimit));
1689         *e = ldiskfs_journal_get_write_access(h, c->ic_root_bh);
1690         if (*e != 0)
1691                 goto fail;
1692
1693         *b = le32_to_cpu(*idle_blocks);
1694         iam_lock_bh(c->ic_root_bh);
1695         *idle_blocks = head->iih_next;
1696         iam_unlock_bh(c->ic_root_bh);
1697         *e = ldiskfs_handle_dirty_metadata(h, inode, c->ic_root_bh);
1698         if (*e != 0) {
1699                 iam_lock_bh(c->ic_root_bh);
1700                 *idle_blocks = cpu_to_le32(*b);
1701                 iam_unlock_bh(c->ic_root_bh);
1702                 goto fail;
1703         }
1704
1705         bh = c->ic_idle_bh;
1706         idle = iam_load_idle_blocks(c, le32_to_cpu(*idle_blocks));
1707         if (idle != NULL && IS_ERR(idle)) {
1708                 *e = PTR_ERR(idle);
1709                 c->ic_idle_bh = NULL;
1710                 brelse(bh);
1711                 goto fail;
1712         }
1713
1714         c->ic_idle_bh = idle;
1715         mutex_unlock(&c->ic_idle_mutex);
1716
1717 got:
1718         /* get write access for the found buffer head */
1719         *e = ldiskfs_journal_get_write_access(h, bh);
1720         if (*e != 0) {
1721                 brelse(bh);
1722                 bh = NULL;
1723                 ldiskfs_std_error(inode->i_sb, *e);
1724         } else {
1725                 /* Clear the reused node as new node does. */
1726                 memset(bh->b_data, 0, inode->i_sb->s_blocksize);
1727                 set_buffer_uptodate(bh);
1728         }
1729         return bh;
1730
1731 newblock:
1732         bh = osd_ldiskfs_append(h, inode, b, e);
1733         return bh;
1734
1735 fail:
1736         mutex_unlock(&c->ic_idle_mutex);
1737         ldiskfs_std_error(inode->i_sb, *e);
1738         return NULL;
1739 }
1740
1741 /*
1742  * Insertion of new record. Interaction with jbd during non-trivial case (when
1743  * split happens) is as following:
1744  *
1745  *  - new leaf node is involved into transaction by iam_new_node();
1746  *
1747  *  - old leaf node is involved into transaction by iam_add_rec();
1748  *
1749  *  - leaf where insertion point ends in, is marked dirty by iam_add_rec();
1750  *
1751  *  - leaf without insertion point is marked dirty (as @new_leaf) by
1752  *  iam_new_leaf();
1753  *
1754  *  - split index nodes are involved into transaction and marked dirty by
1755  *  split_index_node().
1756  *
1757  *  - "safe" index node, which is no split, but where new pointer is inserted
1758  *  is involved into transaction and marked dirty by split_index_node().
1759  *
1760  *  - index node where pointer to new leaf is inserted is involved into
1761  *  transaction by split_index_node() and marked dirty by iam_add_rec().
1762  *
1763  *  - inode is marked dirty by iam_add_rec().
1764  *
1765  */
1766
1767 static int iam_new_leaf(handle_t *handle, struct iam_leaf *leaf)
1768 {
1769         int err;
1770         iam_ptr_t blknr;
1771         struct buffer_head   *new_leaf;
1772         struct buffer_head   *old_leaf;
1773         struct iam_container *c;
1774         struct inode         *obj;
1775         struct iam_path      *path;
1776
1777         assert_inv(iam_leaf_check(leaf));
1778
1779         c = iam_leaf_container(leaf);
1780         path = leaf->il_path;
1781
1782         obj = c->ic_object;
1783         new_leaf = iam_new_node(handle, c, &blknr, &err);
1784         do_corr(schedule());
1785         if (new_leaf != NULL) {
1786                 struct dynlock_handle *lh;
1787
1788                 lh = iam_lock_htree(c, blknr, DLT_WRITE);
1789                 do_corr(schedule());
1790                 if (lh != NULL) {
1791                         iam_leaf_ops(leaf)->init_new(c, new_leaf);
1792                         do_corr(schedule());
1793                         old_leaf = leaf->il_bh;
1794                         iam_leaf_split(leaf, &new_leaf, blknr);
1795                         if (old_leaf != leaf->il_bh) {
1796                                 /*
1797                                  * Switched to the new leaf.
1798                                  */
1799                                 iam_leaf_unlock(leaf);
1800                                 leaf->il_lock = lh;
1801                                 path->ip_frame->leaf = blknr;
1802                         } else
1803                                 iam_unlock_htree(path->ip_container, lh);
1804                         do_corr(schedule());
1805                         err = iam_txn_dirty(handle, path, new_leaf);
1806                         if (err == 0)
1807                                 err = ldiskfs_mark_inode_dirty(handle, obj);
1808                         do_corr(schedule());
1809                 } else
1810                         err = -ENOMEM;
1811                 brelse(new_leaf);
1812         }
1813         assert_inv(iam_leaf_check(leaf));
1814         assert_inv(iam_leaf_check(&iam_leaf_path(leaf)->ip_leaf));
1815         assert_inv(iam_path_check(iam_leaf_path(leaf)));
1816         return err;
1817 }
1818
1819 static inline void dx_set_limit(struct iam_entry *entries, unsigned value)
1820 {
1821         ((struct dx_countlimit *) entries)->limit = cpu_to_le16(value);
1822 }
1823
1824 static int iam_shift_entries(struct iam_path *path,
1825                          struct iam_frame *frame, unsigned count,
1826                          struct iam_entry *entries, struct iam_entry *entries2,
1827                          u32 newblock)
1828 {
1829         unsigned count1;
1830         unsigned count2;
1831         int delta;
1832
1833         struct iam_frame *parent = frame - 1;
1834         struct iam_ikey *pivot = iam_path_ikey(path, 3);
1835
1836         delta = dx_index_is_compat(path) ? 0 : +1;
1837
1838         count1 = count/2 + delta;
1839         count2 = count - count1;
1840         dx_get_ikey(path, iam_entry_shift(path, entries, count1), pivot);
1841
1842         dxtrace(printk("Split index %d/%d\n", count1, count2));
1843
1844         memcpy((char *) iam_entry_shift(path, entries2, delta),
1845                (char *) iam_entry_shift(path, entries, count1),
1846                count2 * iam_entry_size(path));
1847
1848         dx_set_count(entries2, count2 + delta);
1849         dx_set_limit(entries2, dx_node_limit(path));
1850
1851         /*
1852          * NOTE: very subtle piece of code competing dx_probe() may find 2nd
1853          * level index in root index, then we insert new index here and set
1854          * new count in that 2nd level index. so, dx_probe() may see 2nd level
1855          * index w/o hash it looks for. the solution is to check root index
1856          * after we locked just founded 2nd level index -bzzz
1857          */
1858         iam_insert_key_lock(path, parent, pivot, newblock);
1859
1860         /*
1861          * now old and new 2nd level index blocks contain all pointers, so
1862          * dx_probe() may find it in the both.  it's OK -bzzz
1863          */
1864         iam_lock_bh(frame->bh);
1865         dx_set_count(entries, count1);
1866         iam_unlock_bh(frame->bh);
1867
1868         /*
1869          * now old 2nd level index block points to first half of leafs. it's
1870          * importand that dx_probe() must check root index block for changes
1871          * under dx_lock_bh(frame->bh) -bzzz
1872          */
1873
1874         return count1;
1875 }
1876
1877
1878 int split_index_node(handle_t *handle, struct iam_path *path,
1879                      struct dynlock_handle **lh)
1880 {
1881
1882         struct iam_entry *entries;   /* old block contents */
1883         struct iam_entry *entries2;  /* new block contents */
1884         struct iam_frame *frame, *safe;
1885         struct buffer_head *bh_new[DX_MAX_TREE_HEIGHT] = {NULL};
1886         u32 newblock[DX_MAX_TREE_HEIGHT] = {0};
1887         struct dynlock_handle *lock[DX_MAX_TREE_HEIGHT] = {NULL,};
1888         struct dynlock_handle *new_lock[DX_MAX_TREE_HEIGHT] = {NULL,};
1889         struct inode *dir = iam_path_obj(path);
1890         struct iam_descr *descr;
1891         int nr_splet;
1892         int i, err;
1893
1894         descr = iam_path_descr(path);
1895         /*
1896          * Algorithm below depends on this.
1897          */
1898         assert_corr(dx_root_limit(path) < dx_node_limit(path));
1899
1900         frame = path->ip_frame;
1901         entries = frame->entries;
1902
1903         /*
1904          * Tall-tree handling: we might have to split multiple index blocks
1905          * all the way up to tree root. Tricky point here is error handling:
1906          * to avoid complicated undo/rollback we
1907          *
1908          *   - first allocate all necessary blocks
1909          *
1910          *   - insert pointers into them atomically.
1911          */
1912
1913         /*
1914          * Locking: leaf is already locked. htree-locks are acquired on all
1915          * index nodes that require split bottom-to-top, on the "safe" node,
1916          * and on all new nodes
1917          */
1918
1919         dxtrace(printk("using %u of %u node entries\n",
1920                        dx_get_count(entries), dx_get_limit(entries)));
1921
1922         /* What levels need split? */
1923         for (nr_splet = 0; frame >= path->ip_frames &&
1924              dx_get_count(frame->entries) == dx_get_limit(frame->entries);
1925              --frame, ++nr_splet) {
1926                 do_corr(schedule());
1927                 if (nr_splet == DX_MAX_TREE_HEIGHT) {
1928                         /*
1929                         CWARN(dir->i_sb, __FUNCTION__,
1930                                      "Directory index full!\n");
1931                                      */
1932                         err = -ENOSPC;
1933                         goto cleanup;
1934                 }
1935         }
1936
1937         safe = frame;
1938
1939         /*
1940          * Lock all nodes, bottom to top.
1941          */
1942         for (frame = path->ip_frame, i = nr_splet; i >= 0; --i, --frame) {
1943                 do_corr(schedule());
1944                 lock[i] = iam_lock_htree(path->ip_container, frame->curidx,
1945                                          DLT_WRITE);
1946                 if (lock[i] == NULL) {
1947                         err = -ENOMEM;
1948                         goto cleanup;
1949                 }
1950         }
1951
1952         /*
1953          * Check for concurrent index modification.
1954          */
1955         err = iam_check_full_path(path, 1);
1956         if (err)
1957                 goto cleanup;
1958         /*
1959          * And check that the same number of nodes is to be split.
1960          */
1961         for (i = 0, frame = path->ip_frame; frame >= path->ip_frames &&
1962              dx_get_count(frame->entries) == dx_get_limit(frame->entries);
1963              --frame, ++i) {
1964                 ;
1965         }
1966         if (i != nr_splet) {
1967                 err = -EAGAIN;
1968                 goto cleanup;
1969         }
1970
1971         /* Go back down, allocating blocks, locking them, and adding into
1972          * transaction... */
1973         for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
1974                 bh_new[i] = iam_new_node(handle, path->ip_container,
1975                                          &newblock[i], &err);
1976                 do_corr(schedule());
1977                 if (!bh_new[i] ||
1978                     descr->id_ops->id_node_init(path->ip_container,
1979                                                 bh_new[i], 0) != 0)
1980                         goto cleanup;
1981                 new_lock[i] = iam_lock_htree(path->ip_container, newblock[i],
1982                                              DLT_WRITE);
1983                 if (new_lock[i] == NULL) {
1984                         err = -ENOMEM;
1985                         goto cleanup;
1986                 }
1987                 do_corr(schedule());
1988                 BUFFER_TRACE(frame->bh, "get_write_access");
1989                 err = ldiskfs_journal_get_write_access(handle, frame->bh);
1990                 if (err)
1991                         goto journal_error;
1992         }
1993         /* Add "safe" node to transaction too */
1994         if (safe + 1 != path->ip_frames) {
1995                 do_corr(schedule());
1996                 err = ldiskfs_journal_get_write_access(handle, safe->bh);
1997                 if (err)
1998                         goto journal_error;
1999         }
2000
2001         /* Go through nodes once more, inserting pointers */
2002         for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
2003                 unsigned count;
2004                 int idx;
2005                 struct buffer_head *bh2;
2006                 struct buffer_head *bh;
2007
2008                 entries = frame->entries;
2009                 count = dx_get_count(entries);
2010                 idx = iam_entry_diff(path, frame->at, entries);
2011
2012                 bh2 = bh_new[i];
2013                 entries2 = dx_get_entries(path, bh2->b_data, 0);
2014
2015                 bh = frame->bh;
2016                 if (frame == path->ip_frames) {
2017                         /* splitting root node. Tricky point:
2018                          *
2019                          * In the "normal" B-tree we'd split root *and* add
2020                          * new root to the tree with pointers to the old root
2021                          * and its sibling (thus introducing two new nodes).
2022                          *
2023                          * In htree it's enough to add one node, because
2024                          * capacity of the root node is smaller than that of
2025                          * non-root one.
2026                          */
2027                         struct iam_frame *frames;
2028                         struct iam_entry *next;
2029
2030                         assert_corr(i == 0);
2031
2032                         do_corr(schedule());
2033
2034                         frames = path->ip_frames;
2035                         memcpy((char *) entries2, (char *) entries,
2036                                count * iam_entry_size(path));
2037                         dx_set_limit(entries2, dx_node_limit(path));
2038
2039                         /* Set up root */
2040                           iam_lock_bh(frame->bh);
2041                         next = descr->id_ops->id_root_inc(path->ip_container,
2042                                                           path, frame);
2043                         dx_set_block(path, next, newblock[0]);
2044                           iam_unlock_bh(frame->bh);
2045
2046                         do_corr(schedule());
2047                         /* Shift frames in the path */
2048                         memmove(frames + 2, frames + 1,
2049                                 (sizeof path->ip_frames) - 2 * sizeof frames[0]);
2050                         /* Add new access path frame */
2051                         frames[1].at = iam_entry_shift(path, entries2, idx);
2052                         frames[1].entries = entries = entries2;
2053                         frames[1].bh = bh2;
2054                         assert_inv(dx_node_check(path, frame));
2055                         ++ path->ip_frame;
2056                         ++ frame;
2057                         assert_inv(dx_node_check(path, frame));
2058                         bh_new[0] = NULL; /* buffer head is "consumed" */
2059                         err = ldiskfs_handle_dirty_metadata(handle, NULL, bh2);
2060                         if (err)
2061                                 goto journal_error;
2062                         do_corr(schedule());
2063                 } else {
2064                         /* splitting non-root index node. */
2065                         struct iam_frame *parent = frame - 1;
2066
2067                         do_corr(schedule());
2068                         count = iam_shift_entries(path, frame, count,
2069                                               entries, entries2, newblock[i]);
2070                         /* Which index block gets the new entry? */
2071                         if (idx >= count) {
2072                                 int d = dx_index_is_compat(path) ? 0 : +1;
2073
2074                                 frame->at = iam_entry_shift(path, entries2,
2075                                                             idx - count + d);
2076                                 frame->entries = entries = entries2;
2077                                 frame->curidx = newblock[i];
2078                                 swap(frame->bh, bh2);
2079                                 assert_corr(lock[i + 1] != NULL);
2080                                 assert_corr(new_lock[i] != NULL);
2081                                 swap(lock[i + 1], new_lock[i]);
2082                                 bh_new[i] = bh2;
2083                                 parent->at = iam_entry_shift(path,
2084                                                              parent->at, +1);
2085                         }
2086                         assert_inv(dx_node_check(path, frame));
2087                         assert_inv(dx_node_check(path, parent));
2088                         dxtrace(dx_show_index ("node", frame->entries));
2089                         dxtrace(dx_show_index ("node",
2090                                ((struct dx_node *) bh2->b_data)->entries));
2091                         err = ldiskfs_handle_dirty_metadata(handle, NULL, bh2);
2092                         if (err)
2093                                 goto journal_error;
2094                         do_corr(schedule());
2095                         err = ldiskfs_handle_dirty_metadata(handle, NULL,
2096                                                             parent->bh);
2097                         if (err)
2098                                 goto journal_error;
2099                 }
2100                 do_corr(schedule());
2101                 err = ldiskfs_handle_dirty_metadata(handle, NULL, bh);
2102                 if (err)
2103                         goto journal_error;
2104         }
2105                 /*
2106                  * This function was called to make insertion of new leaf
2107                  * possible. Check that it fulfilled its obligations.
2108                  */
2109                 assert_corr(dx_get_count(path->ip_frame->entries) <
2110                             dx_get_limit(path->ip_frame->entries));
2111         assert_corr(lock[nr_splet] != NULL);
2112         *lh = lock[nr_splet];
2113         lock[nr_splet] = NULL;
2114         if (nr_splet > 0) {
2115                 /*
2116                  * Log ->i_size modification.
2117                  */
2118                 err = ldiskfs_mark_inode_dirty(handle, dir);
2119                 if (err)
2120                         goto journal_error;
2121         }
2122         goto cleanup;
2123 journal_error:
2124         ldiskfs_std_error(dir->i_sb, err);
2125
2126 cleanup:
2127         iam_unlock_array(path->ip_container, lock);
2128         iam_unlock_array(path->ip_container, new_lock);
2129
2130         assert_corr(err || iam_frame_is_locked(path, path->ip_frame));
2131
2132         do_corr(schedule());
2133         for (i = 0; i < ARRAY_SIZE(bh_new); ++i) {
2134                 if (bh_new[i] != NULL)
2135                         brelse(bh_new[i]);
2136         }
2137         return err;
2138 }
2139
2140 static int iam_add_rec(handle_t *handle, struct iam_iterator *it,
2141                        struct iam_path *path,
2142                        const struct iam_key *k, const struct iam_rec *r)
2143 {
2144         int err;
2145         struct iam_leaf *leaf;
2146
2147         leaf = &path->ip_leaf;
2148         assert_inv(iam_leaf_check(leaf));
2149         assert_inv(iam_path_check(path));
2150         err = iam_txn_add(handle, path, leaf->il_bh);
2151         if (err == 0) {
2152                 do_corr(schedule());
2153                 if (!iam_leaf_can_add(leaf, k, r)) {
2154                         struct dynlock_handle *lh = NULL;
2155
2156                         do {
2157                                 assert_corr(lh == NULL);
2158                                 do_corr(schedule());
2159                                 err = split_index_node(handle, path, &lh);
2160                                 if (err == -EAGAIN) {
2161                                         assert_corr(lh == NULL);
2162
2163                                         iam_path_fini(path);
2164                                         it->ii_state = IAM_IT_DETACHED;
2165
2166                                         do_corr(schedule());
2167                                         err = iam_it_get_exact(it, k);
2168                                         if (err == -ENOENT)
2169                                                 err = +1; /* repeat split */
2170                                         else if (err == 0)
2171                                                 err = -EEXIST;
2172                                 }
2173                         } while (err > 0);
2174                         assert_inv(iam_path_check(path));
2175                         if (err == 0) {
2176                                 assert_corr(lh != NULL);
2177                                 do_corr(schedule());
2178                                 err = iam_new_leaf(handle, leaf);
2179                                 if (err == 0)
2180                                         err = iam_txn_dirty(handle, path,
2181                                                             path->ip_frame->bh);
2182                         }
2183                         iam_unlock_htree(path->ip_container, lh);
2184                         do_corr(schedule());
2185                 }
2186                 if (err == 0) {
2187                         iam_leaf_rec_add(leaf, k, r);
2188                         err = iam_txn_dirty(handle, path, leaf->il_bh);
2189                 }
2190         }
2191         assert_inv(iam_leaf_check(leaf));
2192         assert_inv(iam_leaf_check(&path->ip_leaf));
2193         assert_inv(iam_path_check(path));
2194         return err;
2195 }
2196
2197 /*
2198  * Insert new record with key @k and contents from @r, shifting records to the
2199  * right. On success, iterator is positioned on the newly inserted record.
2200  *
2201  * precondition: it->ii_flags&IAM_IT_WRITE &&
2202  *               (it_state(it) == IAM_IT_ATTACHED ||
2203  *                it_state(it) == IAM_IT_SKEWED) &&
2204  *               ergo(it_state(it) == IAM_IT_ATTACHED,
2205  *                    it_keycmp(it, k) <= 0) &&
2206  *               ergo(it_before(it), it_keycmp(it, k) > 0));
2207  * postcondition: ergo(result == 0,
2208  *                     it_state(it) == IAM_IT_ATTACHED &&
2209  *                     it_keycmp(it, k) == 0 &&
2210  *                     !memcmp(iam_it_rec_get(it), r, ...))
2211  */
2212 int iam_it_rec_insert(handle_t *h, struct iam_iterator *it,
2213                       const struct iam_key *k, const struct iam_rec *r)
2214 {
2215         int result;
2216         struct iam_path *path;
2217
2218         path = &it->ii_path;
2219
2220         assert_corr(it->ii_flags&IAM_IT_WRITE);
2221         assert_corr(it_state(it) == IAM_IT_ATTACHED ||
2222                     it_state(it) == IAM_IT_SKEWED);
2223         assert_corr(ergo(it_state(it) == IAM_IT_ATTACHED,
2224                          it_keycmp(it, k) <= 0));
2225         assert_corr(ergo(it_before(it), it_keycmp(it, k) > 0));
2226         result = iam_add_rec(h, it, path, k, r);
2227         if (result == 0)
2228                 it->ii_state = IAM_IT_ATTACHED;
2229         assert_corr(ergo(result == 0,
2230                          it_state(it) == IAM_IT_ATTACHED &&
2231                          it_keycmp(it, k) == 0));
2232         return result;
2233 }
2234
2235 static inline int iam_idle_blocks_limit(struct inode *inode)
2236 {
2237         return (inode->i_sb->s_blocksize - sizeof(struct iam_idle_head)) >> 2;
2238 }
2239
2240 /*
2241  * If the leaf cannnot be recycled, we will lose one block for reusing.
2242  * It is not a serious issue because it almost the same of non-recycle.
2243  */
2244 static iam_ptr_t iam_index_shrink(handle_t *h, struct iam_path *p,
2245                                   struct iam_leaf *l, struct buffer_head **bh)
2246 {
2247         struct iam_container *c = p->ip_container;
2248         struct inode *inode = c->ic_object;
2249         struct iam_frame *frame = p->ip_frame;
2250         struct iam_entry *entries;
2251         struct iam_entry *pos;
2252         struct dynlock_handle *lh;
2253         int count;
2254         int rc;
2255
2256         if (c->ic_idle_failed)
2257                 return 0;
2258
2259         if (unlikely(frame == NULL))
2260                 return 0;
2261
2262         if (!iam_leaf_empty(l))
2263                 return 0;
2264
2265         lh = iam_lock_htree(c, frame->curidx, DLT_WRITE);
2266         if (lh == NULL) {
2267                 CWARN("%.16s: No memory to recycle idle blocks\n",
2268                       LDISKFS_SB(inode->i_sb)->s_es->s_volume_name);
2269                 return 0;
2270         }
2271
2272         rc = iam_txn_add(h, p, frame->bh);
2273         if (rc != 0) {
2274                 iam_unlock_htree(c, lh);
2275                 return 0;
2276         }
2277
2278         iam_lock_bh(frame->bh);
2279         entries = frame->entries;
2280         count = dx_get_count(entries);
2281         /* NOT shrink the last entry in the index node, which can be reused
2282          * directly by next new node. */
2283         if (count == 2) {
2284                 iam_unlock_bh(frame->bh);
2285                 iam_unlock_htree(c, lh);
2286                 return 0;
2287         }
2288
2289         pos = iam_find_position(p, frame);
2290         /* There may be some new leaf nodes have been added or empty leaf nodes
2291          * have been shrinked during my delete operation.
2292          *
2293          * If the empty leaf is not under current index node because the index
2294          * node has been split, then just skip the empty leaf, which is rare. */
2295         if (unlikely(frame->leaf != dx_get_block(p, pos))) {
2296                 iam_unlock_bh(frame->bh);
2297                 iam_unlock_htree(c, lh);
2298                 return 0;
2299         }
2300
2301         frame->at = pos;
2302         if (frame->at < iam_entry_shift(p, entries, count - 1)) {
2303                 struct iam_entry *n = iam_entry_shift(p, frame->at, 1);
2304
2305                 memmove(frame->at, n,
2306                         (char *)iam_entry_shift(p, entries, count) - (char *)n);
2307                 frame->at_shifted = 1;
2308         }
2309         dx_set_count(entries, count - 1);
2310         iam_unlock_bh(frame->bh);
2311         rc = iam_txn_dirty(h, p, frame->bh);
2312         iam_unlock_htree(c, lh);
2313         if (rc != 0)
2314                 return 0;
2315
2316         get_bh(l->il_bh);
2317         *bh = l->il_bh;
2318         return frame->leaf;
2319 }
2320
2321 static int
2322 iam_install_idle_blocks(handle_t *h, struct iam_path *p, struct buffer_head *bh,
2323                         __u32 *idle_blocks, iam_ptr_t blk)
2324 {
2325         struct iam_container *c = p->ip_container;
2326         struct buffer_head *old = c->ic_idle_bh;
2327         struct iam_idle_head *head;
2328         int rc;
2329
2330         head = (struct iam_idle_head *)(bh->b_data);
2331         head->iih_magic = cpu_to_le16(IAM_IDLE_HEADER_MAGIC);
2332         head->iih_count = 0;
2333         head->iih_next = *idle_blocks;
2334         /* The bh already get_write_accessed. */
2335         rc = iam_txn_dirty(h, p, bh);
2336         if (rc != 0)
2337                 return rc;
2338
2339         rc = iam_txn_add(h, p, c->ic_root_bh);
2340         if (rc != 0)
2341                 return rc;
2342
2343         iam_lock_bh(c->ic_root_bh);
2344         *idle_blocks = cpu_to_le32(blk);
2345         iam_unlock_bh(c->ic_root_bh);
2346         rc = iam_txn_dirty(h, p, c->ic_root_bh);
2347         if (rc == 0) {
2348                 /* NOT release old before new assigned. */
2349                 get_bh(bh);
2350                 c->ic_idle_bh = bh;
2351                 brelse(old);
2352         } else {
2353                 iam_lock_bh(c->ic_root_bh);
2354                 *idle_blocks = head->iih_next;
2355                 iam_unlock_bh(c->ic_root_bh);
2356         }
2357         return rc;
2358 }
2359
2360 /*
2361  * If the leaf cannnot be recycled, we will lose one block for reusing.
2362  * It is not a serious issue because it almost the same of non-recycle.
2363  */
2364 static void iam_recycle_leaf(handle_t *h, struct iam_path *p,
2365                              struct buffer_head *bh, iam_ptr_t blk)
2366 {
2367         struct iam_container *c = p->ip_container;
2368         struct inode *inode = c->ic_object;
2369         struct iam_idle_head *head;
2370         __u32 *idle_blocks;
2371         int count;
2372         int rc;
2373
2374         mutex_lock(&c->ic_idle_mutex);
2375         if (unlikely(c->ic_idle_failed)) {
2376                 rc = -EFAULT;
2377                 goto unlock;
2378         }
2379
2380         idle_blocks = (__u32 *)(c->ic_root_bh->b_data +
2381                                 c->ic_descr->id_root_gap +
2382                                 sizeof(struct dx_countlimit));
2383         /* It is the first idle block. */
2384         if (c->ic_idle_bh == NULL) {
2385                 rc = iam_install_idle_blocks(h, p, bh, idle_blocks, blk);
2386                 goto unlock;
2387         }
2388
2389         head = (struct iam_idle_head *)(c->ic_idle_bh->b_data);
2390         count = le16_to_cpu(head->iih_count);
2391         /* Current ic_idle_bh is full, to be replaced by the leaf. */
2392         if (count == iam_idle_blocks_limit(inode)) {
2393                 rc = iam_install_idle_blocks(h, p, bh, idle_blocks, blk);
2394                 goto unlock;
2395         }
2396
2397         /* Just add to ic_idle_bh. */
2398         rc = iam_txn_add(h, p, c->ic_idle_bh);
2399         if (rc != 0)
2400                 goto unlock;
2401
2402         head->iih_blks[count] = cpu_to_le32(blk);
2403         head->iih_count = cpu_to_le16(count + 1);
2404         rc = iam_txn_dirty(h, p, c->ic_idle_bh);
2405
2406 unlock:
2407         mutex_unlock(&c->ic_idle_mutex);
2408         if (rc != 0)
2409                 CWARN("%.16s: idle blocks failed, will lose the blk %u\n",
2410                       LDISKFS_SB(inode->i_sb)->s_es->s_volume_name, blk);
2411 }
2412
2413 /*
2414  * Delete record under iterator.
2415  *
2416  * precondition:  it_state(it) == IAM_IT_ATTACHED &&
2417  *                it->ii_flags&IAM_IT_WRITE &&
2418  *                it_at_rec(it)
2419  * postcondition: it_state(it) == IAM_IT_ATTACHED ||
2420  *                it_state(it) == IAM_IT_DETACHED
2421  */
2422 int iam_it_rec_delete(handle_t *h, struct iam_iterator *it)
2423 {
2424         int result;
2425         struct iam_leaf *leaf;
2426         struct iam_path *path;
2427
2428         assert_corr(it_state(it) == IAM_IT_ATTACHED &&
2429                     it->ii_flags&IAM_IT_WRITE);
2430         assert_corr(it_at_rec(it));
2431
2432         path = &it->ii_path;
2433         leaf = &path->ip_leaf;
2434
2435         assert_inv(iam_leaf_check(leaf));
2436         assert_inv(iam_path_check(path));
2437
2438         result = iam_txn_add(h, path, leaf->il_bh);
2439         /*
2440          * no compaction for now.
2441          */
2442         if (result == 0) {
2443                 iam_rec_del(leaf, it->ii_flags&IAM_IT_MOVE);
2444                 result = iam_txn_dirty(h, path, leaf->il_bh);
2445                 if (result == 0 && iam_leaf_at_end(leaf)) {
2446                         struct buffer_head *bh = NULL;
2447                         iam_ptr_t blk;
2448
2449                         blk = iam_index_shrink(h, path, leaf, &bh);
2450                         if (it->ii_flags & IAM_IT_MOVE) {
2451                                 result = iam_it_next(it);
2452                                 if (result > 0)
2453                                         result = 0;
2454                         }
2455
2456                         if (bh != NULL) {
2457                                 iam_recycle_leaf(h, path, bh, blk);
2458                                 brelse(bh);
2459                         }
2460                 }
2461         }
2462         assert_inv(iam_leaf_check(leaf));
2463         assert_inv(iam_path_check(path));
2464         assert_corr(it_state(it) == IAM_IT_ATTACHED ||
2465                     it_state(it) == IAM_IT_DETACHED);
2466         return result;
2467 }
2468
2469 /*
2470  * Convert iterator to cookie.
2471  *
2472  * precondition:  it_state(it) == IAM_IT_ATTACHED &&
2473  *                iam_path_descr(it->ii_path)->id_key_size <= sizeof(iam_pos_t)
2474  * postcondition: it_state(it) == IAM_IT_ATTACHED
2475  */
2476 iam_pos_t iam_it_store(const struct iam_iterator *it)
2477 {
2478         iam_pos_t result;
2479
2480         assert_corr(it_state(it) == IAM_IT_ATTACHED);
2481         assert_corr(it_at_rec(it));
2482         assert_corr(iam_it_container(it)->ic_descr->id_ikey_size <=
2483                     sizeof result);
2484
2485         result = 0;
2486         return *(iam_pos_t *)iam_it_ikey_get(it, (void *)&result);
2487 }
2488
2489 /*
2490  * Restore iterator from cookie.
2491  *
2492  * precondition:  it_state(it) == IAM_IT_DETACHED && it->ii_flags&IAM_IT_MOVE &&
2493  *                iam_path_descr(it->ii_path)->id_key_size <= sizeof(iam_pos_t)
2494  * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED &&
2495  *                                  iam_it_store(it) == pos)
2496  */
2497 int iam_it_load(struct iam_iterator *it, iam_pos_t pos)
2498 {
2499         assert_corr(it_state(it) == IAM_IT_DETACHED &&
2500                     it->ii_flags&IAM_IT_MOVE);
2501         assert_corr(iam_it_container(it)->ic_descr->id_ikey_size <= sizeof pos);
2502         return iam_it_iget(it, (struct iam_ikey *)&pos);
2503 }
2504
2505 /***********************************************************************/
2506 /* invariants                                                          */
2507 /***********************************************************************/
2508
2509 static inline int ptr_inside(void *base, size_t size, void *ptr)
2510 {
2511         return (base <= ptr) && (ptr < base + size);
2512 }
2513
2514 static int iam_frame_invariant(struct iam_frame *f)
2515 {
2516         return
2517                 (f->bh != NULL &&
2518                 f->bh->b_data != NULL &&
2519                 ptr_inside(f->bh->b_data, f->bh->b_size, f->entries) &&
2520                 ptr_inside(f->bh->b_data, f->bh->b_size, f->at) &&
2521                 f->entries <= f->at);
2522 }
2523
2524 static int iam_leaf_invariant(struct iam_leaf *l)
2525 {
2526         return
2527                 l->il_bh != NULL &&
2528                 l->il_bh->b_data != NULL &&
2529                 ptr_inside(l->il_bh->b_data, l->il_bh->b_size, l->il_entries) &&
2530                 ptr_inside(l->il_bh->b_data, l->il_bh->b_size, l->il_at) &&
2531                 l->il_entries <= l->il_at;
2532 }
2533
2534 static int iam_path_invariant(struct iam_path *p)
2535 {
2536         int i;
2537
2538         if (p->ip_container == NULL ||
2539             p->ip_indirect < 0 || p->ip_indirect > DX_MAX_TREE_HEIGHT - 1 ||
2540             p->ip_frame != p->ip_frames + p->ip_indirect ||
2541             !iam_leaf_invariant(&p->ip_leaf))
2542                 return 0;
2543         for (i = 0; i < ARRAY_SIZE(p->ip_frames); ++i) {
2544                 if (i <= p->ip_indirect) {
2545                         if (!iam_frame_invariant(&p->ip_frames[i]))
2546                                 return 0;
2547                 }
2548         }
2549         return 1;
2550 }
2551
2552 int iam_it_invariant(struct iam_iterator *it)
2553 {
2554         return
2555                 (it->ii_state == IAM_IT_DETACHED ||
2556                  it->ii_state == IAM_IT_ATTACHED ||
2557                  it->ii_state == IAM_IT_SKEWED) &&
2558                 !(it->ii_flags & ~(IAM_IT_MOVE | IAM_IT_WRITE)) &&
2559                 ergo(it->ii_state == IAM_IT_ATTACHED ||
2560                      it->ii_state == IAM_IT_SKEWED,
2561                      iam_path_invariant(&it->ii_path) &&
2562                      equi(it_at_rec(it), it->ii_state == IAM_IT_SKEWED));
2563 }
2564
2565 /*
2566  * Search container @c for record with key @k. If record is found, its data
2567  * are moved into @r.
2568  *
2569  * Return values: 0: found, -ENOENT: not-found, -ve: error
2570  */
2571 int iam_lookup(struct iam_container *c, const struct iam_key *k,
2572                struct iam_rec *r, struct iam_path_descr *pd)
2573 {
2574         struct iam_iterator it;
2575         int result;
2576
2577         iam_it_init(&it, c, 0, pd);
2578
2579         result = iam_it_get_exact(&it, k);
2580         if (result == 0)
2581                 /*
2582                  * record with required key found, copy it into user buffer
2583                  */
2584                 iam_reccpy(&it.ii_path.ip_leaf, r);
2585         iam_it_put(&it);
2586         iam_it_fini(&it);
2587         return result;
2588 }
2589
2590 /*
2591  * Insert new record @r with key @k into container @c (within context of
2592  * transaction @h).
2593  *
2594  * Return values: 0: success, -ve: error, including -EEXIST when record with
2595  * given key is already present.
2596  *
2597  * postcondition: ergo(result == 0 || result == -EEXIST,
2598  *                                  iam_lookup(c, k, r2) > 0;
2599  */
2600 int iam_insert(handle_t *h, struct iam_container *c, const struct iam_key *k,
2601                const struct iam_rec *r, struct iam_path_descr *pd)
2602 {
2603         struct iam_iterator it;
2604         int result;
2605
2606         iam_it_init(&it, c, IAM_IT_WRITE, pd);
2607
2608         result = iam_it_get_exact(&it, k);
2609         if (result == -ENOENT)
2610                 result = iam_it_rec_insert(h, &it, k, r);
2611         else if (result == 0)
2612                 result = -EEXIST;
2613         iam_it_put(&it);
2614         iam_it_fini(&it);
2615         return result;
2616 }
2617
2618 /*
2619  * Update record with the key @k in container @c (within context of
2620  * transaction @h), new record is given by @r.
2621  *
2622  * Return values: +1: skip because of the same rec value, 0: success,
2623  * -ve: error, including -ENOENT if no record with the given key found.
2624  */
2625 int iam_update(handle_t *h, struct iam_container *c, const struct iam_key *k,
2626                const struct iam_rec *r, struct iam_path_descr *pd)
2627 {
2628         struct iam_iterator it;
2629         struct iam_leaf *folio;
2630         int result;
2631
2632         iam_it_init(&it, c, IAM_IT_WRITE, pd);
2633
2634         result = iam_it_get_exact(&it, k);
2635         if (result == 0) {
2636                 folio = &it.ii_path.ip_leaf;
2637                 result = iam_leaf_ops(folio)->rec_eq(folio, r);
2638                 if (result == 0)
2639                         iam_it_rec_set(h, &it, r);
2640                 else
2641                         result = 1;
2642         }
2643         iam_it_put(&it);
2644         iam_it_fini(&it);
2645         return result;
2646 }
2647
2648 /*
2649  * Delete existing record with key @k.
2650  *
2651  * Return values: 0: success, -ENOENT: not-found, -ve: other error.
2652  *
2653  * postcondition: ergo(result == 0 || result == -ENOENT,
2654  *                                 !iam_lookup(c, k, *));
2655  */
2656 int iam_delete(handle_t *h, struct iam_container *c, const struct iam_key *k,
2657                struct iam_path_descr *pd)
2658 {
2659         struct iam_iterator it;
2660         int result;
2661
2662         iam_it_init(&it, c, IAM_IT_WRITE, pd);
2663
2664         result = iam_it_get_exact(&it, k);
2665         if (result == 0)
2666                 iam_it_rec_delete(h, &it);
2667         iam_it_put(&it);
2668         iam_it_fini(&it);
2669         return result;
2670 }
2671
2672 int iam_root_limit(int rootgap, int blocksize, int size)
2673 {
2674         int limit;
2675         int nlimit;
2676
2677         limit = (blocksize - rootgap) / size;
2678         nlimit = blocksize / size;
2679         if (limit == nlimit)
2680                 limit--;
2681         return limit;
2682 }