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.
104 * The IAM root block is a special node, which contains the IAM descriptor.
105 * It is on disk format:
107 * +---------+-------+--------+---------+-------+------+-------+------------+
108 * |IAM desc | count | idle | | | | | |
109 * |(fix/var)| / | blocks | padding | entry | .... | entry | free space |
110 * | | limit | | | | | | |
111 * +---------+-------+--------+---------+-------+------+-------+------------+
113 * The padding length is calculated with the parameters in the IAM descriptor.
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.
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
128 * The idle blocks pool is organized as a series of tables, and each table
129 * can be described as following (on-disk format):
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 * +---------+---------+---------+---------+------+---------+-------+
137 * The logic blk# for the first table is stored in the root node "idle_blocks".
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 #include "osd_internal.h"
156 * List of all registered formats.
158 * No locking. Callers synchronize.
160 static CFS_LIST_HEAD(iam_formats);
162 void iam_format_register(struct iam_format *fmt)
164 cfs_list_add(&fmt->if_linkage, &iam_formats);
166 EXPORT_SYMBOL(iam_format_register);
168 static struct buffer_head *
169 iam_load_idle_blocks(struct iam_container *c, iam_ptr_t blk)
171 struct inode *inode = c->ic_object;
172 struct iam_idle_head *head;
173 struct buffer_head *bh;
176 LASSERT_SEM_LOCKED(&c->ic_idle_sem);
181 bh = ldiskfs_bread(NULL, inode, blk, 0, &err);
183 CERROR("%.16s: cannot load idle blocks, blk = %u, err = %d\n",
184 LDISKFS_SB(inode->i_sb)->s_es->s_volume_name, blk, err);
185 c->ic_idle_failed = 1;
189 head = (struct iam_idle_head *)(bh->b_data);
190 if (le16_to_cpu(head->iih_magic) != IAM_IDLE_HEADER_MAGIC) {
191 CERROR("%.16s: invalid idle block head, blk = %u, magic = %d\n",
192 LDISKFS_SB(inode->i_sb)->s_es->s_volume_name, blk,
193 le16_to_cpu(head->iih_magic));
195 c->ic_idle_failed = 1;
196 return ERR_PTR(-EBADF);
203 * Determine format of given container. This is done by scanning list of
204 * registered formats and calling ->if_guess() method of each in turn.
206 static int iam_format_guess(struct iam_container *c)
209 struct iam_format *fmt;
212 * XXX temporary initialization hook.
215 static int initialized = 0;
218 iam_lvar_format_init();
219 iam_lfix_format_init();
225 cfs_list_for_each_entry(fmt, &iam_formats, if_linkage) {
226 result = fmt->if_guess(c);
232 struct buffer_head *bh;
235 LASSERT(c->ic_root_bh != NULL);
237 idle_blocks = (__u32 *)(c->ic_root_bh->b_data +
238 c->ic_descr->id_root_gap +
239 sizeof(struct dx_countlimit));
240 cfs_down(&c->ic_idle_sem);
241 bh = iam_load_idle_blocks(c, le32_to_cpu(*idle_blocks));
242 if (bh != NULL && IS_ERR(bh))
243 result = PTR_ERR(bh);
246 cfs_up(&c->ic_idle_sem);
253 * Initialize container @c.
255 int iam_container_init(struct iam_container *c,
256 struct iam_descr *descr, struct inode *inode)
258 memset(c, 0, sizeof *c);
260 c->ic_object = inode;
261 cfs_init_rwsem(&c->ic_sem);
262 dynlock_init(&c->ic_tree_lock);
263 cfs_sema_init(&c->ic_idle_sem, 1);
266 EXPORT_SYMBOL(iam_container_init);
269 * Determine container format.
271 int iam_container_setup(struct iam_container *c)
273 return iam_format_guess(c);
275 EXPORT_SYMBOL(iam_container_setup);
278 * Finalize container @c, release all resources.
280 void iam_container_fini(struct iam_container *c)
282 brelse(c->ic_idle_bh);
283 c->ic_idle_bh = NULL;
284 brelse(c->ic_root_bh);
285 c->ic_root_bh = NULL;
287 EXPORT_SYMBOL(iam_container_fini);
289 void iam_path_init(struct iam_path *path, struct iam_container *c,
290 struct iam_path_descr *pd)
292 memset(path, 0, sizeof *path);
293 path->ip_container = c;
294 path->ip_frame = path->ip_frames;
296 path->ip_leaf.il_path = path;
299 static void iam_leaf_fini(struct iam_leaf *leaf);
301 void iam_path_release(struct iam_path *path)
305 for (i = 0; i < ARRAY_SIZE(path->ip_frames); i++) {
306 if (path->ip_frames[i].bh != NULL) {
307 brelse(path->ip_frames[i].bh);
308 path->ip_frames[i].bh = NULL;
313 void iam_path_fini(struct iam_path *path)
315 iam_leaf_fini(&path->ip_leaf);
316 iam_path_release(path);
320 void iam_path_compat_init(struct iam_path_compat *path, struct inode *inode)
324 path->ipc_hinfo = &path->ipc_hinfo_area;
325 for (i = 0; i < ARRAY_SIZE(path->ipc_scratch); ++i)
326 path->ipc_descr.ipd_key_scratch[i] =
327 (struct iam_ikey *)&path->ipc_scratch[i];
329 iam_path_init(&path->ipc_path, &path->ipc_container, &path->ipc_descr);
332 void iam_path_compat_fini(struct iam_path_compat *path)
334 iam_path_fini(&path->ipc_path);
338 * Helper function initializing iam_path_descr and its key scratch area.
340 struct iam_path_descr *iam_ipd_alloc(void *area, int keysize)
342 struct iam_path_descr *ipd;
348 for (i = 0; i < ARRAY_SIZE(ipd->ipd_key_scratch); ++i, karea += keysize)
349 ipd->ipd_key_scratch[i] = karea;
352 EXPORT_SYMBOL(iam_ipd_alloc);
354 void iam_ipd_free(struct iam_path_descr *ipd)
357 EXPORT_SYMBOL(iam_ipd_free);
359 int iam_node_read(struct iam_container *c, iam_ptr_t ptr,
360 handle_t *h, struct buffer_head **bh)
364 /* NB: it can be called by iam_lfix_guess() which is still at
365 * very early stage, c->ic_root_bh and c->ic_descr->id_ops
366 * haven't been intialized yet.
367 * Also, we don't have this for IAM dir.
369 if (c->ic_root_bh != NULL &&
370 c->ic_descr->id_ops->id_root_ptr(c) == ptr) {
371 get_bh(c->ic_root_bh);
376 *bh = ldiskfs_bread(h, c->ic_object, (int)ptr, 0, &result);
383 * Return pointer to current leaf record. Pointer is valid while corresponding
384 * leaf node is locked and pinned.
386 static struct iam_rec *iam_leaf_rec(const struct iam_leaf *leaf)
388 return iam_leaf_ops(leaf)->rec(leaf);
392 * Return pointer to the current leaf key. This function returns pointer to
393 * the key stored in node.
395 * Caller should assume that returned pointer is only valid while leaf node is
398 static struct iam_key *iam_leaf_key(const struct iam_leaf *leaf)
400 return iam_leaf_ops(leaf)->key(leaf);
403 static int iam_leaf_key_size(const struct iam_leaf *leaf)
405 return iam_leaf_ops(leaf)->key_size(leaf);
408 static struct iam_ikey *iam_leaf_ikey(const struct iam_leaf *leaf,
409 struct iam_ikey *key)
411 return iam_leaf_ops(leaf)->ikey(leaf, key);
414 static int iam_leaf_keycmp(const struct iam_leaf *leaf,
415 const struct iam_key *key)
417 return iam_leaf_ops(leaf)->key_cmp(leaf, key);
420 static int iam_leaf_keyeq(const struct iam_leaf *leaf,
421 const struct iam_key *key)
423 return iam_leaf_ops(leaf)->key_eq(leaf, key);
426 #if LDISKFS_INVARIANT_ON
427 static int iam_leaf_check(struct iam_leaf *leaf);
428 extern int dx_node_check(struct iam_path *p, struct iam_frame *f);
430 static int iam_path_check(struct iam_path *p)
435 struct iam_descr *param;
438 param = iam_path_descr(p);
439 for (i = 0; result && i < ARRAY_SIZE(p->ip_frames); ++i) {
440 f = &p->ip_frames[i];
442 result = dx_node_check(p, f);
444 result = !param->id_ops->id_node_check(p, f);
447 if (result && p->ip_leaf.il_bh != NULL)
448 result = iam_leaf_check(&p->ip_leaf);
450 ldiskfs_std_error(iam_path_obj(p)->i_sb, result);
456 static int iam_leaf_load(struct iam_path *path)
460 struct iam_container *c;
461 struct buffer_head *bh;
462 struct iam_leaf *leaf;
463 struct iam_descr *descr;
465 c = path->ip_container;
466 leaf = &path->ip_leaf;
467 descr = iam_path_descr(path);
468 block = path->ip_frame->leaf;
471 printk(CFS_KERN_EMERG "wrong leaf: %lu %d [%p %p %p]\n",
472 (long unsigned)path->ip_frame->leaf,
473 dx_get_count(dx_node_get_entries(path, path->ip_frame)),
474 path->ip_frames[0].bh, path->ip_frames[1].bh,
475 path->ip_frames[2].bh);
477 err = descr->id_ops->id_node_read(c, block, NULL, &bh);
480 leaf->il_curidx = block;
481 err = iam_leaf_ops(leaf)->init(leaf);
482 assert_inv(ergo(err == 0, iam_leaf_check(leaf)));
487 static void iam_unlock_htree(struct iam_container *ic,
488 struct dynlock_handle *lh)
491 dynlock_unlock(&ic->ic_tree_lock, lh);
495 static void iam_leaf_unlock(struct iam_leaf *leaf)
497 if (leaf->il_lock != NULL) {
498 iam_unlock_htree(iam_leaf_container(leaf),
501 leaf->il_lock = NULL;
505 static void iam_leaf_fini(struct iam_leaf *leaf)
507 if (leaf->il_path != NULL) {
508 iam_leaf_unlock(leaf);
509 assert_inv(ergo(leaf->il_bh != NULL, iam_leaf_check(leaf)));
510 iam_leaf_ops(leaf)->fini(leaf);
519 static void iam_leaf_start(struct iam_leaf *folio)
521 iam_leaf_ops(folio)->start(folio);
524 void iam_leaf_next(struct iam_leaf *folio)
526 iam_leaf_ops(folio)->next(folio);
529 static void iam_leaf_rec_add(struct iam_leaf *leaf, const struct iam_key *key,
530 const struct iam_rec *rec)
532 iam_leaf_ops(leaf)->rec_add(leaf, key, rec);
535 static void iam_rec_del(struct iam_leaf *leaf, int shift)
537 iam_leaf_ops(leaf)->rec_del(leaf, shift);
540 int iam_leaf_at_end(const struct iam_leaf *leaf)
542 return iam_leaf_ops(leaf)->at_end(leaf);
545 void iam_leaf_split(struct iam_leaf *l, struct buffer_head **bh, iam_ptr_t nr)
547 iam_leaf_ops(l)->split(l, bh, nr);
550 static inline int iam_leaf_empty(struct iam_leaf *l)
552 return iam_leaf_ops(l)->leaf_empty(l);
555 int iam_leaf_can_add(const struct iam_leaf *l,
556 const struct iam_key *k, const struct iam_rec *r)
558 return iam_leaf_ops(l)->can_add(l, k, r);
561 #if LDISKFS_INVARIANT_ON
562 static int iam_leaf_check(struct iam_leaf *leaf)
566 struct iam_lentry *orig;
567 struct iam_path *path;
568 struct iam_container *bag;
575 path = iam_leaf_path(leaf);
576 bag = iam_leaf_container(leaf);
578 result = iam_leaf_ops(leaf)->init(leaf);
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) {
601 static int iam_txn_dirty(handle_t *handle,
602 struct iam_path *path, struct buffer_head *bh)
606 result = ldiskfs_journal_dirty_metadata(handle, bh);
608 ldiskfs_std_error(iam_path_obj(path)->i_sb, result);
612 static int iam_txn_add(handle_t *handle,
613 struct iam_path *path, struct buffer_head *bh)
617 result = ldiskfs_journal_get_write_access(handle, bh);
619 ldiskfs_std_error(iam_path_obj(path)->i_sb, result);
623 /***********************************************************************/
624 /* iterator interface */
625 /***********************************************************************/
627 static enum iam_it_state it_state(const struct iam_iterator *it)
633 * Helper function returning scratch key.
635 static struct iam_container *iam_it_container(const struct iam_iterator *it)
637 return it->ii_path.ip_container;
640 static inline int it_keycmp(const struct iam_iterator *it,
641 const struct iam_key *k)
643 return iam_leaf_keycmp(&it->ii_path.ip_leaf, k);
646 static inline int it_keyeq(const struct iam_iterator *it,
647 const struct iam_key *k)
649 return iam_leaf_keyeq(&it->ii_path.ip_leaf, k);
652 static int it_ikeycmp(const struct iam_iterator *it, const struct iam_ikey *ik)
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);
659 static inline int it_at_rec(const struct iam_iterator *it)
661 return !iam_leaf_at_end(&it->ii_path.ip_leaf);
664 static inline int it_before(const struct iam_iterator *it)
666 return it_state(it) == IAM_IT_SKEWED && it_at_rec(it);
670 * Helper wrapper around iam_it_get(): returns 0 (success) only when record
671 * with exactly the same key as asked is found.
673 static int iam_it_get_exact(struct iam_iterator *it, const struct iam_key *k)
677 result = iam_it_get(it, k);
680 else if (result == 0)
682 * Return -ENOENT if cursor is located above record with a key
683 * different from one specified, or in the empty leaf.
685 * XXX returning -ENOENT only works if iam_it_get() never
686 * returns -ENOENT as a legitimate error.
692 void iam_container_write_lock(struct iam_container *ic)
694 cfs_down_write(&ic->ic_sem);
697 void iam_container_write_unlock(struct iam_container *ic)
699 cfs_up_write(&ic->ic_sem);
702 void iam_container_read_lock(struct iam_container *ic)
704 cfs_down_read(&ic->ic_sem);
707 void iam_container_read_unlock(struct iam_container *ic)
709 cfs_up_read(&ic->ic_sem);
713 * Initialize iterator to IAM_IT_DETACHED state.
715 * postcondition: it_state(it) == IAM_IT_DETACHED
717 int iam_it_init(struct iam_iterator *it, struct iam_container *c, __u32 flags,
718 struct iam_path_descr *pd)
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);
726 EXPORT_SYMBOL(iam_it_init);
729 * Finalize iterator and release all resources.
731 * precondition: it_state(it) == IAM_IT_DETACHED
733 void iam_it_fini(struct iam_iterator *it)
735 assert_corr(it_state(it) == IAM_IT_DETACHED);
736 iam_path_fini(&it->ii_path);
738 EXPORT_SYMBOL(iam_it_fini);
741 * this locking primitives are used to protect parts
742 * of dir's htree. protection unit is block: leaf or index
744 static struct dynlock_handle *iam_lock_htree(struct iam_container *ic,
746 enum dynlock_type lt)
748 return dynlock_lock(&ic->ic_tree_lock, value, lt, GFP_NOFS);
751 int iam_index_lock(struct iam_path *path, struct dynlock_handle **lh)
755 for (f = path->ip_frame; f >= path->ip_frames; --f, ++lh) {
757 *lh = iam_lock_htree(path->ip_container, f->curidx, DLT_READ);
765 * Fast check for frame consistency.
767 static int iam_check_fast(struct iam_path *path, struct iam_frame *frame)
769 struct iam_container *bag;
770 struct iam_entry *next;
771 struct iam_entry *last;
772 struct iam_entry *entries;
773 struct iam_entry *at;
775 bag = path->ip_container;
777 entries = frame->entries;
778 last = iam_entry_shift(path, entries, dx_get_count(entries) - 1);
780 if (unlikely(at > last))
783 if (unlikely(dx_get_block(path, at) != frame->leaf))
786 if (unlikely(iam_ikeycmp(bag, iam_ikey_at(path, at),
787 path->ip_ikey_target) > 0))
790 next = iam_entry_shift(path, at, +1);
792 if (unlikely(iam_ikeycmp(bag, iam_ikey_at(path, next),
793 path->ip_ikey_target) <= 0))
799 int dx_index_is_compat(struct iam_path *path)
801 return iam_path_descr(path) == NULL;
807 * search position of specified hash in index
811 struct iam_entry *iam_find_position(struct iam_path *path,
812 struct iam_frame *frame)
819 count = dx_get_count(frame->entries);
820 assert_corr(count && count <= dx_get_limit(frame->entries));
821 p = iam_entry_shift(path, frame->entries,
822 dx_index_is_compat(path) ? 1 : 2);
823 q = iam_entry_shift(path, frame->entries, count - 1);
825 m = iam_entry_shift(path, p, iam_entry_diff(path, q, p) / 2);
826 if (iam_ikeycmp(path->ip_container, iam_ikey_at(path, m),
827 path->ip_ikey_target) > 0)
828 q = iam_entry_shift(path, m, -1);
830 p = iam_entry_shift(path, m, +1);
832 return iam_entry_shift(path, p, -1);
837 static iam_ptr_t iam_find_ptr(struct iam_path *path, struct iam_frame *frame)
839 return dx_get_block(path, iam_find_position(path, frame));
842 void iam_insert_key(struct iam_path *path, struct iam_frame *frame,
843 const struct iam_ikey *key, iam_ptr_t ptr)
845 struct iam_entry *entries = frame->entries;
846 struct iam_entry *new = iam_entry_shift(path, frame->at, +1);
847 int count = dx_get_count(entries);
850 * Unfortunately we cannot assert this, as this function is sometimes
851 * called by VFS under i_sem and without pdirops lock.
853 assert_corr(1 || iam_frame_is_locked(path, frame));
854 assert_corr(count < dx_get_limit(entries));
855 assert_corr(frame->at < iam_entry_shift(path, entries, count));
856 assert_inv(dx_node_check(path, frame));
858 memmove(iam_entry_shift(path, new, 1), new,
859 (char *)iam_entry_shift(path, entries, count) - (char *)new);
860 dx_set_ikey(path, new, key);
861 dx_set_block(path, new, ptr);
862 dx_set_count(entries, count + 1);
863 assert_inv(dx_node_check(path, frame));
866 void iam_insert_key_lock(struct iam_path *path, struct iam_frame *frame,
867 const struct iam_ikey *key, iam_ptr_t ptr)
869 iam_lock_bh(frame->bh);
870 iam_insert_key(path, frame, key, ptr);
871 iam_unlock_bh(frame->bh);
874 * returns 0 if path was unchanged, -EAGAIN otherwise.
876 static int iam_check_path(struct iam_path *path, struct iam_frame *frame)
880 iam_lock_bh(frame->bh);
881 equal = iam_check_fast(path, frame) == 0 ||
882 frame->leaf == iam_find_ptr(path, frame);
883 DX_DEVAL(iam_lock_stats.dls_bh_again += !equal);
884 iam_unlock_bh(frame->bh);
886 return equal ? 0 : -EAGAIN;
889 static int iam_lookup_try(struct iam_path *path)
895 struct iam_descr *param;
896 struct iam_frame *frame;
897 struct iam_container *c;
899 param = iam_path_descr(path);
900 c = path->ip_container;
902 ptr = param->id_ops->id_root_ptr(c);
903 for (frame = path->ip_frames, i = 0; i <= path->ip_indirect;
905 err = param->id_ops->id_node_read(c, (iam_ptr_t)ptr, NULL,
909 iam_lock_bh(frame->bh);
911 * node must be initialized under bh lock because concurrent
912 * creation procedure may change it and iam_lookup_try() will
913 * see obsolete tree height. -bzzz
918 if (LDISKFS_INVARIANT_ON) {
919 err = param->id_ops->id_node_check(path, frame);
924 err = param->id_ops->id_node_load(path, frame);
928 assert_inv(dx_node_check(path, frame));
930 * splitting may change root index block and move hash we're
931 * looking for into another index block so, we have to check
932 * this situation and repeat from begining if path got changed
936 err = iam_check_path(path, frame - 1);
941 frame->at = iam_find_position(path, frame);
943 frame->leaf = ptr = dx_get_block(path, frame->at);
945 iam_unlock_bh(frame->bh);
949 iam_unlock_bh(frame->bh);
950 path->ip_frame = --frame;
954 static int __iam_path_lookup(struct iam_path *path)
959 for (i = 0; i < DX_MAX_TREE_HEIGHT; ++ i)
960 assert(path->ip_frames[i].bh == NULL);
963 err = iam_lookup_try(path);
967 } while (err == -EAGAIN);
973 * returns 0 if path was unchanged, -EAGAIN otherwise.
975 static int iam_check_full_path(struct iam_path *path, int search)
977 struct iam_frame *bottom;
978 struct iam_frame *scan;
984 for (bottom = path->ip_frames, i = 0;
985 i < DX_MAX_TREE_HEIGHT && bottom->bh != NULL; ++bottom, ++i) {
986 ; /* find last filled in frame */
990 * Lock frames, bottom to top.
992 for (scan = bottom - 1; scan >= path->ip_frames; --scan)
993 iam_lock_bh(scan->bh);
995 * Check them top to bottom.
998 for (scan = path->ip_frames; scan < bottom; ++scan) {
999 struct iam_entry *pos;
1002 if (iam_check_fast(path, scan) == 0)
1005 pos = iam_find_position(path, scan);
1006 if (scan->leaf != dx_get_block(path, pos)) {
1012 pos = iam_entry_shift(path, scan->entries,
1013 dx_get_count(scan->entries) - 1);
1014 if (scan->at > pos ||
1015 scan->leaf != dx_get_block(path, scan->at)) {
1023 * Unlock top to bottom.
1025 for (scan = path->ip_frames; scan < bottom; ++scan)
1026 iam_unlock_bh(scan->bh);
1027 DX_DEVAL(iam_lock_stats.dls_bh_full_again += !!result);
1028 do_corr(schedule());
1035 * Performs path lookup and returns with found leaf (if any) locked by htree
1038 int iam_lookup_lock(struct iam_path *path,
1039 struct dynlock_handle **dl, enum dynlock_type lt)
1044 dir = iam_path_obj(path);
1045 while ((result = __iam_path_lookup(path)) == 0) {
1046 do_corr(schedule());
1047 *dl = iam_lock_htree(path->ip_container, path->ip_frame->leaf,
1050 iam_path_fini(path);
1054 do_corr(schedule());
1056 * while locking leaf we just found may get split so we need
1057 * to check this -bzzz
1059 if (iam_check_full_path(path, 1) == 0)
1061 iam_unlock_htree(path->ip_container, *dl);
1063 iam_path_fini(path);
1068 * Performs tree top-to-bottom traversal starting from root, and loads leaf
1071 static int iam_path_lookup(struct iam_path *path, int index)
1073 struct iam_container *c;
1074 struct iam_descr *descr;
1075 struct iam_leaf *leaf;
1078 c = path->ip_container;
1079 leaf = &path->ip_leaf;
1080 descr = iam_path_descr(path);
1081 result = iam_lookup_lock(path, &leaf->il_lock, DLT_WRITE);
1082 assert_inv(iam_path_check(path));
1083 do_corr(schedule());
1085 result = iam_leaf_load(path);
1086 assert_inv(ergo(result == 0, iam_leaf_check(leaf)));
1088 do_corr(schedule());
1090 result = iam_leaf_ops(leaf)->
1091 ilookup(leaf, path->ip_ikey_target);
1093 result = iam_leaf_ops(leaf)->
1094 lookup(leaf, path->ip_key_target);
1095 do_corr(schedule());
1098 iam_leaf_unlock(leaf);
1104 * Common part of iam_it_{i,}get().
1106 static int __iam_it_get(struct iam_iterator *it, int index)
1109 assert_corr(it_state(it) == IAM_IT_DETACHED);
1111 result = iam_path_lookup(&it->ii_path, index);
1115 collision = result & IAM_LOOKUP_LAST;
1116 switch (result & ~IAM_LOOKUP_LAST) {
1117 case IAM_LOOKUP_EXACT:
1119 it->ii_state = IAM_IT_ATTACHED;
1123 it->ii_state = IAM_IT_ATTACHED;
1125 case IAM_LOOKUP_BEFORE:
1126 case IAM_LOOKUP_EMPTY:
1128 it->ii_state = IAM_IT_SKEWED;
1133 result |= collision;
1136 * See iam_it_get_exact() for explanation.
1138 assert_corr(result != -ENOENT);
1143 * Correct hash, but not the same key was found, iterate through hash
1144 * collision chain, looking for correct record.
1146 static int iam_it_collision(struct iam_iterator *it)
1150 assert(ergo(it_at_rec(it), !it_keyeq(it, it->ii_path.ip_key_target)));
1152 while ((result = iam_it_next(it)) == 0) {
1153 do_corr(schedule());
1154 if (it_ikeycmp(it, it->ii_path.ip_ikey_target) != 0)
1156 if (it_keyeq(it, it->ii_path.ip_key_target))
1163 * Attach iterator. After successful completion, @it points to record with
1164 * least key not larger than @k.
1166 * Return value: 0: positioned on existing record,
1167 * +ve: exact position found,
1170 * precondition: it_state(it) == IAM_IT_DETACHED
1171 * postcondition: ergo(result == 0 && it_state(it) == IAM_IT_ATTACHED,
1172 * it_keycmp(it, k) <= 0)
1174 int iam_it_get(struct iam_iterator *it, const struct iam_key *k)
1177 assert_corr(it_state(it) == IAM_IT_DETACHED);
1179 it->ii_path.ip_ikey_target = NULL;
1180 it->ii_path.ip_key_target = k;
1182 result = __iam_it_get(it, 0);
1184 if (result == IAM_LOOKUP_LAST) {
1185 result = iam_it_collision(it);
1189 result = __iam_it_get(it, 0);
1194 result &= ~IAM_LOOKUP_LAST;
1196 assert_corr(ergo(result > 0, it_keycmp(it, k) == 0));
1197 assert_corr(ergo(result == 0 && it_state(it) == IAM_IT_ATTACHED,
1198 it_keycmp(it, k) <= 0));
1201 EXPORT_SYMBOL(iam_it_get);
1204 * Attach iterator by index key.
1206 static int iam_it_iget(struct iam_iterator *it, const struct iam_ikey *k)
1208 assert_corr(it_state(it) == IAM_IT_DETACHED);
1210 it->ii_path.ip_ikey_target = k;
1211 return __iam_it_get(it, 1) & ~IAM_LOOKUP_LAST;
1215 * Attach iterator, and assure it points to the record (not skewed).
1217 * Return value: 0: positioned on existing record,
1218 * +ve: exact position found,
1221 * precondition: it_state(it) == IAM_IT_DETACHED &&
1222 * !(it->ii_flags&IAM_IT_WRITE)
1223 * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED)
1225 int iam_it_get_at(struct iam_iterator *it, const struct iam_key *k)
1228 assert_corr(it_state(it) == IAM_IT_DETACHED &&
1229 !(it->ii_flags&IAM_IT_WRITE));
1230 result = iam_it_get(it, k);
1232 if (it_state(it) != IAM_IT_ATTACHED) {
1233 assert_corr(it_state(it) == IAM_IT_SKEWED);
1234 result = iam_it_next(it);
1237 assert_corr(ergo(result >= 0, it_state(it) == IAM_IT_ATTACHED));
1240 EXPORT_SYMBOL(iam_it_get_at);
1243 * Duplicates iterator.
1245 * postcondition: it_state(dst) == it_state(src) &&
1246 * iam_it_container(dst) == iam_it_container(src) &&
1247 * dst->ii_flags = src->ii_flags &&
1248 * ergo(it_state(src) == IAM_IT_ATTACHED,
1249 * iam_it_rec_get(dst) == iam_it_rec_get(src) &&
1250 * iam_it_key_get(dst) == iam_it_key_get(src))
1252 void iam_it_dup(struct iam_iterator *dst, const struct iam_iterator *src)
1254 dst->ii_flags = src->ii_flags;
1255 dst->ii_state = src->ii_state;
1256 /* XXX not yet. iam_path_dup(&dst->ii_path, &src->ii_path); */
1258 * XXX: duplicate lock.
1260 assert_corr(it_state(dst) == it_state(src));
1261 assert_corr(iam_it_container(dst) == iam_it_container(src));
1262 assert_corr(dst->ii_flags = src->ii_flags);
1263 assert_corr(ergo(it_state(src) == IAM_IT_ATTACHED,
1264 iam_it_rec_get(dst) == iam_it_rec_get(src) &&
1265 iam_it_key_get(dst) == iam_it_key_get(src)));
1270 * Detach iterator. Does nothing it detached state.
1272 * postcondition: it_state(it) == IAM_IT_DETACHED
1274 void iam_it_put(struct iam_iterator *it)
1276 if (it->ii_state != IAM_IT_DETACHED) {
1277 it->ii_state = IAM_IT_DETACHED;
1278 iam_leaf_fini(&it->ii_path.ip_leaf);
1281 EXPORT_SYMBOL(iam_it_put);
1283 static struct iam_ikey *iam_it_ikey_get(const struct iam_iterator *it,
1284 struct iam_ikey *ikey);
1288 * This function increments the frame pointer to search the next leaf
1289 * block, and reads in the necessary intervening nodes if the search
1290 * should be necessary. Whether or not the search is necessary is
1291 * controlled by the hash parameter. If the hash value is even, then
1292 * the search is only continued if the next block starts with that
1293 * hash value. This is used if we are searching for a specific file.
1295 * If the hash value is HASH_NB_ALWAYS, then always go to the next block.
1297 * This function returns 1 if the caller should continue to search,
1298 * or 0 if it should not. If there is an error reading one of the
1299 * index blocks, it will a negative error code.
1301 * If start_hash is non-null, it will be filled in with the starting
1302 * hash of the next page.
1304 static int iam_htree_advance(struct inode *dir, __u32 hash,
1305 struct iam_path *path, __u32 *start_hash,
1308 struct iam_frame *p;
1309 struct buffer_head *bh;
1310 int err, num_frames = 0;
1315 * Find the next leaf page by incrementing the frame pointer.
1316 * If we run out of entries in the interior node, loop around and
1317 * increment pointer in the parent node. When we break out of
1318 * this loop, num_frames indicates the number of interior
1319 * nodes need to be read.
1322 do_corr(schedule());
1327 p->at = iam_entry_shift(path, p->at, +1);
1328 if (p->at < iam_entry_shift(path, p->entries,
1329 dx_get_count(p->entries))) {
1330 p->leaf = dx_get_block(path, p->at);
1331 iam_unlock_bh(p->bh);
1334 iam_unlock_bh(p->bh);
1335 if (p == path->ip_frames)
1346 * If the hash is 1, then continue only if the next page has a
1347 * continuation hash of any value. This is used for readdir
1348 * handling. Otherwise, check to see if the hash matches the
1349 * desired contiuation hash. If it doesn't, return since
1350 * there's no point to read in the successive index pages.
1352 dx_get_ikey(path, p->at, (struct iam_ikey *)&bhash);
1354 *start_hash = bhash;
1355 if ((hash & 1) == 0) {
1356 if ((bhash & ~1) != hash)
1361 * If the hash is HASH_NB_ALWAYS, we always go to the next
1362 * block so no check is necessary
1364 while (num_frames--) {
1367 do_corr(schedule());
1369 idx = p->leaf = dx_get_block(path, p->at);
1370 iam_unlock_bh(p->bh);
1371 err = iam_path_descr(path)->id_ops->
1372 id_node_read(path->ip_container, idx, NULL, &bh);
1374 return err; /* Failure */
1377 assert_corr(p->bh != bh);
1379 p->entries = dx_node_get_entries(path, p);
1380 p->at = iam_entry_shift(path, p->entries, !compat);
1381 assert_corr(p->curidx != idx);
1384 assert_corr(p->leaf != dx_get_block(path, p->at));
1385 p->leaf = dx_get_block(path, p->at);
1386 iam_unlock_bh(p->bh);
1387 assert_inv(dx_node_check(path, p));
1393 static inline int iam_index_advance(struct iam_path *path)
1395 return iam_htree_advance(iam_path_obj(path), 0, path, NULL, 0);
1398 static void iam_unlock_array(struct iam_container *ic,
1399 struct dynlock_handle **lh)
1403 for (i = 0; i < DX_MAX_TREE_HEIGHT; ++i, ++lh) {
1405 iam_unlock_htree(ic, *lh);
1411 * Advance index part of @path to point to the next leaf. Returns 1 on
1412 * success, 0, when end of container was reached. Leaf node is locked.
1414 int iam_index_next(struct iam_container *c, struct iam_path *path)
1417 struct dynlock_handle *lh[DX_MAX_TREE_HEIGHT] = { 0, };
1419 struct inode *object;
1422 * Locking for iam_index_next()... is to be described.
1425 object = c->ic_object;
1426 cursor = path->ip_frame->leaf;
1429 result = iam_index_lock(path, lh);
1430 do_corr(schedule());
1434 result = iam_check_full_path(path, 0);
1435 if (result == 0 && cursor == path->ip_frame->leaf) {
1436 result = iam_index_advance(path);
1438 assert_corr(result == 0 ||
1439 cursor != path->ip_frame->leaf);
1443 iam_unlock_array(c, lh);
1445 iam_path_release(path);
1446 do_corr(schedule());
1448 result = __iam_path_lookup(path);
1452 while (path->ip_frame->leaf != cursor) {
1453 do_corr(schedule());
1455 result = iam_index_lock(path, lh);
1456 do_corr(schedule());
1460 result = iam_check_full_path(path, 0);
1464 result = iam_index_advance(path);
1466 CERROR("cannot find cursor : %u\n",
1472 result = iam_check_full_path(path, 0);
1475 iam_unlock_array(c, lh);
1477 } while (result == -EAGAIN);
1481 iam_unlock_array(c, lh);
1486 * Move iterator one record right.
1488 * Return value: 0: success,
1489 * +1: end of container reached
1492 * precondition: (it_state(it) == IAM_IT_ATTACHED ||
1493 * it_state(it) == IAM_IT_SKEWED) && it->ii_flags&IAM_IT_MOVE
1494 * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED) &&
1495 * ergo(result > 0, it_state(it) == IAM_IT_DETACHED)
1497 int iam_it_next(struct iam_iterator *it)
1500 struct iam_path *path;
1501 struct iam_leaf *leaf;
1503 do_corr(struct iam_ikey *ik_orig);
1505 /* assert_corr(it->ii_flags&IAM_IT_MOVE); */
1506 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1507 it_state(it) == IAM_IT_SKEWED);
1509 path = &it->ii_path;
1510 leaf = &path->ip_leaf;
1511 obj = iam_path_obj(path);
1513 assert_corr(iam_leaf_is_locked(leaf));
1516 do_corr(ik_orig = it_at_rec(it) ?
1517 iam_it_ikey_get(it, iam_path_ikey(path, 2)) : NULL);
1518 if (it_before(it)) {
1519 assert_corr(!iam_leaf_at_end(leaf));
1520 it->ii_state = IAM_IT_ATTACHED;
1522 if (!iam_leaf_at_end(leaf))
1523 /* advance within leaf node */
1524 iam_leaf_next(leaf);
1526 * multiple iterations may be necessary due to empty leaves.
1528 while (result == 0 && iam_leaf_at_end(leaf)) {
1529 do_corr(schedule());
1530 /* advance index portion of the path */
1531 result = iam_index_next(iam_it_container(it), path);
1532 assert_corr(iam_leaf_is_locked(leaf));
1534 struct dynlock_handle *lh;
1535 lh = iam_lock_htree(iam_it_container(it),
1536 path->ip_frame->leaf,
1539 iam_leaf_fini(leaf);
1541 result = iam_leaf_load(path);
1543 iam_leaf_start(leaf);
1546 } else if (result == 0)
1547 /* end of container reached */
1553 it->ii_state = IAM_IT_ATTACHED;
1555 assert_corr(ergo(result == 0, it_state(it) == IAM_IT_ATTACHED));
1556 assert_corr(ergo(result > 0, it_state(it) == IAM_IT_DETACHED));
1557 assert_corr(ergo(result == 0 && ik_orig != NULL,
1558 it_ikeycmp(it, ik_orig) >= 0));
1561 EXPORT_SYMBOL(iam_it_next);
1564 * Return pointer to the record under iterator.
1566 * precondition: it_state(it) == IAM_IT_ATTACHED && it_at_rec(it)
1567 * postcondition: it_state(it) == IAM_IT_ATTACHED
1569 struct iam_rec *iam_it_rec_get(const struct iam_iterator *it)
1571 assert_corr(it_state(it) == IAM_IT_ATTACHED);
1572 assert_corr(it_at_rec(it));
1573 return iam_leaf_rec(&it->ii_path.ip_leaf);
1575 EXPORT_SYMBOL(iam_it_rec_get);
1577 static void iam_it_reccpy(struct iam_iterator *it, const struct iam_rec *r)
1579 struct iam_leaf *folio;
1581 folio = &it->ii_path.ip_leaf;
1582 iam_leaf_ops(folio)->rec_set(folio, r);
1586 * Replace contents of record under iterator.
1588 * precondition: it_state(it) == IAM_IT_ATTACHED &&
1589 * it->ii_flags&IAM_IT_WRITE
1590 * postcondition: it_state(it) == IAM_IT_ATTACHED &&
1591 * ergo(result == 0, !memcmp(iam_it_rec_get(it), r, ...))
1593 int iam_it_rec_set(handle_t *h,
1594 struct iam_iterator *it, const struct iam_rec *r)
1597 struct iam_path *path;
1598 struct buffer_head *bh;
1600 assert_corr(it_state(it) == IAM_IT_ATTACHED &&
1601 it->ii_flags&IAM_IT_WRITE);
1602 assert_corr(it_at_rec(it));
1604 path = &it->ii_path;
1605 bh = path->ip_leaf.il_bh;
1606 result = iam_txn_add(h, path, bh);
1608 iam_it_reccpy(it, r);
1609 result = iam_txn_dirty(h, path, bh);
1613 EXPORT_SYMBOL(iam_it_rec_set);
1616 * Return pointer to the index key under iterator.
1618 * precondition: it_state(it) == IAM_IT_ATTACHED ||
1619 * it_state(it) == IAM_IT_SKEWED
1621 static struct iam_ikey *iam_it_ikey_get(const struct iam_iterator *it,
1622 struct iam_ikey *ikey)
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_ikey(&it->ii_path.ip_leaf, ikey);
1631 * Return pointer to the key under iterator.
1633 * precondition: it_state(it) == IAM_IT_ATTACHED ||
1634 * it_state(it) == IAM_IT_SKEWED
1636 struct iam_key *iam_it_key_get(const struct iam_iterator *it)
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(&it->ii_path.ip_leaf);
1643 EXPORT_SYMBOL(iam_it_key_get);
1646 * Return size of key under iterator (in bytes)
1648 * precondition: it_state(it) == IAM_IT_ATTACHED ||
1649 * it_state(it) == IAM_IT_SKEWED
1651 int iam_it_key_size(const struct iam_iterator *it)
1653 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1654 it_state(it) == IAM_IT_SKEWED);
1655 assert_corr(it_at_rec(it));
1656 return iam_leaf_key_size(&it->ii_path.ip_leaf);
1658 EXPORT_SYMBOL(iam_it_key_size);
1660 struct buffer_head *
1661 iam_new_node(handle_t *h, struct iam_container *c, iam_ptr_t *b, int *e)
1663 struct inode *inode = c->ic_object;
1664 struct buffer_head *bh = NULL;
1665 struct iam_idle_head *head;
1666 struct buffer_head *idle;
1670 if (c->ic_idle_bh == NULL)
1673 cfs_down(&c->ic_idle_sem);
1674 if (unlikely(c->ic_idle_failed || c->ic_idle_bh == NULL)) {
1675 cfs_up(&c->ic_idle_sem);
1679 head = (struct iam_idle_head *)(c->ic_idle_bh->b_data);
1680 count = le16_to_cpu(head->iih_count);
1682 *e = ldiskfs_journal_get_write_access(h, c->ic_idle_bh);
1687 *b = le32_to_cpu(head->iih_blks[count]);
1688 head->iih_count = cpu_to_le16(count);
1689 *e = ldiskfs_journal_dirty_metadata(h, c->ic_idle_bh);
1693 cfs_up(&c->ic_idle_sem);
1694 bh = ldiskfs_bread(NULL, inode, *b, 0, e);
1700 /* The block itself which contains the iam_idle_head is
1701 * also an idle block, and can be used as the new node. */
1702 idle_blocks = (__u32 *)(c->ic_root_bh->b_data +
1703 c->ic_descr->id_root_gap +
1704 sizeof(struct dx_countlimit));
1705 *e = ldiskfs_journal_get_write_access(h, c->ic_root_bh);
1709 *b = le32_to_cpu(*idle_blocks);
1710 iam_lock_bh(c->ic_root_bh);
1711 *idle_blocks = head->iih_next;
1712 iam_unlock_bh(c->ic_root_bh);
1713 *e = ldiskfs_journal_dirty_metadata(h, c->ic_root_bh);
1715 iam_lock_bh(c->ic_root_bh);
1716 *idle_blocks = cpu_to_le32(*b);
1717 iam_unlock_bh(c->ic_root_bh);
1722 idle = iam_load_idle_blocks(c, le32_to_cpu(*idle_blocks));
1723 if (idle != NULL && IS_ERR(idle)) {
1725 c->ic_idle_bh = NULL;
1730 c->ic_idle_bh = idle;
1731 cfs_up(&c->ic_idle_sem);
1734 /* get write access for the found buffer head */
1735 *e = ldiskfs_journal_get_write_access(h, bh);
1739 ldiskfs_std_error(inode->i_sb, *e);
1744 bh = ldiskfs_append(h, inode, b, e);
1748 cfs_up(&c->ic_idle_sem);
1749 ldiskfs_std_error(inode->i_sb, *e);
1754 * Insertion of new record. Interaction with jbd during non-trivial case (when
1755 * split happens) is as following:
1757 * - new leaf node is involved into transaction by iam_new_node();
1759 * - old leaf node is involved into transaction by iam_add_rec();
1761 * - leaf where insertion point ends in, is marked dirty by iam_add_rec();
1763 * - leaf without insertion point is marked dirty (as @new_leaf) by
1766 * - split index nodes are involved into transaction and marked dirty by
1767 * split_index_node().
1769 * - "safe" index node, which is no split, but where new pointer is inserted
1770 * is involved into transaction and marked dirty by split_index_node().
1772 * - index node where pointer to new leaf is inserted is involved into
1773 * transaction by split_index_node() and marked dirty by iam_add_rec().
1775 * - inode is marked dirty by iam_add_rec().
1779 static int iam_new_leaf(handle_t *handle, struct iam_leaf *leaf)
1783 struct buffer_head *new_leaf;
1784 struct buffer_head *old_leaf;
1785 struct iam_container *c;
1787 struct iam_path *path;
1789 assert_inv(iam_leaf_check(leaf));
1791 c = iam_leaf_container(leaf);
1792 path = leaf->il_path;
1795 new_leaf = iam_new_node(handle, c, &blknr, &err);
1796 do_corr(schedule());
1797 if (new_leaf != NULL) {
1798 struct dynlock_handle *lh;
1800 lh = iam_lock_htree(c, blknr, DLT_WRITE);
1801 do_corr(schedule());
1803 iam_leaf_ops(leaf)->init_new(c, new_leaf);
1804 do_corr(schedule());
1805 old_leaf = leaf->il_bh;
1806 iam_leaf_split(leaf, &new_leaf, blknr);
1807 if (old_leaf != leaf->il_bh) {
1809 * Switched to the new leaf.
1811 iam_leaf_unlock(leaf);
1813 path->ip_frame->leaf = blknr;
1815 iam_unlock_htree(path->ip_container, lh);
1816 do_corr(schedule());
1817 err = iam_txn_dirty(handle, path, new_leaf);
1820 err = ldiskfs_mark_inode_dirty(handle, obj);
1821 do_corr(schedule());
1825 assert_inv(iam_leaf_check(leaf));
1826 assert_inv(iam_leaf_check(&iam_leaf_path(leaf)->ip_leaf));
1827 assert_inv(iam_path_check(iam_leaf_path(leaf)));
1831 static inline void dx_set_limit(struct iam_entry *entries, unsigned value)
1833 ((struct dx_countlimit *) entries)->limit = cpu_to_le16(value);
1836 static int iam_shift_entries(struct iam_path *path,
1837 struct iam_frame *frame, unsigned count,
1838 struct iam_entry *entries, struct iam_entry *entries2,
1845 struct iam_frame *parent = frame - 1;
1846 struct iam_ikey *pivot = iam_path_ikey(path, 3);
1848 delta = dx_index_is_compat(path) ? 0 : +1;
1850 count1 = count/2 + delta;
1851 count2 = count - count1;
1852 dx_get_ikey(path, iam_entry_shift(path, entries, count1), pivot);
1854 dxtrace(printk("Split index %d/%d\n", count1, count2));
1856 memcpy((char *) iam_entry_shift(path, entries2, delta),
1857 (char *) iam_entry_shift(path, entries, count1),
1858 count2 * iam_entry_size(path));
1860 dx_set_count(entries2, count2 + delta);
1861 dx_set_limit(entries2, dx_node_limit(path));
1864 * NOTE: very subtle piece of code competing dx_probe() may find 2nd
1865 * level index in root index, then we insert new index here and set
1866 * new count in that 2nd level index. so, dx_probe() may see 2nd level
1867 * index w/o hash it looks for. the solution is to check root index
1868 * after we locked just founded 2nd level index -bzzz
1870 iam_insert_key_lock(path, parent, pivot, newblock);
1873 * now old and new 2nd level index blocks contain all pointers, so
1874 * dx_probe() may find it in the both. it's OK -bzzz
1876 iam_lock_bh(frame->bh);
1877 dx_set_count(entries, count1);
1878 iam_unlock_bh(frame->bh);
1881 * now old 2nd level index block points to first half of leafs. it's
1882 * importand that dx_probe() must check root index block for changes
1883 * under dx_lock_bh(frame->bh) -bzzz
1890 int split_index_node(handle_t *handle, struct iam_path *path,
1891 struct dynlock_handle **lh)
1894 struct iam_entry *entries; /* old block contents */
1895 struct iam_entry *entries2; /* new block contents */
1896 struct iam_frame *frame, *safe;
1897 struct buffer_head *bh_new[DX_MAX_TREE_HEIGHT] = {0};
1898 u32 newblock[DX_MAX_TREE_HEIGHT] = {0};
1899 struct dynlock_handle *lock[DX_MAX_TREE_HEIGHT] = {NULL,};
1900 struct dynlock_handle *new_lock[DX_MAX_TREE_HEIGHT] = {NULL,};
1901 struct inode *dir = iam_path_obj(path);
1902 struct iam_descr *descr;
1906 descr = iam_path_descr(path);
1908 * Algorithm below depends on this.
1910 assert_corr(dx_root_limit(path) < dx_node_limit(path));
1912 frame = path->ip_frame;
1913 entries = frame->entries;
1916 * Tall-tree handling: we might have to split multiple index blocks
1917 * all the way up to tree root. Tricky point here is error handling:
1918 * to avoid complicated undo/rollback we
1920 * - first allocate all necessary blocks
1922 * - insert pointers into them atomically.
1926 * Locking: leaf is already locked. htree-locks are acquired on all
1927 * index nodes that require split bottom-to-top, on the "safe" node,
1928 * and on all new nodes
1931 dxtrace(printk("using %u of %u node entries\n",
1932 dx_get_count(entries), dx_get_limit(entries)));
1934 /* What levels need split? */
1935 for (nr_splet = 0; frame >= path->ip_frames &&
1936 dx_get_count(frame->entries) == dx_get_limit(frame->entries);
1937 --frame, ++nr_splet) {
1938 do_corr(schedule());
1939 if (nr_splet == DX_MAX_TREE_HEIGHT) {
1941 CWARN(dir->i_sb, __FUNCTION__,
1942 "Directory index full!\n");
1952 * Lock all nodes, bottom to top.
1954 for (frame = path->ip_frame, i = nr_splet; i >= 0; --i, --frame) {
1955 do_corr(schedule());
1956 lock[i] = iam_lock_htree(path->ip_container, frame->curidx,
1958 if (lock[i] == NULL) {
1965 * Check for concurrent index modification.
1967 err = iam_check_full_path(path, 1);
1971 * And check that the same number of nodes is to be split.
1973 for (i = 0, frame = path->ip_frame; frame >= path->ip_frames &&
1974 dx_get_count(frame->entries) == dx_get_limit(frame->entries);
1978 if (i != nr_splet) {
1983 /* Go back down, allocating blocks, locking them, and adding into
1985 for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
1986 bh_new[i] = iam_new_node(handle, path->ip_container,
1987 &newblock[i], &err);
1988 do_corr(schedule());
1990 descr->id_ops->id_node_init(path->ip_container,
1993 new_lock[i] = iam_lock_htree(path->ip_container, newblock[i],
1995 if (new_lock[i] == NULL) {
1999 do_corr(schedule());
2000 BUFFER_TRACE(frame->bh, "get_write_access");
2001 err = ldiskfs_journal_get_write_access(handle, frame->bh);
2005 /* Add "safe" node to transaction too */
2006 if (safe + 1 != path->ip_frames) {
2007 do_corr(schedule());
2008 err = ldiskfs_journal_get_write_access(handle, safe->bh);
2013 /* Go through nodes once more, inserting pointers */
2014 for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
2017 struct buffer_head *bh2;
2018 struct buffer_head *bh;
2020 entries = frame->entries;
2021 count = dx_get_count(entries);
2022 idx = iam_entry_diff(path, frame->at, entries);
2025 entries2 = dx_get_entries(path, bh2->b_data, 0);
2028 if (frame == path->ip_frames) {
2029 /* splitting root node. Tricky point:
2031 * In the "normal" B-tree we'd split root *and* add
2032 * new root to the tree with pointers to the old root
2033 * and its sibling (thus introducing two new nodes).
2035 * In htree it's enough to add one node, because
2036 * capacity of the root node is smaller than that of
2039 struct iam_frame *frames;
2040 struct iam_entry *next;
2042 assert_corr(i == 0);
2044 do_corr(schedule());
2046 frames = path->ip_frames;
2047 memcpy((char *) entries2, (char *) entries,
2048 count * iam_entry_size(path));
2049 dx_set_limit(entries2, dx_node_limit(path));
2052 iam_lock_bh(frame->bh);
2053 next = descr->id_ops->id_root_inc(path->ip_container,
2055 dx_set_block(path, next, newblock[0]);
2056 iam_unlock_bh(frame->bh);
2058 do_corr(schedule());
2059 /* Shift frames in the path */
2060 memmove(frames + 2, frames + 1,
2061 (sizeof path->ip_frames) - 2 * sizeof frames[0]);
2062 /* Add new access path frame */
2063 frames[1].at = iam_entry_shift(path, entries2, idx);
2064 frames[1].entries = entries = entries2;
2066 assert_inv(dx_node_check(path, frame));
2069 assert_inv(dx_node_check(path, frame));
2070 bh_new[0] = NULL; /* buffer head is "consumed" */
2071 err = ldiskfs_journal_get_write_access(handle, bh2);
2074 do_corr(schedule());
2076 /* splitting non-root index node. */
2077 struct iam_frame *parent = frame - 1;
2079 do_corr(schedule());
2080 count = iam_shift_entries(path, frame, count,
2081 entries, entries2, newblock[i]);
2082 /* Which index block gets the new entry? */
2084 int d = dx_index_is_compat(path) ? 0 : +1;
2086 frame->at = iam_entry_shift(path, entries2,
2088 frame->entries = entries = entries2;
2089 frame->curidx = newblock[i];
2090 swap(frame->bh, bh2);
2091 assert_corr(lock[i + 1] != NULL);
2092 assert_corr(new_lock[i] != NULL);
2093 swap(lock[i + 1], new_lock[i]);
2095 parent->at = iam_entry_shift(path,
2098 assert_inv(dx_node_check(path, frame));
2099 assert_inv(dx_node_check(path, parent));
2100 dxtrace(dx_show_index ("node", frame->entries));
2101 dxtrace(dx_show_index ("node",
2102 ((struct dx_node *) bh2->b_data)->entries));
2103 err = ldiskfs_journal_dirty_metadata(handle, bh2);
2106 do_corr(schedule());
2107 err = ldiskfs_journal_dirty_metadata(handle, parent->bh);
2111 do_corr(schedule());
2112 err = ldiskfs_journal_dirty_metadata(handle, bh);
2117 * This function was called to make insertion of new leaf
2118 * possible. Check that it fulfilled its obligations.
2120 assert_corr(dx_get_count(path->ip_frame->entries) <
2121 dx_get_limit(path->ip_frame->entries));
2122 assert_corr(lock[nr_splet] != NULL);
2123 *lh = lock[nr_splet];
2124 lock[nr_splet] = NULL;
2127 * Log ->i_size modification.
2129 err = ldiskfs_mark_inode_dirty(handle, dir);
2135 ldiskfs_std_error(dir->i_sb, err);
2138 iam_unlock_array(path->ip_container, lock);
2139 iam_unlock_array(path->ip_container, new_lock);
2141 assert_corr(err || iam_frame_is_locked(path, path->ip_frame));
2143 do_corr(schedule());
2144 for (i = 0; i < ARRAY_SIZE(bh_new); ++i) {
2145 if (bh_new[i] != NULL)
2151 static int iam_add_rec(handle_t *handle, struct iam_iterator *it,
2152 struct iam_path *path,
2153 const struct iam_key *k, const struct iam_rec *r)
2156 struct iam_leaf *leaf;
2158 leaf = &path->ip_leaf;
2159 assert_inv(iam_leaf_check(leaf));
2160 assert_inv(iam_path_check(path));
2161 err = iam_txn_add(handle, path, leaf->il_bh);
2163 do_corr(schedule());
2164 if (!iam_leaf_can_add(leaf, k, r)) {
2165 struct dynlock_handle *lh = NULL;
2168 assert_corr(lh == NULL);
2169 do_corr(schedule());
2170 err = split_index_node(handle, path, &lh);
2171 if (err == -EAGAIN) {
2172 assert_corr(lh == NULL);
2174 iam_path_fini(path);
2175 it->ii_state = IAM_IT_DETACHED;
2177 do_corr(schedule());
2178 err = iam_it_get_exact(it, k);
2180 err = +1; /* repeat split */
2185 assert_inv(iam_path_check(path));
2187 assert_corr(lh != NULL);
2188 do_corr(schedule());
2189 err = iam_new_leaf(handle, leaf);
2191 err = iam_txn_dirty(handle, path,
2192 path->ip_frame->bh);
2194 iam_unlock_htree(path->ip_container, lh);
2195 do_corr(schedule());
2198 iam_leaf_rec_add(leaf, k, r);
2199 err = iam_txn_dirty(handle, path, leaf->il_bh);
2202 assert_inv(iam_leaf_check(leaf));
2203 assert_inv(iam_leaf_check(&path->ip_leaf));
2204 assert_inv(iam_path_check(path));
2209 * Insert new record with key @k and contents from @r, shifting records to the
2210 * right. On success, iterator is positioned on the newly inserted record.
2212 * precondition: it->ii_flags&IAM_IT_WRITE &&
2213 * (it_state(it) == IAM_IT_ATTACHED ||
2214 * it_state(it) == IAM_IT_SKEWED) &&
2215 * ergo(it_state(it) == IAM_IT_ATTACHED,
2216 * it_keycmp(it, k) <= 0) &&
2217 * ergo(it_before(it), it_keycmp(it, k) > 0));
2218 * postcondition: ergo(result == 0,
2219 * it_state(it) == IAM_IT_ATTACHED &&
2220 * it_keycmp(it, k) == 0 &&
2221 * !memcmp(iam_it_rec_get(it), r, ...))
2223 int iam_it_rec_insert(handle_t *h, struct iam_iterator *it,
2224 const struct iam_key *k, const struct iam_rec *r)
2227 struct iam_path *path;
2229 path = &it->ii_path;
2231 assert_corr(it->ii_flags&IAM_IT_WRITE);
2232 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
2233 it_state(it) == IAM_IT_SKEWED);
2234 assert_corr(ergo(it_state(it) == IAM_IT_ATTACHED,
2235 it_keycmp(it, k) <= 0));
2236 assert_corr(ergo(it_before(it), it_keycmp(it, k) > 0));
2237 result = iam_add_rec(h, it, path, k, r);
2239 it->ii_state = IAM_IT_ATTACHED;
2240 assert_corr(ergo(result == 0,
2241 it_state(it) == IAM_IT_ATTACHED &&
2242 it_keycmp(it, k) == 0));
2245 EXPORT_SYMBOL(iam_it_rec_insert);
2247 static inline int iam_idle_blocks_limit(struct inode *inode)
2249 return (inode->i_sb->s_blocksize - sizeof(struct iam_idle_head)) >> 2;
2253 * If the leaf cannnot be recycled, we will lose one block for reusing.
2254 * It is not a serious issue because it almost the same of non-recycle.
2256 static iam_ptr_t iam_index_shrink(handle_t *h, struct iam_path *p,
2257 struct iam_leaf *l, struct buffer_head **bh)
2259 struct iam_container *c = p->ip_container;
2260 struct inode *inode = c->ic_object;
2261 struct iam_frame *frame = p->ip_frame;
2262 struct iam_entry *entries;
2263 struct dynlock_handle *lh;
2267 if (c->ic_idle_failed)
2270 if (unlikely(frame == NULL))
2273 if (!iam_leaf_empty(l))
2276 lh = iam_lock_htree(c, frame->curidx, DLT_WRITE);
2278 CWARN("%.16s: No memory to recycle idle blocks\n",
2279 LDISKFS_SB(inode->i_sb)->s_es->s_volume_name);
2283 rc = iam_txn_add(h, p, frame->bh);
2285 iam_unlock_htree(c, lh);
2289 iam_lock_bh(frame->bh);
2290 entries = frame->entries;
2291 count = dx_get_count(entries);
2292 if (frame->at < iam_entry_shift(p, entries, count - 1)) {
2293 struct iam_entry *n = iam_entry_shift(p, frame->at, 1);
2295 memmove(frame->at, n,
2296 (char *)iam_entry_shift(p, entries, count) - (char *)n);
2297 frame->at_shifted = 1;
2299 dx_set_count(entries, count - 1);
2300 rc = iam_txn_dirty(h, p, frame->bh);
2301 iam_unlock_bh(frame->bh);
2302 iam_unlock_htree(c, lh);
2312 iam_install_idle_blocks(handle_t *h, struct iam_path *p, struct buffer_head *bh,
2313 __u32 *idle_blocks, iam_ptr_t blk)
2315 struct iam_container *c = p->ip_container;
2316 struct buffer_head *old = c->ic_idle_bh;
2317 struct iam_idle_head *head;
2320 rc = iam_txn_add(h, p, bh);
2324 head = (struct iam_idle_head *)(bh->b_data);
2325 head->iih_magic = cpu_to_le16(IAM_IDLE_HEADER_MAGIC);
2326 head->iih_count = 0;
2327 head->iih_next = *idle_blocks;
2328 rc = iam_txn_dirty(h, p, bh);
2332 rc = iam_txn_add(h, p, c->ic_root_bh);
2336 iam_lock_bh(c->ic_root_bh);
2337 *idle_blocks = cpu_to_le32(blk);
2338 iam_unlock_bh(c->ic_root_bh);
2339 rc = iam_txn_dirty(h, p, c->ic_root_bh);
2341 /* NOT release old before new assigned. */
2346 iam_lock_bh(c->ic_root_bh);
2347 *idle_blocks = head->iih_next;
2348 iam_unlock_bh(c->ic_root_bh);
2354 * If the leaf cannnot be recycled, we will lose one block for reusing.
2355 * It is not a serious issue because it almost the same of non-recycle.
2357 static void iam_recycle_leaf(handle_t *h, struct iam_path *p,
2358 struct buffer_head *bh, iam_ptr_t blk)
2360 struct iam_container *c = p->ip_container;
2361 struct inode *inode = c->ic_object;
2362 struct iam_idle_head *head;
2367 cfs_down(&c->ic_idle_sem);
2368 if (unlikely(c->ic_idle_failed)) {
2373 idle_blocks = (__u32 *)(c->ic_root_bh->b_data +
2374 c->ic_descr->id_root_gap +
2375 sizeof(struct dx_countlimit));
2376 /* It is the first idle block. */
2377 if (c->ic_idle_bh == NULL) {
2378 rc = iam_install_idle_blocks(h, p, bh, idle_blocks, blk);
2382 head = (struct iam_idle_head *)(c->ic_idle_bh->b_data);
2383 count = le16_to_cpu(head->iih_count);
2384 /* Current ic_idle_bh is full, to be replaced by the leaf. */
2385 if (count == iam_idle_blocks_limit(inode)) {
2386 rc = iam_install_idle_blocks(h, p, bh, idle_blocks, blk);
2390 /* Just add to ic_idle_bh. */
2391 rc = iam_txn_add(h, p, c->ic_idle_bh);
2395 head->iih_blks[count] = cpu_to_le32(blk);
2396 head->iih_count = cpu_to_le16(count + 1);
2397 rc = iam_txn_dirty(h, p, c->ic_idle_bh);
2400 cfs_up(&c->ic_idle_sem);
2402 CWARN("%.16s: idle blocks failed, will lose the blk %u\n",
2403 LDISKFS_SB(inode->i_sb)->s_es->s_volume_name, blk);
2407 * Delete record under iterator.
2409 * precondition: it_state(it) == IAM_IT_ATTACHED &&
2410 * it->ii_flags&IAM_IT_WRITE &&
2412 * postcondition: it_state(it) == IAM_IT_ATTACHED ||
2413 * it_state(it) == IAM_IT_DETACHED
2415 int iam_it_rec_delete(handle_t *h, struct iam_iterator *it)
2418 struct iam_leaf *leaf;
2419 struct iam_path *path;
2421 assert_corr(it_state(it) == IAM_IT_ATTACHED &&
2422 it->ii_flags&IAM_IT_WRITE);
2423 assert_corr(it_at_rec(it));
2425 path = &it->ii_path;
2426 leaf = &path->ip_leaf;
2428 assert_inv(iam_leaf_check(leaf));
2429 assert_inv(iam_path_check(path));
2431 result = iam_txn_add(h, path, leaf->il_bh);
2433 * no compaction for now.
2436 iam_rec_del(leaf, it->ii_flags&IAM_IT_MOVE);
2437 result = iam_txn_dirty(h, path, leaf->il_bh);
2438 if (result == 0 && iam_leaf_at_end(leaf)) {
2439 struct buffer_head *bh = NULL;
2442 blk = iam_index_shrink(h, path, leaf, &bh);
2443 if (it->ii_flags & IAM_IT_MOVE) {
2444 result = iam_it_next(it);
2450 iam_recycle_leaf(h, path, bh, blk);
2455 assert_inv(iam_leaf_check(leaf));
2456 assert_inv(iam_path_check(path));
2457 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
2458 it_state(it) == IAM_IT_DETACHED);
2461 EXPORT_SYMBOL(iam_it_rec_delete);
2464 * Convert iterator to cookie.
2466 * precondition: it_state(it) == IAM_IT_ATTACHED &&
2467 * iam_path_descr(it->ii_path)->id_key_size <= sizeof(iam_pos_t)
2468 * postcondition: it_state(it) == IAM_IT_ATTACHED
2470 iam_pos_t iam_it_store(const struct iam_iterator *it)
2474 assert_corr(it_state(it) == IAM_IT_ATTACHED);
2475 assert_corr(it_at_rec(it));
2476 assert_corr(iam_it_container(it)->ic_descr->id_ikey_size <=
2480 return *(iam_pos_t *)iam_it_ikey_get(it, (void *)&result);
2482 EXPORT_SYMBOL(iam_it_store);
2485 * Restore iterator from cookie.
2487 * precondition: it_state(it) == IAM_IT_DETACHED && it->ii_flags&IAM_IT_MOVE &&
2488 * iam_path_descr(it->ii_path)->id_key_size <= sizeof(iam_pos_t)
2489 * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED &&
2490 * iam_it_store(it) == pos)
2492 int iam_it_load(struct iam_iterator *it, iam_pos_t pos)
2494 assert_corr(it_state(it) == IAM_IT_DETACHED &&
2495 it->ii_flags&IAM_IT_MOVE);
2496 assert_corr(iam_it_container(it)->ic_descr->id_ikey_size <= sizeof pos);
2497 return iam_it_iget(it, (struct iam_ikey *)&pos);
2499 EXPORT_SYMBOL(iam_it_load);
2501 /***********************************************************************/
2503 /***********************************************************************/
2505 static inline int ptr_inside(void *base, size_t size, void *ptr)
2507 return (base <= ptr) && (ptr < base + size);
2510 int iam_frame_invariant(struct iam_frame *f)
2514 f->bh->b_data != NULL &&
2515 ptr_inside(f->bh->b_data, f->bh->b_size, f->entries) &&
2516 ptr_inside(f->bh->b_data, f->bh->b_size, f->at) &&
2517 f->entries <= f->at);
2519 int iam_leaf_invariant(struct iam_leaf *l)
2523 l->il_bh->b_data != NULL &&
2524 ptr_inside(l->il_bh->b_data, l->il_bh->b_size, l->il_entries) &&
2525 ptr_inside(l->il_bh->b_data, l->il_bh->b_size, l->il_at) &&
2526 l->il_entries <= l->il_at;
2529 int iam_path_invariant(struct iam_path *p)
2533 if (p->ip_container == NULL ||
2534 p->ip_indirect < 0 || p->ip_indirect > DX_MAX_TREE_HEIGHT - 1 ||
2535 p->ip_frame != p->ip_frames + p->ip_indirect ||
2536 !iam_leaf_invariant(&p->ip_leaf))
2538 for (i = 0; i < ARRAY_SIZE(p->ip_frames); ++i) {
2539 if (i <= p->ip_indirect) {
2540 if (!iam_frame_invariant(&p->ip_frames[i]))
2547 int iam_it_invariant(struct iam_iterator *it)
2550 (it->ii_state == IAM_IT_DETACHED ||
2551 it->ii_state == IAM_IT_ATTACHED ||
2552 it->ii_state == IAM_IT_SKEWED) &&
2553 !(it->ii_flags & ~(IAM_IT_MOVE | IAM_IT_WRITE)) &&
2554 ergo(it->ii_state == IAM_IT_ATTACHED ||
2555 it->ii_state == IAM_IT_SKEWED,
2556 iam_path_invariant(&it->ii_path) &&
2557 equi(it_at_rec(it), it->ii_state == IAM_IT_SKEWED));
2561 * Search container @c for record with key @k. If record is found, its data
2562 * are moved into @r.
2564 * Return values: 0: found, -ENOENT: not-found, -ve: error
2566 int iam_lookup(struct iam_container *c, const struct iam_key *k,
2567 struct iam_rec *r, struct iam_path_descr *pd)
2569 struct iam_iterator it;
2572 iam_it_init(&it, c, 0, pd);
2574 result = iam_it_get_exact(&it, k);
2577 * record with required key found, copy it into user buffer
2579 iam_reccpy(&it.ii_path.ip_leaf, r);
2584 EXPORT_SYMBOL(iam_lookup);
2587 * Insert new record @r with key @k into container @c (within context of
2590 * Return values: 0: success, -ve: error, including -EEXIST when record with
2591 * given key is already present.
2593 * postcondition: ergo(result == 0 || result == -EEXIST,
2594 * iam_lookup(c, k, r2) > 0;
2596 int iam_insert(handle_t *h, struct iam_container *c, const struct iam_key *k,
2597 const struct iam_rec *r, struct iam_path_descr *pd)
2599 struct iam_iterator it;
2602 iam_it_init(&it, c, IAM_IT_WRITE, pd);
2604 result = iam_it_get_exact(&it, k);
2605 if (result == -ENOENT)
2606 result = iam_it_rec_insert(h, &it, k, r);
2607 else if (result == 0)
2613 EXPORT_SYMBOL(iam_insert);
2616 * Update record with the key @k in container @c (within context of
2617 * transaction @h), new record is given by @r.
2619 * Return values: +1: skip because of the same rec value, 0: success,
2620 * -ve: error, including -ENOENT if no record with the given key found.
2622 int iam_update(handle_t *h, struct iam_container *c, const struct iam_key *k,
2623 const struct iam_rec *r, struct iam_path_descr *pd)
2625 struct iam_iterator it;
2626 struct iam_leaf *folio;
2629 iam_it_init(&it, c, IAM_IT_WRITE, pd);
2631 result = iam_it_get_exact(&it, k);
2633 folio = &it.ii_path.ip_leaf;
2634 result = iam_leaf_ops(folio)->rec_eq(folio, r);
2636 iam_it_rec_set(h, &it, r);
2644 EXPORT_SYMBOL(iam_update);
2647 * Delete existing record with key @k.
2649 * Return values: 0: success, -ENOENT: not-found, -ve: other error.
2651 * postcondition: ergo(result == 0 || result == -ENOENT,
2652 * !iam_lookup(c, k, *));
2654 int iam_delete(handle_t *h, struct iam_container *c, const struct iam_key *k,
2655 struct iam_path_descr *pd)
2657 struct iam_iterator it;
2660 iam_it_init(&it, c, IAM_IT_WRITE, pd);
2662 result = iam_it_get_exact(&it, k);
2664 iam_it_rec_delete(h, &it);
2669 EXPORT_SYMBOL(iam_delete);
2671 int iam_root_limit(int rootgap, int blocksize, int size)
2676 limit = (blocksize - rootgap) / size;
2677 nlimit = blocksize / size;
2678 if (limit == nlimit)