4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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).
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
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
27 * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
28 * Use is subject to license terms.
30 * Copyright (c) 2011, 2012, Whamcloud, Inc.
33 * This file is part of Lustre, http://www.lustre.org/
34 * Lustre is a trademark of Sun Microsystems, Inc.
37 * Top-level entry points into iam module
39 * Author: Wang Di <wangdi@clusterfs.com>
40 * Author: Nikita Danilov <nikita@clusterfs.com>
44 * iam: big theory statement.
46 * iam (Index Access Module) is a module providing abstraction of persistent
47 * transactional container on top of generalized ldiskfs htree.
51 * - key, pointer, and record size specifiable per container.
53 * - trees taller than 2 index levels.
55 * - read/write to existing ldiskfs htree directories as iam containers.
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.
61 * iam does not work with keys directly, instead it calls user-supplied key
62 * comparison function (->dpo_keycmp()).
64 * Pointers are (currently) interpreted as logical offsets (measured in
65 * blocksful) within underlying flat file on top of which iam tree lives.
69 * iam mostly tries to reuse existing htree formats.
71 * Format of index node:
73 * +-----+-------+-------+-------+------+-------+------------+
74 * | | count | | | | | |
75 * | gap | / | entry | entry | .... | entry | free space |
76 * | | limit | | | | | |
77 * +-----+-------+-------+-------+------+-------+------------+
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).
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
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.
97 * free space portion of node new entries are added to
99 * Entries in index node are sorted by their key value.
101 * Format of a leaf node is not specified. Generic iam code accesses leaf
102 * nodes through ->id_leaf methods in struct iam_descr.
106 #include <linux/module.h>
107 #include <linux/fs.h>
108 #include <linux/pagemap.h>
109 #include <linux/time.h>
110 #include <linux/fcntl.h>
111 #include <linux/stat.h>
112 #include <linux/string.h>
113 #include <linux/quotaops.h>
114 #include <linux/buffer_head.h>
115 #include "osd_internal.h"
121 * List of all registered formats.
123 * No locking. Callers synchronize.
125 static CFS_LIST_HEAD(iam_formats);
127 void iam_format_register(struct iam_format *fmt)
129 cfs_list_add(&fmt->if_linkage, &iam_formats);
131 EXPORT_SYMBOL(iam_format_register);
134 * Determine format of given container. This is done by scanning list of
135 * registered formats and calling ->if_guess() method of each in turn.
137 static int iam_format_guess(struct iam_container *c)
140 struct iam_format *fmt;
143 * XXX temporary initialization hook.
146 static int initialized = 0;
149 iam_lvar_format_init();
150 iam_lfix_format_init();
156 cfs_list_for_each_entry(fmt, &iam_formats, if_linkage) {
157 result = fmt->if_guess(c);
165 * Initialize container @c.
167 int iam_container_init(struct iam_container *c,
168 struct iam_descr *descr, struct inode *inode)
170 memset(c, 0, sizeof *c);
172 c->ic_object = inode;
173 cfs_init_rwsem(&c->ic_sem);
174 dynlock_init(&c->ic_tree_lock);
177 EXPORT_SYMBOL(iam_container_init);
180 * Determine container format.
182 int iam_container_setup(struct iam_container *c)
184 return iam_format_guess(c);
186 EXPORT_SYMBOL(iam_container_setup);
189 * Finalize container @c, release all resources.
191 void iam_container_fini(struct iam_container *c)
193 brelse(c->ic_root_bh);
194 c->ic_root_bh = NULL;
196 EXPORT_SYMBOL(iam_container_fini);
198 void iam_path_init(struct iam_path *path, struct iam_container *c,
199 struct iam_path_descr *pd)
201 memset(path, 0, sizeof *path);
202 path->ip_container = c;
203 path->ip_frame = path->ip_frames;
205 path->ip_leaf.il_path = path;
208 static void iam_leaf_fini(struct iam_leaf *leaf);
210 void iam_path_release(struct iam_path *path)
214 for (i = 0; i < ARRAY_SIZE(path->ip_frames); i++) {
215 if (path->ip_frames[i].bh != NULL) {
216 brelse(path->ip_frames[i].bh);
217 path->ip_frames[i].bh = NULL;
222 void iam_path_fini(struct iam_path *path)
224 iam_leaf_fini(&path->ip_leaf);
225 iam_path_release(path);
229 void iam_path_compat_init(struct iam_path_compat *path, struct inode *inode)
233 path->ipc_hinfo = &path->ipc_hinfo_area;
234 for (i = 0; i < ARRAY_SIZE(path->ipc_scratch); ++i)
235 path->ipc_descr.ipd_key_scratch[i] =
236 (struct iam_ikey *)&path->ipc_scratch[i];
238 iam_path_init(&path->ipc_path, &path->ipc_container, &path->ipc_descr);
241 void iam_path_compat_fini(struct iam_path_compat *path)
243 iam_path_fini(&path->ipc_path);
247 * Helper function initializing iam_path_descr and its key scratch area.
249 struct iam_path_descr *iam_ipd_alloc(void *area, int keysize)
251 struct iam_path_descr *ipd;
257 for (i = 0; i < ARRAY_SIZE(ipd->ipd_key_scratch); ++i, karea += keysize)
258 ipd->ipd_key_scratch[i] = karea;
261 EXPORT_SYMBOL(iam_ipd_alloc);
263 void iam_ipd_free(struct iam_path_descr *ipd)
266 EXPORT_SYMBOL(iam_ipd_free);
268 int iam_node_read(struct iam_container *c, iam_ptr_t ptr,
269 handle_t *h, struct buffer_head **bh)
273 /* NB: it can be called by iam_lfix_guess() which is still at
274 * very early stage, c->ic_root_bh and c->ic_descr->id_ops
275 * haven't been intialized yet.
276 * Also, we don't have this for IAM dir.
278 if (c->ic_root_bh != NULL &&
279 c->ic_descr->id_ops->id_root_ptr(c) == ptr) {
280 get_bh(c->ic_root_bh);
285 *bh = ldiskfs_bread(h, c->ic_object, (int)ptr, 0, &result);
292 * Return pointer to current leaf record. Pointer is valid while corresponding
293 * leaf node is locked and pinned.
295 static struct iam_rec *iam_leaf_rec(const struct iam_leaf *leaf)
297 return iam_leaf_ops(leaf)->rec(leaf);
301 * Return pointer to the current leaf key. This function returns pointer to
302 * the key stored in node.
304 * Caller should assume that returned pointer is only valid while leaf node is
307 static struct iam_key *iam_leaf_key(const struct iam_leaf *leaf)
309 return iam_leaf_ops(leaf)->key(leaf);
312 static int iam_leaf_key_size(const struct iam_leaf *leaf)
314 return iam_leaf_ops(leaf)->key_size(leaf);
317 static struct iam_ikey *iam_leaf_ikey(const struct iam_leaf *leaf,
318 struct iam_ikey *key)
320 return iam_leaf_ops(leaf)->ikey(leaf, key);
323 static int iam_leaf_keycmp(const struct iam_leaf *leaf,
324 const struct iam_key *key)
326 return iam_leaf_ops(leaf)->key_cmp(leaf, key);
329 static int iam_leaf_keyeq(const struct iam_leaf *leaf,
330 const struct iam_key *key)
332 return iam_leaf_ops(leaf)->key_eq(leaf, key);
335 #if LDISKFS_INVARIANT_ON
336 static int iam_leaf_check(struct iam_leaf *leaf);
337 extern int dx_node_check(struct iam_path *p, struct iam_frame *f);
339 static int iam_path_check(struct iam_path *p)
344 struct iam_descr *param;
347 param = iam_path_descr(p);
348 for (i = 0; result && i < ARRAY_SIZE(p->ip_frames); ++i) {
349 f = &p->ip_frames[i];
351 result = dx_node_check(p, f);
353 result = !param->id_ops->id_node_check(p, f);
356 if (result && p->ip_leaf.il_bh != NULL)
357 result = iam_leaf_check(&p->ip_leaf);
359 ldiskfs_std_error(iam_path_obj(p)->i_sb, result);
365 static int iam_leaf_load(struct iam_path *path)
369 struct iam_container *c;
370 struct buffer_head *bh;
371 struct iam_leaf *leaf;
372 struct iam_descr *descr;
374 c = path->ip_container;
375 leaf = &path->ip_leaf;
376 descr = iam_path_descr(path);
377 block = path->ip_frame->leaf;
380 printk(CFS_KERN_EMERG "wrong leaf: %lu %d [%p %p %p]\n",
381 (long unsigned)path->ip_frame->leaf,
382 dx_get_count(dx_node_get_entries(path, path->ip_frame)),
383 path->ip_frames[0].bh, path->ip_frames[1].bh,
384 path->ip_frames[2].bh);
386 err = descr->id_ops->id_node_read(c, block, NULL, &bh);
389 leaf->il_curidx = block;
390 err = iam_leaf_ops(leaf)->init(leaf);
391 assert_inv(ergo(err == 0, iam_leaf_check(leaf)));
396 static void iam_unlock_htree(struct iam_container *ic,
397 struct dynlock_handle *lh)
400 dynlock_unlock(&ic->ic_tree_lock, lh);
404 static void iam_leaf_unlock(struct iam_leaf *leaf)
406 if (leaf->il_lock != NULL) {
407 iam_unlock_htree(iam_leaf_container(leaf),
410 leaf->il_lock = NULL;
414 static void iam_leaf_fini(struct iam_leaf *leaf)
416 if (leaf->il_path != NULL) {
417 iam_leaf_unlock(leaf);
418 assert_inv(ergo(leaf->il_bh != NULL, iam_leaf_check(leaf)));
419 iam_leaf_ops(leaf)->fini(leaf);
428 static void iam_leaf_start(struct iam_leaf *folio)
430 iam_leaf_ops(folio)->start(folio);
433 void iam_leaf_next(struct iam_leaf *folio)
435 iam_leaf_ops(folio)->next(folio);
438 static void iam_leaf_rec_add(struct iam_leaf *leaf, const struct iam_key *key,
439 const struct iam_rec *rec)
441 iam_leaf_ops(leaf)->rec_add(leaf, key, rec);
444 static void iam_rec_del(struct iam_leaf *leaf, int shift)
446 iam_leaf_ops(leaf)->rec_del(leaf, shift);
449 int iam_leaf_at_end(const struct iam_leaf *leaf)
451 return iam_leaf_ops(leaf)->at_end(leaf);
454 void iam_leaf_split(struct iam_leaf *l, struct buffer_head **bh, iam_ptr_t nr)
456 iam_leaf_ops(l)->split(l, bh, nr);
459 int iam_leaf_can_add(const struct iam_leaf *l,
460 const struct iam_key *k, const struct iam_rec *r)
462 return iam_leaf_ops(l)->can_add(l, k, r);
465 #if LDISKFS_INVARIANT_ON
466 static int iam_leaf_check(struct iam_leaf *leaf)
470 struct iam_lentry *orig;
471 struct iam_path *path;
472 struct iam_container *bag;
479 path = iam_leaf_path(leaf);
480 bag = iam_leaf_container(leaf);
482 result = iam_leaf_ops(leaf)->init(leaf);
487 iam_leaf_start(leaf);
488 k0 = iam_path_ikey(path, 0);
489 k1 = iam_path_ikey(path, 1);
490 while (!iam_leaf_at_end(leaf)) {
491 iam_ikeycpy(bag, k0, k1);
492 iam_ikeycpy(bag, k1, iam_leaf_ikey(leaf, k1));
493 if (!first && iam_ikeycmp(bag, k0, k1) > 0) {
505 static int iam_txn_dirty(handle_t *handle,
506 struct iam_path *path, struct buffer_head *bh)
510 result = ldiskfs_journal_dirty_metadata(handle, bh);
512 ldiskfs_std_error(iam_path_obj(path)->i_sb, result);
516 static int iam_txn_add(handle_t *handle,
517 struct iam_path *path, struct buffer_head *bh)
521 result = ldiskfs_journal_get_write_access(handle, bh);
523 ldiskfs_std_error(iam_path_obj(path)->i_sb, result);
527 /***********************************************************************/
528 /* iterator interface */
529 /***********************************************************************/
531 static enum iam_it_state it_state(const struct iam_iterator *it)
537 * Helper function returning scratch key.
539 static struct iam_container *iam_it_container(const struct iam_iterator *it)
541 return it->ii_path.ip_container;
544 static inline int it_keycmp(const struct iam_iterator *it,
545 const struct iam_key *k)
547 return iam_leaf_keycmp(&it->ii_path.ip_leaf, k);
550 static inline int it_keyeq(const struct iam_iterator *it,
551 const struct iam_key *k)
553 return iam_leaf_keyeq(&it->ii_path.ip_leaf, k);
556 static int it_ikeycmp(const struct iam_iterator *it, const struct iam_ikey *ik)
558 return iam_ikeycmp(it->ii_path.ip_container,
559 iam_leaf_ikey(&it->ii_path.ip_leaf,
560 iam_path_ikey(&it->ii_path, 0)), ik);
563 static inline int it_at_rec(const struct iam_iterator *it)
565 return !iam_leaf_at_end(&it->ii_path.ip_leaf);
568 static inline int it_before(const struct iam_iterator *it)
570 return it_state(it) == IAM_IT_SKEWED && it_at_rec(it);
574 * Helper wrapper around iam_it_get(): returns 0 (success) only when record
575 * with exactly the same key as asked is found.
577 static int iam_it_get_exact(struct iam_iterator *it, const struct iam_key *k)
581 result = iam_it_get(it, k);
584 else if (result == 0)
586 * Return -ENOENT if cursor is located above record with a key
587 * different from one specified, or in the empty leaf.
589 * XXX returning -ENOENT only works if iam_it_get() never
590 * returns -ENOENT as a legitimate error.
596 void iam_container_write_lock(struct iam_container *ic)
598 cfs_down_write(&ic->ic_sem);
601 void iam_container_write_unlock(struct iam_container *ic)
603 cfs_up_write(&ic->ic_sem);
606 void iam_container_read_lock(struct iam_container *ic)
608 cfs_down_read(&ic->ic_sem);
611 void iam_container_read_unlock(struct iam_container *ic)
613 cfs_up_read(&ic->ic_sem);
617 * Initialize iterator to IAM_IT_DETACHED state.
619 * postcondition: it_state(it) == IAM_IT_DETACHED
621 int iam_it_init(struct iam_iterator *it, struct iam_container *c, __u32 flags,
622 struct iam_path_descr *pd)
624 memset(it, 0, sizeof *it);
625 it->ii_flags = flags;
626 it->ii_state = IAM_IT_DETACHED;
627 iam_path_init(&it->ii_path, c, pd);
630 EXPORT_SYMBOL(iam_it_init);
633 * Finalize iterator and release all resources.
635 * precondition: it_state(it) == IAM_IT_DETACHED
637 void iam_it_fini(struct iam_iterator *it)
639 assert_corr(it_state(it) == IAM_IT_DETACHED);
640 iam_path_fini(&it->ii_path);
642 EXPORT_SYMBOL(iam_it_fini);
645 * this locking primitives are used to protect parts
646 * of dir's htree. protection unit is block: leaf or index
648 static struct dynlock_handle *iam_lock_htree(struct iam_container *ic,
650 enum dynlock_type lt)
652 return dynlock_lock(&ic->ic_tree_lock, value, lt, GFP_NOFS);
655 int iam_index_lock(struct iam_path *path, struct dynlock_handle **lh)
659 for (f = path->ip_frame; f >= path->ip_frames; --f, ++lh) {
661 *lh = iam_lock_htree(path->ip_container, f->curidx, DLT_READ);
669 * Fast check for frame consistency.
671 static int iam_check_fast(struct iam_path *path, struct iam_frame *frame)
673 struct iam_container *bag;
674 struct iam_entry *next;
675 struct iam_entry *last;
676 struct iam_entry *entries;
677 struct iam_entry *at;
679 bag = path->ip_container;
681 entries = frame->entries;
682 last = iam_entry_shift(path, entries, dx_get_count(entries) - 1);
684 if (unlikely(at > last))
687 if (unlikely(dx_get_block(path, at) != frame->leaf))
690 if (unlikely(iam_ikeycmp(bag, iam_ikey_at(path, at),
691 path->ip_ikey_target) > 0))
694 next = iam_entry_shift(path, at, +1);
696 if (unlikely(iam_ikeycmp(bag, iam_ikey_at(path, next),
697 path->ip_ikey_target) <= 0))
703 int dx_index_is_compat(struct iam_path *path)
705 return iam_path_descr(path) == NULL;
711 * search position of specified hash in index
715 struct iam_entry *iam_find_position(struct iam_path *path,
716 struct iam_frame *frame)
723 count = dx_get_count(frame->entries);
724 assert_corr(count && count <= dx_get_limit(frame->entries));
725 p = iam_entry_shift(path, frame->entries,
726 dx_index_is_compat(path) ? 1 : 2);
727 q = iam_entry_shift(path, frame->entries, count - 1);
729 m = iam_entry_shift(path, p, iam_entry_diff(path, q, p) / 2);
730 if (iam_ikeycmp(path->ip_container, iam_ikey_at(path, m),
731 path->ip_ikey_target) > 0)
732 q = iam_entry_shift(path, m, -1);
734 p = iam_entry_shift(path, m, +1);
736 return iam_entry_shift(path, p, -1);
741 static iam_ptr_t iam_find_ptr(struct iam_path *path, struct iam_frame *frame)
743 return dx_get_block(path, iam_find_position(path, frame));
746 void iam_insert_key(struct iam_path *path, struct iam_frame *frame,
747 const struct iam_ikey *key, iam_ptr_t ptr)
749 struct iam_entry *entries = frame->entries;
750 struct iam_entry *new = iam_entry_shift(path, frame->at, +1);
751 int count = dx_get_count(entries);
754 * Unfortunately we cannot assert this, as this function is sometimes
755 * called by VFS under i_sem and without pdirops lock.
757 assert_corr(1 || iam_frame_is_locked(path, frame));
758 assert_corr(count < dx_get_limit(entries));
759 assert_corr(frame->at < iam_entry_shift(path, entries, count));
760 assert_inv(dx_node_check(path, frame));
762 memmove(iam_entry_shift(path, new, 1), new,
763 (char *)iam_entry_shift(path, entries, count) - (char *)new);
764 dx_set_ikey(path, new, key);
765 dx_set_block(path, new, ptr);
766 dx_set_count(entries, count + 1);
767 assert_inv(dx_node_check(path, frame));
770 void iam_insert_key_lock(struct iam_path *path, struct iam_frame *frame,
771 const struct iam_ikey *key, iam_ptr_t ptr)
773 iam_lock_bh(frame->bh);
774 iam_insert_key(path, frame, key, ptr);
775 iam_unlock_bh(frame->bh);
778 * returns 0 if path was unchanged, -EAGAIN otherwise.
780 static int iam_check_path(struct iam_path *path, struct iam_frame *frame)
784 iam_lock_bh(frame->bh);
785 equal = iam_check_fast(path, frame) == 0 ||
786 frame->leaf == iam_find_ptr(path, frame);
787 DX_DEVAL(iam_lock_stats.dls_bh_again += !equal);
788 iam_unlock_bh(frame->bh);
790 return equal ? 0 : -EAGAIN;
793 static int iam_lookup_try(struct iam_path *path)
799 struct iam_descr *param;
800 struct iam_frame *frame;
801 struct iam_container *c;
803 param = iam_path_descr(path);
804 c = path->ip_container;
806 ptr = param->id_ops->id_root_ptr(c);
807 for (frame = path->ip_frames, i = 0; i <= path->ip_indirect;
809 err = param->id_ops->id_node_read(c, (iam_ptr_t)ptr, NULL,
813 iam_lock_bh(frame->bh);
815 * node must be initialized under bh lock because concurrent
816 * creation procedure may change it and iam_lookup_try() will
817 * see obsolete tree height. -bzzz
822 if (LDISKFS_INVARIANT_ON) {
823 err = param->id_ops->id_node_check(path, frame);
828 err = param->id_ops->id_node_load(path, frame);
832 assert_inv(dx_node_check(path, frame));
834 * splitting may change root index block and move hash we're
835 * looking for into another index block so, we have to check
836 * this situation and repeat from begining if path got changed
840 err = iam_check_path(path, frame - 1);
845 frame->at = iam_find_position(path, frame);
847 frame->leaf = ptr = dx_get_block(path, frame->at);
849 iam_unlock_bh(frame->bh);
853 iam_unlock_bh(frame->bh);
854 path->ip_frame = --frame;
858 static int __iam_path_lookup(struct iam_path *path)
863 for (i = 0; i < DX_MAX_TREE_HEIGHT; ++ i)
864 assert(path->ip_frames[i].bh == NULL);
867 err = iam_lookup_try(path);
871 } while (err == -EAGAIN);
877 * returns 0 if path was unchanged, -EAGAIN otherwise.
879 static int iam_check_full_path(struct iam_path *path, int search)
881 struct iam_frame *bottom;
882 struct iam_frame *scan;
888 for (bottom = path->ip_frames, i = 0;
889 i < DX_MAX_TREE_HEIGHT && bottom->bh != NULL; ++bottom, ++i) {
890 ; /* find last filled in frame */
894 * Lock frames, bottom to top.
896 for (scan = bottom - 1; scan >= path->ip_frames; --scan)
897 iam_lock_bh(scan->bh);
899 * Check them top to bottom.
902 for (scan = path->ip_frames; scan < bottom; ++scan) {
903 struct iam_entry *pos;
906 if (iam_check_fast(path, scan) == 0)
909 pos = iam_find_position(path, scan);
910 if (scan->leaf != dx_get_block(path, pos)) {
916 pos = iam_entry_shift(path, scan->entries,
917 dx_get_count(scan->entries) - 1);
918 if (scan->at > pos ||
919 scan->leaf != dx_get_block(path, scan->at)) {
927 * Unlock top to bottom.
929 for (scan = path->ip_frames; scan < bottom; ++scan)
930 iam_unlock_bh(scan->bh);
931 DX_DEVAL(iam_lock_stats.dls_bh_full_again += !!result);
939 * Performs path lookup and returns with found leaf (if any) locked by htree
942 int iam_lookup_lock(struct iam_path *path,
943 struct dynlock_handle **dl, enum dynlock_type lt)
948 dir = iam_path_obj(path);
949 while ((result = __iam_path_lookup(path)) == 0) {
951 *dl = iam_lock_htree(path->ip_container, path->ip_frame->leaf,
960 * while locking leaf we just found may get split so we need
961 * to check this -bzzz
963 if (iam_check_full_path(path, 1) == 0)
965 iam_unlock_htree(path->ip_container, *dl);
972 * Performs tree top-to-bottom traversal starting from root, and loads leaf
975 static int iam_path_lookup(struct iam_path *path, int index)
977 struct iam_container *c;
978 struct iam_descr *descr;
979 struct iam_leaf *leaf;
982 c = path->ip_container;
983 leaf = &path->ip_leaf;
984 descr = iam_path_descr(path);
985 result = iam_lookup_lock(path, &leaf->il_lock, DLT_WRITE);
986 assert_inv(iam_path_check(path));
989 result = iam_leaf_load(path);
990 assert_inv(ergo(result == 0, iam_leaf_check(leaf)));
994 result = iam_leaf_ops(leaf)->
995 ilookup(leaf, path->ip_ikey_target);
997 result = iam_leaf_ops(leaf)->
998 lookup(leaf, path->ip_key_target);
1002 iam_leaf_unlock(leaf);
1008 * Common part of iam_it_{i,}get().
1010 static int __iam_it_get(struct iam_iterator *it, int index)
1013 assert_corr(it_state(it) == IAM_IT_DETACHED);
1015 result = iam_path_lookup(&it->ii_path, index);
1019 collision = result & IAM_LOOKUP_LAST;
1020 switch (result & ~IAM_LOOKUP_LAST) {
1021 case IAM_LOOKUP_EXACT:
1023 it->ii_state = IAM_IT_ATTACHED;
1027 it->ii_state = IAM_IT_ATTACHED;
1029 case IAM_LOOKUP_BEFORE:
1030 case IAM_LOOKUP_EMPTY:
1032 it->ii_state = IAM_IT_SKEWED;
1037 result |= collision;
1040 * See iam_it_get_exact() for explanation.
1042 assert_corr(result != -ENOENT);
1047 * Correct hash, but not the same key was found, iterate through hash
1048 * collision chain, looking for correct record.
1050 static int iam_it_collision(struct iam_iterator *it)
1054 assert(ergo(it_at_rec(it), !it_keyeq(it, it->ii_path.ip_key_target)));
1056 while ((result = iam_it_next(it)) == 0) {
1057 do_corr(schedule());
1058 if (it_ikeycmp(it, it->ii_path.ip_ikey_target) != 0)
1060 if (it_keyeq(it, it->ii_path.ip_key_target))
1067 * Attach iterator. After successful completion, @it points to record with
1068 * least key not larger than @k.
1070 * Return value: 0: positioned on existing record,
1071 * +ve: exact position found,
1074 * precondition: it_state(it) == IAM_IT_DETACHED
1075 * postcondition: ergo(result == 0 && it_state(it) == IAM_IT_ATTACHED,
1076 * it_keycmp(it, k) <= 0)
1078 int iam_it_get(struct iam_iterator *it, const struct iam_key *k)
1081 assert_corr(it_state(it) == IAM_IT_DETACHED);
1083 it->ii_path.ip_ikey_target = NULL;
1084 it->ii_path.ip_key_target = k;
1086 result = __iam_it_get(it, 0);
1088 if (result == IAM_LOOKUP_LAST) {
1089 result = iam_it_collision(it);
1093 result = __iam_it_get(it, 0);
1098 result &= ~IAM_LOOKUP_LAST;
1100 assert_corr(ergo(result > 0, it_keycmp(it, k) == 0));
1101 assert_corr(ergo(result == 0 && it_state(it) == IAM_IT_ATTACHED,
1102 it_keycmp(it, k) <= 0));
1105 EXPORT_SYMBOL(iam_it_get);
1108 * Attach iterator by index key.
1110 static int iam_it_iget(struct iam_iterator *it, const struct iam_ikey *k)
1112 assert_corr(it_state(it) == IAM_IT_DETACHED);
1114 it->ii_path.ip_ikey_target = k;
1115 return __iam_it_get(it, 1) & ~IAM_LOOKUP_LAST;
1119 * Attach iterator, and assure it points to the record (not skewed).
1121 * Return value: 0: positioned on existing record,
1122 * +ve: exact position found,
1125 * precondition: it_state(it) == IAM_IT_DETACHED &&
1126 * !(it->ii_flags&IAM_IT_WRITE)
1127 * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED)
1129 int iam_it_get_at(struct iam_iterator *it, const struct iam_key *k)
1132 assert_corr(it_state(it) == IAM_IT_DETACHED &&
1133 !(it->ii_flags&IAM_IT_WRITE));
1134 result = iam_it_get(it, k);
1136 if (it_state(it) != IAM_IT_ATTACHED) {
1137 assert_corr(it_state(it) == IAM_IT_SKEWED);
1138 result = iam_it_next(it);
1141 assert_corr(ergo(result >= 0, it_state(it) == IAM_IT_ATTACHED));
1144 EXPORT_SYMBOL(iam_it_get_at);
1147 * Duplicates iterator.
1149 * postcondition: it_state(dst) == it_state(src) &&
1150 * iam_it_container(dst) == iam_it_container(src) &&
1151 * dst->ii_flags = src->ii_flags &&
1152 * ergo(it_state(src) == IAM_IT_ATTACHED,
1153 * iam_it_rec_get(dst) == iam_it_rec_get(src) &&
1154 * iam_it_key_get(dst) == iam_it_key_get(src))
1156 void iam_it_dup(struct iam_iterator *dst, const struct iam_iterator *src)
1158 dst->ii_flags = src->ii_flags;
1159 dst->ii_state = src->ii_state;
1160 /* XXX not yet. iam_path_dup(&dst->ii_path, &src->ii_path); */
1162 * XXX: duplicate lock.
1164 assert_corr(it_state(dst) == it_state(src));
1165 assert_corr(iam_it_container(dst) == iam_it_container(src));
1166 assert_corr(dst->ii_flags = src->ii_flags);
1167 assert_corr(ergo(it_state(src) == IAM_IT_ATTACHED,
1168 iam_it_rec_get(dst) == iam_it_rec_get(src) &&
1169 iam_it_key_get(dst) == iam_it_key_get(src)));
1174 * Detach iterator. Does nothing it detached state.
1176 * postcondition: it_state(it) == IAM_IT_DETACHED
1178 void iam_it_put(struct iam_iterator *it)
1180 if (it->ii_state != IAM_IT_DETACHED) {
1181 it->ii_state = IAM_IT_DETACHED;
1182 iam_leaf_fini(&it->ii_path.ip_leaf);
1185 EXPORT_SYMBOL(iam_it_put);
1187 static struct iam_ikey *iam_it_ikey_get(const struct iam_iterator *it,
1188 struct iam_ikey *ikey);
1192 * This function increments the frame pointer to search the next leaf
1193 * block, and reads in the necessary intervening nodes if the search
1194 * should be necessary. Whether or not the search is necessary is
1195 * controlled by the hash parameter. If the hash value is even, then
1196 * the search is only continued if the next block starts with that
1197 * hash value. This is used if we are searching for a specific file.
1199 * If the hash value is HASH_NB_ALWAYS, then always go to the next block.
1201 * This function returns 1 if the caller should continue to search,
1202 * or 0 if it should not. If there is an error reading one of the
1203 * index blocks, it will a negative error code.
1205 * If start_hash is non-null, it will be filled in with the starting
1206 * hash of the next page.
1208 static int iam_htree_advance(struct inode *dir, __u32 hash,
1209 struct iam_path *path, __u32 *start_hash,
1212 struct iam_frame *p;
1213 struct buffer_head *bh;
1214 int err, num_frames = 0;
1219 * Find the next leaf page by incrementing the frame pointer.
1220 * If we run out of entries in the interior node, loop around and
1221 * increment pointer in the parent node. When we break out of
1222 * this loop, num_frames indicates the number of interior
1223 * nodes need to be read.
1226 do_corr(schedule());
1228 p->at = iam_entry_shift(path, p->at, +1);
1229 if (p->at < iam_entry_shift(path, p->entries,
1230 dx_get_count(p->entries))) {
1231 p->leaf = dx_get_block(path, p->at);
1232 iam_unlock_bh(p->bh);
1235 iam_unlock_bh(p->bh);
1236 if (p == path->ip_frames)
1247 * If the hash is 1, then continue only if the next page has a
1248 * continuation hash of any value. This is used for readdir
1249 * handling. Otherwise, check to see if the hash matches the
1250 * desired contiuation hash. If it doesn't, return since
1251 * there's no point to read in the successive index pages.
1253 dx_get_ikey(path, p->at, (struct iam_ikey *)&bhash);
1255 *start_hash = bhash;
1256 if ((hash & 1) == 0) {
1257 if ((bhash & ~1) != hash)
1262 * If the hash is HASH_NB_ALWAYS, we always go to the next
1263 * block so no check is necessary
1265 while (num_frames--) {
1268 do_corr(schedule());
1270 idx = p->leaf = dx_get_block(path, p->at);
1271 iam_unlock_bh(p->bh);
1272 err = iam_path_descr(path)->id_ops->
1273 id_node_read(path->ip_container, idx, NULL, &bh);
1275 return err; /* Failure */
1278 assert_corr(p->bh != bh);
1280 p->entries = dx_node_get_entries(path, p);
1281 p->at = iam_entry_shift(path, p->entries, !compat);
1282 assert_corr(p->curidx != idx);
1285 assert_corr(p->leaf != dx_get_block(path, p->at));
1286 p->leaf = dx_get_block(path, p->at);
1287 iam_unlock_bh(p->bh);
1288 assert_inv(dx_node_check(path, p));
1294 static inline int iam_index_advance(struct iam_path *path)
1296 return iam_htree_advance(iam_path_obj(path), 0, path, NULL, 0);
1299 static void iam_unlock_array(struct iam_container *ic,
1300 struct dynlock_handle **lh)
1304 for (i = 0; i < DX_MAX_TREE_HEIGHT; ++i, ++lh) {
1306 iam_unlock_htree(ic, *lh);
1312 * Advance index part of @path to point to the next leaf. Returns 1 on
1313 * success, 0, when end of container was reached. Leaf node is locked.
1315 int iam_index_next(struct iam_container *c, struct iam_path *path)
1318 struct dynlock_handle *lh[DX_MAX_TREE_HEIGHT] = { 0, };
1320 struct inode *object;
1323 * Locking for iam_index_next()... is to be described.
1326 object = c->ic_object;
1327 cursor = path->ip_frame->leaf;
1330 result = iam_index_lock(path, lh);
1331 do_corr(schedule());
1335 result = iam_check_full_path(path, 0);
1336 if (result == 0 && cursor == path->ip_frame->leaf) {
1337 result = iam_index_advance(path);
1339 assert_corr(result == 0 ||
1340 cursor != path->ip_frame->leaf);
1344 iam_unlock_array(c, lh);
1346 iam_path_release(path);
1347 do_corr(schedule());
1349 result = __iam_path_lookup(path);
1353 while (path->ip_frame->leaf != cursor) {
1354 do_corr(schedule());
1356 result = iam_index_lock(path, lh);
1357 do_corr(schedule());
1361 result = iam_check_full_path(path, 0);
1365 result = iam_index_advance(path);
1367 CERROR("cannot find cursor : %u\n",
1373 result = iam_check_full_path(path, 0);
1376 iam_unlock_array(c, lh);
1378 } while (result == -EAGAIN);
1382 iam_unlock_array(c, lh);
1387 * Move iterator one record right.
1389 * Return value: 0: success,
1390 * +1: end of container reached
1393 * precondition: (it_state(it) == IAM_IT_ATTACHED ||
1394 * it_state(it) == IAM_IT_SKEWED) && it->ii_flags&IAM_IT_MOVE
1395 * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED) &&
1396 * ergo(result > 0, it_state(it) == IAM_IT_DETACHED)
1398 int iam_it_next(struct iam_iterator *it)
1401 struct iam_path *path;
1402 struct iam_leaf *leaf;
1404 do_corr(struct iam_ikey *ik_orig);
1406 /* assert_corr(it->ii_flags&IAM_IT_MOVE); */
1407 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1408 it_state(it) == IAM_IT_SKEWED);
1410 path = &it->ii_path;
1411 leaf = &path->ip_leaf;
1412 obj = iam_path_obj(path);
1414 assert_corr(iam_leaf_is_locked(leaf));
1417 do_corr(ik_orig = it_at_rec(it) ?
1418 iam_it_ikey_get(it, iam_path_ikey(path, 2)) : NULL);
1419 if (it_before(it)) {
1420 assert_corr(!iam_leaf_at_end(leaf));
1421 it->ii_state = IAM_IT_ATTACHED;
1423 if (!iam_leaf_at_end(leaf))
1424 /* advance within leaf node */
1425 iam_leaf_next(leaf);
1427 * multiple iterations may be necessary due to empty leaves.
1429 while (result == 0 && iam_leaf_at_end(leaf)) {
1430 do_corr(schedule());
1431 /* advance index portion of the path */
1432 result = iam_index_next(iam_it_container(it), path);
1433 assert_corr(iam_leaf_is_locked(leaf));
1435 struct dynlock_handle *lh;
1436 lh = iam_lock_htree(iam_it_container(it),
1437 path->ip_frame->leaf,
1440 iam_leaf_fini(leaf);
1442 result = iam_leaf_load(path);
1444 iam_leaf_start(leaf);
1447 } else if (result == 0)
1448 /* end of container reached */
1454 it->ii_state = IAM_IT_ATTACHED;
1456 assert_corr(ergo(result == 0, it_state(it) == IAM_IT_ATTACHED));
1457 assert_corr(ergo(result > 0, it_state(it) == IAM_IT_DETACHED));
1458 assert_corr(ergo(result == 0 && ik_orig != NULL,
1459 it_ikeycmp(it, ik_orig) >= 0));
1462 EXPORT_SYMBOL(iam_it_next);
1465 * Return pointer to the record under iterator.
1467 * precondition: it_state(it) == IAM_IT_ATTACHED && it_at_rec(it)
1468 * postcondition: it_state(it) == IAM_IT_ATTACHED
1470 struct iam_rec *iam_it_rec_get(const struct iam_iterator *it)
1472 assert_corr(it_state(it) == IAM_IT_ATTACHED);
1473 assert_corr(it_at_rec(it));
1474 return iam_leaf_rec(&it->ii_path.ip_leaf);
1476 EXPORT_SYMBOL(iam_it_rec_get);
1478 static void iam_it_reccpy(struct iam_iterator *it, const struct iam_rec *r)
1480 struct iam_leaf *folio;
1482 folio = &it->ii_path.ip_leaf;
1483 iam_leaf_ops(folio)->rec_set(folio, r);
1487 * Replace contents of record under iterator.
1489 * precondition: it_state(it) == IAM_IT_ATTACHED &&
1490 * it->ii_flags&IAM_IT_WRITE
1491 * postcondition: it_state(it) == IAM_IT_ATTACHED &&
1492 * ergo(result == 0, !memcmp(iam_it_rec_get(it), r, ...))
1494 int iam_it_rec_set(handle_t *h,
1495 struct iam_iterator *it, const struct iam_rec *r)
1498 struct iam_path *path;
1499 struct buffer_head *bh;
1501 assert_corr(it_state(it) == IAM_IT_ATTACHED &&
1502 it->ii_flags&IAM_IT_WRITE);
1503 assert_corr(it_at_rec(it));
1505 path = &it->ii_path;
1506 bh = path->ip_leaf.il_bh;
1507 result = iam_txn_add(h, path, bh);
1509 iam_it_reccpy(it, r);
1510 result = iam_txn_dirty(h, path, bh);
1514 EXPORT_SYMBOL(iam_it_rec_set);
1517 * Return pointer to the index key under iterator.
1519 * precondition: it_state(it) == IAM_IT_ATTACHED ||
1520 * it_state(it) == IAM_IT_SKEWED
1522 static struct iam_ikey *iam_it_ikey_get(const struct iam_iterator *it,
1523 struct iam_ikey *ikey)
1525 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1526 it_state(it) == IAM_IT_SKEWED);
1527 assert_corr(it_at_rec(it));
1528 return iam_leaf_ikey(&it->ii_path.ip_leaf, ikey);
1532 * Return pointer to the key under iterator.
1534 * precondition: it_state(it) == IAM_IT_ATTACHED ||
1535 * it_state(it) == IAM_IT_SKEWED
1537 struct iam_key *iam_it_key_get(const struct iam_iterator *it)
1539 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1540 it_state(it) == IAM_IT_SKEWED);
1541 assert_corr(it_at_rec(it));
1542 return iam_leaf_key(&it->ii_path.ip_leaf);
1544 EXPORT_SYMBOL(iam_it_key_get);
1547 * Return size of key under iterator (in bytes)
1549 * precondition: it_state(it) == IAM_IT_ATTACHED ||
1550 * it_state(it) == IAM_IT_SKEWED
1552 int iam_it_key_size(const struct iam_iterator *it)
1554 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1555 it_state(it) == IAM_IT_SKEWED);
1556 assert_corr(it_at_rec(it));
1557 return iam_leaf_key_size(&it->ii_path.ip_leaf);
1559 EXPORT_SYMBOL(iam_it_key_size);
1562 * Insertion of new record. Interaction with jbd during non-trivial case (when
1563 * split happens) is as following:
1565 * - new leaf node is involved into transaction by ldiskfs_append();
1567 * - old leaf node is involved into transaction by iam_add_rec();
1569 * - leaf where insertion point ends in, is marked dirty by iam_add_rec();
1571 * - leaf without insertion point is marked dirty (as @new_leaf) by
1574 * - split index nodes are involved into transaction and marked dirty by
1575 * split_index_node().
1577 * - "safe" index node, which is no split, but where new pointer is inserted
1578 * is involved into transaction and marked dirty by split_index_node().
1580 * - index node where pointer to new leaf is inserted is involved into
1581 * transaction by split_index_node() and marked dirty by iam_add_rec().
1583 * - inode is marked dirty by iam_add_rec().
1587 static int iam_new_leaf(handle_t *handle, struct iam_leaf *leaf)
1591 struct buffer_head *new_leaf;
1592 struct buffer_head *old_leaf;
1593 struct iam_container *c;
1595 struct iam_path *path;
1597 assert_inv(iam_leaf_check(leaf));
1599 c = iam_leaf_container(leaf);
1600 path = leaf->il_path;
1603 new_leaf = ldiskfs_append(handle, obj, (__u32 *)&blknr, &err);
1604 do_corr(schedule());
1605 if (new_leaf != NULL) {
1606 struct dynlock_handle *lh;
1608 lh = iam_lock_htree(c, blknr, DLT_WRITE);
1609 do_corr(schedule());
1611 iam_leaf_ops(leaf)->init_new(c, new_leaf);
1612 do_corr(schedule());
1613 old_leaf = leaf->il_bh;
1614 iam_leaf_split(leaf, &new_leaf, blknr);
1615 if (old_leaf != leaf->il_bh) {
1617 * Switched to the new leaf.
1619 iam_leaf_unlock(leaf);
1621 path->ip_frame->leaf = blknr;
1623 iam_unlock_htree(path->ip_container, lh);
1624 do_corr(schedule());
1625 err = iam_txn_dirty(handle, path, new_leaf);
1628 err = ldiskfs_mark_inode_dirty(handle, obj);
1629 do_corr(schedule());
1633 assert_inv(iam_leaf_check(leaf));
1634 assert_inv(iam_leaf_check(&iam_leaf_path(leaf)->ip_leaf));
1635 assert_inv(iam_path_check(iam_leaf_path(leaf)));
1639 static inline void dx_set_limit(struct iam_entry *entries, unsigned value)
1641 ((struct dx_countlimit *) entries)->limit = cpu_to_le16(value);
1644 static int iam_shift_entries(struct iam_path *path,
1645 struct iam_frame *frame, unsigned count,
1646 struct iam_entry *entries, struct iam_entry *entries2,
1653 struct iam_frame *parent = frame - 1;
1654 struct iam_ikey *pivot = iam_path_ikey(path, 3);
1656 delta = dx_index_is_compat(path) ? 0 : +1;
1658 count1 = count/2 + delta;
1659 count2 = count - count1;
1660 dx_get_ikey(path, iam_entry_shift(path, entries, count1), pivot);
1662 dxtrace(printk("Split index %d/%d\n", count1, count2));
1664 memcpy((char *) iam_entry_shift(path, entries2, delta),
1665 (char *) iam_entry_shift(path, entries, count1),
1666 count2 * iam_entry_size(path));
1668 dx_set_count(entries2, count2 + delta);
1669 dx_set_limit(entries2, dx_node_limit(path));
1672 * NOTE: very subtle piece of code competing dx_probe() may find 2nd
1673 * level index in root index, then we insert new index here and set
1674 * new count in that 2nd level index. so, dx_probe() may see 2nd level
1675 * index w/o hash it looks for. the solution is to check root index
1676 * after we locked just founded 2nd level index -bzzz
1678 iam_insert_key_lock(path, parent, pivot, newblock);
1681 * now old and new 2nd level index blocks contain all pointers, so
1682 * dx_probe() may find it in the both. it's OK -bzzz
1684 iam_lock_bh(frame->bh);
1685 dx_set_count(entries, count1);
1686 iam_unlock_bh(frame->bh);
1689 * now old 2nd level index block points to first half of leafs. it's
1690 * importand that dx_probe() must check root index block for changes
1691 * under dx_lock_bh(frame->bh) -bzzz
1698 int split_index_node(handle_t *handle, struct iam_path *path,
1699 struct dynlock_handle **lh)
1702 struct iam_entry *entries; /* old block contents */
1703 struct iam_entry *entries2; /* new block contents */
1704 struct iam_frame *frame, *safe;
1705 struct buffer_head *bh_new[DX_MAX_TREE_HEIGHT] = {0};
1706 u32 newblock[DX_MAX_TREE_HEIGHT] = {0};
1707 struct dynlock_handle *lock[DX_MAX_TREE_HEIGHT] = {NULL,};
1708 struct dynlock_handle *new_lock[DX_MAX_TREE_HEIGHT] = {NULL,};
1709 struct inode *dir = iam_path_obj(path);
1710 struct iam_descr *descr;
1714 descr = iam_path_descr(path);
1716 * Algorithm below depends on this.
1718 assert_corr(dx_root_limit(path) < dx_node_limit(path));
1720 frame = path->ip_frame;
1721 entries = frame->entries;
1724 * Tall-tree handling: we might have to split multiple index blocks
1725 * all the way up to tree root. Tricky point here is error handling:
1726 * to avoid complicated undo/rollback we
1728 * - first allocate all necessary blocks
1730 * - insert pointers into them atomically.
1734 * Locking: leaf is already locked. htree-locks are acquired on all
1735 * index nodes that require split bottom-to-top, on the "safe" node,
1736 * and on all new nodes
1739 dxtrace(printk("using %u of %u node entries\n",
1740 dx_get_count(entries), dx_get_limit(entries)));
1742 /* What levels need split? */
1743 for (nr_splet = 0; frame >= path->ip_frames &&
1744 dx_get_count(frame->entries) == dx_get_limit(frame->entries);
1745 --frame, ++nr_splet) {
1746 do_corr(schedule());
1747 if (nr_splet == DX_MAX_TREE_HEIGHT) {
1749 CWARN(dir->i_sb, __FUNCTION__,
1750 "Directory index full!\n");
1760 * Lock all nodes, bottom to top.
1762 for (frame = path->ip_frame, i = nr_splet; i >= 0; --i, --frame) {
1763 do_corr(schedule());
1764 lock[i] = iam_lock_htree(path->ip_container, frame->curidx,
1766 if (lock[i] == NULL) {
1773 * Check for concurrent index modification.
1775 err = iam_check_full_path(path, 1);
1779 * And check that the same number of nodes is to be split.
1781 for (i = 0, frame = path->ip_frame; frame >= path->ip_frames &&
1782 dx_get_count(frame->entries) == dx_get_limit(frame->entries);
1786 if (i != nr_splet) {
1791 /* Go back down, allocating blocks, locking them, and adding into
1793 for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
1794 bh_new[i] = ldiskfs_append (handle, dir, &newblock[i], &err);
1795 do_corr(schedule());
1797 descr->id_ops->id_node_init(path->ip_container,
1800 new_lock[i] = iam_lock_htree(path->ip_container, newblock[i],
1802 if (new_lock[i] == NULL) {
1806 do_corr(schedule());
1807 BUFFER_TRACE(frame->bh, "get_write_access");
1808 err = ldiskfs_journal_get_write_access(handle, frame->bh);
1812 /* Add "safe" node to transaction too */
1813 if (safe + 1 != path->ip_frames) {
1814 do_corr(schedule());
1815 err = ldiskfs_journal_get_write_access(handle, safe->bh);
1820 /* Go through nodes once more, inserting pointers */
1821 for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
1824 struct buffer_head *bh2;
1825 struct buffer_head *bh;
1827 entries = frame->entries;
1828 count = dx_get_count(entries);
1829 idx = iam_entry_diff(path, frame->at, entries);
1832 entries2 = dx_get_entries(path, bh2->b_data, 0);
1835 if (frame == path->ip_frames) {
1836 /* splitting root node. Tricky point:
1838 * In the "normal" B-tree we'd split root *and* add
1839 * new root to the tree with pointers to the old root
1840 * and its sibling (thus introducing two new nodes).
1842 * In htree it's enough to add one node, because
1843 * capacity of the root node is smaller than that of
1846 struct iam_frame *frames;
1847 struct iam_entry *next;
1849 assert_corr(i == 0);
1851 do_corr(schedule());
1853 frames = path->ip_frames;
1854 memcpy((char *) entries2, (char *) entries,
1855 count * iam_entry_size(path));
1856 dx_set_limit(entries2, dx_node_limit(path));
1859 iam_lock_bh(frame->bh);
1860 next = descr->id_ops->id_root_inc(path->ip_container,
1862 dx_set_block(path, next, newblock[0]);
1863 iam_unlock_bh(frame->bh);
1865 do_corr(schedule());
1866 /* Shift frames in the path */
1867 memmove(frames + 2, frames + 1,
1868 (sizeof path->ip_frames) - 2 * sizeof frames[0]);
1869 /* Add new access path frame */
1870 frames[1].at = iam_entry_shift(path, entries2, idx);
1871 frames[1].entries = entries = entries2;
1873 assert_inv(dx_node_check(path, frame));
1876 assert_inv(dx_node_check(path, frame));
1877 bh_new[0] = NULL; /* buffer head is "consumed" */
1878 err = ldiskfs_journal_get_write_access(handle, bh2);
1881 do_corr(schedule());
1883 /* splitting non-root index node. */
1884 struct iam_frame *parent = frame - 1;
1886 do_corr(schedule());
1887 count = iam_shift_entries(path, frame, count,
1888 entries, entries2, newblock[i]);
1889 /* Which index block gets the new entry? */
1891 int d = dx_index_is_compat(path) ? 0 : +1;
1893 frame->at = iam_entry_shift(path, entries2,
1895 frame->entries = entries = entries2;
1896 frame->curidx = newblock[i];
1897 swap(frame->bh, bh2);
1898 assert_corr(lock[i + 1] != NULL);
1899 assert_corr(new_lock[i] != NULL);
1900 swap(lock[i + 1], new_lock[i]);
1902 parent->at = iam_entry_shift(path,
1905 assert_inv(dx_node_check(path, frame));
1906 assert_inv(dx_node_check(path, parent));
1907 dxtrace(dx_show_index ("node", frame->entries));
1908 dxtrace(dx_show_index ("node",
1909 ((struct dx_node *) bh2->b_data)->entries));
1910 err = ldiskfs_journal_dirty_metadata(handle, bh2);
1913 do_corr(schedule());
1914 err = ldiskfs_journal_dirty_metadata(handle, parent->bh);
1918 do_corr(schedule());
1919 err = ldiskfs_journal_dirty_metadata(handle, bh);
1924 * This function was called to make insertion of new leaf
1925 * possible. Check that it fulfilled its obligations.
1927 assert_corr(dx_get_count(path->ip_frame->entries) <
1928 dx_get_limit(path->ip_frame->entries));
1929 assert_corr(lock[nr_splet] != NULL);
1930 *lh = lock[nr_splet];
1931 lock[nr_splet] = NULL;
1934 * Log ->i_size modification.
1936 err = ldiskfs_mark_inode_dirty(handle, dir);
1942 ldiskfs_std_error(dir->i_sb, err);
1945 iam_unlock_array(path->ip_container, lock);
1946 iam_unlock_array(path->ip_container, new_lock);
1948 assert_corr(err || iam_frame_is_locked(path, path->ip_frame));
1950 do_corr(schedule());
1951 for (i = 0; i < ARRAY_SIZE(bh_new); ++i) {
1952 if (bh_new[i] != NULL)
1958 static int iam_add_rec(handle_t *handle, struct iam_iterator *it,
1959 struct iam_path *path,
1960 const struct iam_key *k, const struct iam_rec *r)
1963 struct iam_leaf *leaf;
1965 leaf = &path->ip_leaf;
1966 assert_inv(iam_leaf_check(leaf));
1967 assert_inv(iam_path_check(path));
1968 err = iam_txn_add(handle, path, leaf->il_bh);
1970 do_corr(schedule());
1971 if (!iam_leaf_can_add(leaf, k, r)) {
1972 struct dynlock_handle *lh = NULL;
1975 assert_corr(lh == NULL);
1976 do_corr(schedule());
1977 err = split_index_node(handle, path, &lh);
1978 if (err == -EAGAIN) {
1979 assert_corr(lh == NULL);
1981 iam_path_fini(path);
1982 it->ii_state = IAM_IT_DETACHED;
1984 do_corr(schedule());
1985 err = iam_it_get_exact(it, k);
1987 err = +1; /* repeat split */
1992 assert_inv(iam_path_check(path));
1994 assert_corr(lh != NULL);
1995 do_corr(schedule());
1996 err = iam_new_leaf(handle, leaf);
1998 err = iam_txn_dirty(handle, path,
1999 path->ip_frame->bh);
2001 iam_unlock_htree(path->ip_container, lh);
2002 do_corr(schedule());
2005 iam_leaf_rec_add(leaf, k, r);
2006 err = iam_txn_dirty(handle, path, leaf->il_bh);
2009 assert_inv(iam_leaf_check(leaf));
2010 assert_inv(iam_leaf_check(&path->ip_leaf));
2011 assert_inv(iam_path_check(path));
2016 * Insert new record with key @k and contents from @r, shifting records to the
2017 * right. On success, iterator is positioned on the newly inserted record.
2019 * precondition: it->ii_flags&IAM_IT_WRITE &&
2020 * (it_state(it) == IAM_IT_ATTACHED ||
2021 * it_state(it) == IAM_IT_SKEWED) &&
2022 * ergo(it_state(it) == IAM_IT_ATTACHED,
2023 * it_keycmp(it, k) <= 0) &&
2024 * ergo(it_before(it), it_keycmp(it, k) > 0));
2025 * postcondition: ergo(result == 0,
2026 * it_state(it) == IAM_IT_ATTACHED &&
2027 * it_keycmp(it, k) == 0 &&
2028 * !memcmp(iam_it_rec_get(it), r, ...))
2030 int iam_it_rec_insert(handle_t *h, struct iam_iterator *it,
2031 const struct iam_key *k, const struct iam_rec *r)
2034 struct iam_path *path;
2036 path = &it->ii_path;
2038 assert_corr(it->ii_flags&IAM_IT_WRITE);
2039 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
2040 it_state(it) == IAM_IT_SKEWED);
2041 assert_corr(ergo(it_state(it) == IAM_IT_ATTACHED,
2042 it_keycmp(it, k) <= 0));
2043 assert_corr(ergo(it_before(it), it_keycmp(it, k) > 0));
2044 result = iam_add_rec(h, it, path, k, r);
2046 it->ii_state = IAM_IT_ATTACHED;
2047 assert_corr(ergo(result == 0,
2048 it_state(it) == IAM_IT_ATTACHED &&
2049 it_keycmp(it, k) == 0));
2052 EXPORT_SYMBOL(iam_it_rec_insert);
2055 * Delete record under iterator.
2057 * precondition: it_state(it) == IAM_IT_ATTACHED &&
2058 * it->ii_flags&IAM_IT_WRITE &&
2060 * postcondition: it_state(it) == IAM_IT_ATTACHED ||
2061 * it_state(it) == IAM_IT_DETACHED
2063 int iam_it_rec_delete(handle_t *h, struct iam_iterator *it)
2066 struct iam_leaf *leaf;
2067 struct iam_path *path;
2069 assert_corr(it_state(it) == IAM_IT_ATTACHED &&
2070 it->ii_flags&IAM_IT_WRITE);
2071 assert_corr(it_at_rec(it));
2073 path = &it->ii_path;
2074 leaf = &path->ip_leaf;
2076 assert_inv(iam_leaf_check(leaf));
2077 assert_inv(iam_path_check(path));
2079 result = iam_txn_add(h, path, leaf->il_bh);
2081 * no compaction for now.
2084 iam_rec_del(leaf, it->ii_flags&IAM_IT_MOVE);
2085 result = iam_txn_dirty(h, path, leaf->il_bh);
2086 if (result == 0 && iam_leaf_at_end(leaf) &&
2087 it->ii_flags&IAM_IT_MOVE) {
2088 result = iam_it_next(it);
2093 assert_inv(iam_leaf_check(leaf));
2094 assert_inv(iam_path_check(path));
2095 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
2096 it_state(it) == IAM_IT_DETACHED);
2099 EXPORT_SYMBOL(iam_it_rec_delete);
2102 * Convert iterator to cookie.
2104 * precondition: it_state(it) == IAM_IT_ATTACHED &&
2105 * iam_path_descr(it->ii_path)->id_key_size <= sizeof(iam_pos_t)
2106 * postcondition: it_state(it) == IAM_IT_ATTACHED
2108 iam_pos_t iam_it_store(const struct iam_iterator *it)
2112 assert_corr(it_state(it) == IAM_IT_ATTACHED);
2113 assert_corr(it_at_rec(it));
2114 assert_corr(iam_it_container(it)->ic_descr->id_ikey_size <=
2118 return *(iam_pos_t *)iam_it_ikey_get(it, (void *)&result);
2120 EXPORT_SYMBOL(iam_it_store);
2123 * Restore iterator from cookie.
2125 * precondition: it_state(it) == IAM_IT_DETACHED && it->ii_flags&IAM_IT_MOVE &&
2126 * iam_path_descr(it->ii_path)->id_key_size <= sizeof(iam_pos_t)
2127 * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED &&
2128 * iam_it_store(it) == pos)
2130 int iam_it_load(struct iam_iterator *it, iam_pos_t pos)
2132 assert_corr(it_state(it) == IAM_IT_DETACHED &&
2133 it->ii_flags&IAM_IT_MOVE);
2134 assert_corr(iam_it_container(it)->ic_descr->id_ikey_size <= sizeof pos);
2135 return iam_it_iget(it, (struct iam_ikey *)&pos);
2137 EXPORT_SYMBOL(iam_it_load);
2139 /***********************************************************************/
2141 /***********************************************************************/
2143 static inline int ptr_inside(void *base, size_t size, void *ptr)
2145 return (base <= ptr) && (ptr < base + size);
2148 int iam_frame_invariant(struct iam_frame *f)
2152 f->bh->b_data != NULL &&
2153 ptr_inside(f->bh->b_data, f->bh->b_size, f->entries) &&
2154 ptr_inside(f->bh->b_data, f->bh->b_size, f->at) &&
2155 f->entries <= f->at);
2157 int iam_leaf_invariant(struct iam_leaf *l)
2161 l->il_bh->b_data != NULL &&
2162 ptr_inside(l->il_bh->b_data, l->il_bh->b_size, l->il_entries) &&
2163 ptr_inside(l->il_bh->b_data, l->il_bh->b_size, l->il_at) &&
2164 l->il_entries <= l->il_at;
2167 int iam_path_invariant(struct iam_path *p)
2171 if (p->ip_container == NULL ||
2172 p->ip_indirect < 0 || p->ip_indirect > DX_MAX_TREE_HEIGHT - 1 ||
2173 p->ip_frame != p->ip_frames + p->ip_indirect ||
2174 !iam_leaf_invariant(&p->ip_leaf))
2176 for (i = 0; i < ARRAY_SIZE(p->ip_frames); ++i) {
2177 if (i <= p->ip_indirect) {
2178 if (!iam_frame_invariant(&p->ip_frames[i]))
2185 int iam_it_invariant(struct iam_iterator *it)
2188 (it->ii_state == IAM_IT_DETACHED ||
2189 it->ii_state == IAM_IT_ATTACHED ||
2190 it->ii_state == IAM_IT_SKEWED) &&
2191 !(it->ii_flags & ~(IAM_IT_MOVE | IAM_IT_WRITE)) &&
2192 ergo(it->ii_state == IAM_IT_ATTACHED ||
2193 it->ii_state == IAM_IT_SKEWED,
2194 iam_path_invariant(&it->ii_path) &&
2195 equi(it_at_rec(it), it->ii_state == IAM_IT_SKEWED));
2199 * Search container @c for record with key @k. If record is found, its data
2200 * are moved into @r.
2202 * Return values: 0: found, -ENOENT: not-found, -ve: error
2204 int iam_lookup(struct iam_container *c, const struct iam_key *k,
2205 struct iam_rec *r, struct iam_path_descr *pd)
2207 struct iam_iterator it;
2210 iam_it_init(&it, c, 0, pd);
2212 result = iam_it_get_exact(&it, k);
2215 * record with required key found, copy it into user buffer
2217 iam_reccpy(&it.ii_path.ip_leaf, r);
2222 EXPORT_SYMBOL(iam_lookup);
2225 * Insert new record @r with key @k into container @c (within context of
2228 * Return values: 0: success, -ve: error, including -EEXIST when record with
2229 * given key is already present.
2231 * postcondition: ergo(result == 0 || result == -EEXIST,
2232 * iam_lookup(c, k, r2) > 0;
2234 int iam_insert(handle_t *h, struct iam_container *c, const struct iam_key *k,
2235 const struct iam_rec *r, struct iam_path_descr *pd)
2237 struct iam_iterator it;
2240 iam_it_init(&it, c, IAM_IT_WRITE, pd);
2242 result = iam_it_get_exact(&it, k);
2243 if (result == -ENOENT)
2244 result = iam_it_rec_insert(h, &it, k, r);
2245 else if (result == 0)
2251 EXPORT_SYMBOL(iam_insert);
2254 * Update record with the key @k in container @c (within context of
2255 * transaction @h), new record is given by @r.
2257 * Return values: +1: skip because of the same rec value, 0: success,
2258 * -ve: error, including -ENOENT if no record with the given key found.
2260 int iam_update(handle_t *h, struct iam_container *c, const struct iam_key *k,
2261 const struct iam_rec *r, struct iam_path_descr *pd)
2263 struct iam_iterator it;
2264 struct iam_leaf *folio;
2267 iam_it_init(&it, c, IAM_IT_WRITE, pd);
2269 result = iam_it_get_exact(&it, k);
2271 folio = &it.ii_path.ip_leaf;
2272 result = iam_leaf_ops(folio)->rec_eq(folio, r);
2274 iam_it_rec_set(h, &it, r);
2282 EXPORT_SYMBOL(iam_update);
2285 * Delete existing record with key @k.
2287 * Return values: 0: success, -ENOENT: not-found, -ve: other error.
2289 * postcondition: ergo(result == 0 || result == -ENOENT,
2290 * !iam_lookup(c, k, *));
2292 int iam_delete(handle_t *h, struct iam_container *c, const struct iam_key *k,
2293 struct iam_path_descr *pd)
2295 struct iam_iterator it;
2298 iam_it_init(&it, c, IAM_IT_WRITE, pd);
2300 result = iam_it_get_exact(&it, k);
2302 iam_it_rec_delete(h, &it);
2307 EXPORT_SYMBOL(iam_delete);
2309 int iam_root_limit(int rootgap, int blocksize, int size)
2314 limit = (blocksize - rootgap) / size;
2315 nlimit = blocksize / size;
2316 if (limit == nlimit)