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
18 * http://www.gnu.org/licenses/gpl-2.0.html
23 * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
24 * Use is subject to license terms.
26 * Copyright (c) 2011, 2017, Intel Corporation.
29 * This file is part of Lustre, http://www.lustre.org/
30 * Lustre is a trademark of Sun Microsystems, Inc.
33 * Top-level entry points into iam module
35 * Author: Wang Di <wangdi@clusterfs.com>
36 * Author: Nikita Danilov <nikita@clusterfs.com>
40 * iam: big theory statement.
42 * iam (Index Access Module) is a module providing abstraction of persistent
43 * transactional container on top of generalized ldiskfs htree.
47 * - key, pointer, and record size specifiable per container.
49 * - trees taller than 2 index levels.
51 * - read/write to existing ldiskfs htree directories as iam containers.
53 * iam container is a tree, consisting of leaf nodes containing keys and
54 * records stored in this container, and index nodes, containing keys and
55 * pointers to leaf or index nodes.
57 * iam does not work with keys directly, instead it calls user-supplied key
58 * comparison function (->dpo_keycmp()).
60 * Pointers are (currently) interpreted as logical offsets (measured in
61 * blocksful) within underlying flat file on top of which iam tree lives.
65 * iam mostly tries to reuse existing htree formats.
67 * Format of index node:
69 * +-----+-------+-------+-------+------+-------+------------+
70 * | | count | | | | | |
71 * | gap | / | entry | entry | .... | entry | free space |
72 * | | limit | | | | | |
73 * +-----+-------+-------+-------+------+-------+------------+
75 * gap this part of node is never accessed by iam code. It
76 * exists for binary compatibility with ldiskfs htree (that,
77 * in turn, stores fake struct ext2_dirent for ext2
78 * compatibility), and to keep some unspecified per-node
79 * data. Gap can be different for root and non-root index
80 * nodes. Gap size can be specified for each container
81 * (gap of 0 is allowed).
83 * count/limit current number of entries in this node, and the maximal
84 * number of entries that can fit into node. count/limit
85 * has the same size as entry, and is itself counted in
88 * entry index entry: consists of a key immediately followed by
89 * a pointer to a child node. Size of a key and size of a
90 * pointer depends on container. Entry has neither
91 * alignment nor padding.
93 * free space portion of node new entries are added to
95 * Entries in index node are sorted by their key value.
97 * Format of a leaf node is not specified. Generic iam code accesses leaf
98 * nodes through ->id_leaf methods in struct iam_descr.
100 * The IAM root block is a special node, which contains the IAM descriptor.
101 * It is on disk format:
103 * +---------+-------+--------+---------+-------+------+-------+------------+
104 * |IAM desc | count | idle | | | | | |
105 * |(fix/var)| / | blocks | padding | entry | .... | entry | free space |
106 * | | limit | | | | | | |
107 * +---------+-------+--------+---------+-------+------+-------+------------+
109 * The padding length is calculated with the parameters in the IAM descriptor.
111 * The field "idle_blocks" is used to record empty leaf nodes, which have not
112 * been released but all contained entries in them have been removed. Usually,
113 * the idle blocks in the IAM should be reused when need to allocate new leaf
114 * nodes for new entries, it depends on the IAM hash functions to map the new
115 * entries to these idle blocks. Unfortunately, it is not easy to design some
116 * hash functions for such clever mapping, especially considering the insert/
117 * lookup performance.
119 * So the IAM recycles the empty leaf nodes, and put them into a per-file based
120 * idle blocks pool. If need some new leaf node, it will try to take idle block
121 * from such pool with priority, in spite of how the IAM hash functions to map
124 * The idle blocks pool is organized as a series of tables, and each table
125 * can be described as following (on-disk format):
127 * +---------+---------+---------+---------+------+---------+-------+
128 * | magic | count | next | logic | | logic | free |
129 * |(16 bits)|(16 bits)| table | blk # | .... | blk # | space |
130 * | | |(32 bits)|(32 bits)| |(32 bits)| |
131 * +---------+---------+---------+---------+------+---------+-------+
133 * The logic blk# for the first table is stored in the root node "idle_blocks".
137 #include <linux/module.h>
138 #include <linux/fs.h>
139 #include <linux/pagemap.h>
140 #include <linux/time.h>
141 #include <linux/fcntl.h>
142 #include <linux/stat.h>
143 #include <linux/string.h>
144 #include <linux/quotaops.h>
145 #include <linux/buffer_head.h>
147 #include <ldiskfs/ldiskfs.h>
148 #include <ldiskfs/xattr.h>
151 #include "osd_internal.h"
153 #include <ldiskfs/acl.h>
156 * List of all registered formats.
158 * No locking. Callers synchronize.
160 static struct list_head iam_formats = LIST_HEAD_INIT(iam_formats);
162 void iam_format_register(struct iam_format *fmt)
164 list_add(&fmt->if_linkage, &iam_formats);
167 static struct buffer_head *
168 iam_load_idle_blocks(struct iam_container *c, iam_ptr_t blk)
170 struct inode *inode = c->ic_object;
171 struct iam_idle_head *head;
172 struct buffer_head *bh;
174 LASSERT(mutex_is_locked(&c->ic_idle_mutex));
179 bh = __ldiskfs_bread(NULL, inode, blk, 0);
180 if (IS_ERR_OR_NULL(bh)) {
181 CERROR("%s: cannot load idle blocks, blk = %u, err = %ld\n",
182 osd_ino2name(inode), blk, bh ? PTR_ERR(bh) : -EIO);
183 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("%s: invalid idle block head, blk = %u, magic = %d\n",
192 osd_ino2name(inode), blk, le16_to_cpu(head->iih_magic));
194 c->ic_idle_failed = 1;
195 return ERR_PTR(-EBADF);
202 * Determine format of given container. This is done by scanning list of
203 * registered formats and calling ->if_guess() method of each in turn.
205 static int iam_format_guess(struct iam_container *c)
208 struct iam_format *fmt;
211 * XXX temporary initialization hook.
214 static int initialized = 0;
217 iam_lvar_format_init();
218 iam_lfix_format_init();
224 list_for_each_entry(fmt, &iam_formats, if_linkage) {
225 result = fmt->if_guess(c);
231 struct buffer_head *bh;
234 LASSERT(c->ic_root_bh != NULL);
236 idle_blocks = (__u32 *)(c->ic_root_bh->b_data +
237 c->ic_descr->id_root_gap +
238 sizeof(struct dx_countlimit));
239 mutex_lock(&c->ic_idle_mutex);
240 bh = iam_load_idle_blocks(c, le32_to_cpu(*idle_blocks));
241 if (bh != NULL && IS_ERR(bh))
242 result = PTR_ERR(bh);
245 mutex_unlock(&c->ic_idle_mutex);
252 * Initialize container @c.
254 int iam_container_init(struct iam_container *c,
255 struct iam_descr *descr, struct inode *inode)
257 memset(c, 0, sizeof *c);
259 c->ic_object = inode;
260 init_rwsem(&c->ic_sem);
261 dynlock_init(&c->ic_tree_lock);
262 mutex_init(&c->ic_idle_mutex);
267 * Determine container format.
269 int iam_container_setup(struct iam_container *c)
271 return iam_format_guess(c);
275 * Finalize container @c, release all resources.
277 void iam_container_fini(struct iam_container *c)
279 brelse(c->ic_idle_bh);
280 c->ic_idle_bh = NULL;
281 brelse(c->ic_root_bh);
282 c->ic_root_bh = NULL;
285 void iam_path_init(struct iam_path *path, struct iam_container *c,
286 struct iam_path_descr *pd)
288 memset(path, 0, sizeof *path);
289 path->ip_container = c;
290 path->ip_frame = path->ip_frames;
292 path->ip_leaf.il_path = path;
295 static void iam_leaf_fini(struct iam_leaf *leaf);
297 void iam_path_release(struct iam_path *path)
301 for (i = 0; i < ARRAY_SIZE(path->ip_frames); i++) {
302 if (path->ip_frames[i].bh != NULL) {
303 path->ip_frames[i].at_shifted = 0;
304 brelse(path->ip_frames[i].bh);
305 path->ip_frames[i].bh = NULL;
310 void iam_path_fini(struct iam_path *path)
312 iam_leaf_fini(&path->ip_leaf);
313 iam_path_release(path);
317 void iam_path_compat_init(struct iam_path_compat *path, struct inode *inode)
321 path->ipc_hinfo = &path->ipc_hinfo_area;
322 for (i = 0; i < ARRAY_SIZE(path->ipc_scratch); ++i)
323 path->ipc_descr.ipd_key_scratch[i] =
324 (struct iam_ikey *)&path->ipc_scratch[i];
326 iam_path_init(&path->ipc_path, &path->ipc_container, &path->ipc_descr);
329 void iam_path_compat_fini(struct iam_path_compat *path)
331 iam_path_fini(&path->ipc_path);
335 * Helper function initializing iam_path_descr and its key scratch area.
337 struct iam_path_descr *iam_ipd_alloc(void *area, int keysize)
339 struct iam_path_descr *ipd;
345 for (i = 0; i < ARRAY_SIZE(ipd->ipd_key_scratch); ++i, karea += keysize)
346 ipd->ipd_key_scratch[i] = karea;
350 void iam_ipd_free(struct iam_path_descr *ipd)
354 int iam_node_read(struct iam_container *c, iam_ptr_t ptr,
355 handle_t *h, struct buffer_head **bh)
358 * NB: it can be called by iam_lfix_guess() which is still at
359 * very early stage, c->ic_root_bh and c->ic_descr->id_ops
360 * haven't been intialized yet.
361 * Also, we don't have this for IAM dir.
363 if (c->ic_root_bh != NULL &&
364 c->ic_descr->id_ops->id_root_ptr(c) == ptr) {
365 get_bh(c->ic_root_bh);
370 *bh = __ldiskfs_bread(h, c->ic_object, (int)ptr, 0);
381 * Return pointer to current leaf record. Pointer is valid while corresponding
382 * leaf node is locked and pinned.
384 static struct iam_rec *iam_leaf_rec(const struct iam_leaf *leaf)
386 return iam_leaf_ops(leaf)->rec(leaf);
390 * Return pointer to the current leaf key. This function returns pointer to
391 * the key stored in node.
393 * Caller should assume that returned pointer is only valid while leaf node is
396 static struct iam_key *iam_leaf_key(const struct iam_leaf *leaf)
398 return iam_leaf_ops(leaf)->key(leaf);
401 static int iam_leaf_key_size(const struct iam_leaf *leaf)
403 return iam_leaf_ops(leaf)->key_size(leaf);
406 static struct iam_ikey *iam_leaf_ikey(const struct iam_leaf *leaf,
407 struct iam_ikey *key)
409 return iam_leaf_ops(leaf)->ikey(leaf, key);
412 static int iam_leaf_keycmp(const struct iam_leaf *leaf,
413 const struct iam_key *key)
415 return iam_leaf_ops(leaf)->key_cmp(leaf, key);
418 static int iam_leaf_keyeq(const struct iam_leaf *leaf,
419 const struct iam_key *key)
421 return iam_leaf_ops(leaf)->key_eq(leaf, key);
424 #if LDISKFS_INVARIANT_ON
425 extern int dx_node_check(struct iam_path *p, struct iam_frame *f);
427 static int iam_path_check(struct iam_path *p)
432 struct iam_descr *param;
435 param = iam_path_descr(p);
436 for (i = 0; result && i < ARRAY_SIZE(p->ip_frames); ++i) {
437 f = &p->ip_frames[i];
439 result = dx_node_check(p, f);
441 result = !param->id_ops->id_node_check(p, f);
444 if (result && p->ip_leaf.il_bh != NULL)
447 ldiskfs_std_error(iam_path_obj(p)->i_sb, result);
453 static int iam_leaf_load(struct iam_path *path)
457 struct iam_container *c;
458 struct buffer_head *bh;
459 struct iam_leaf *leaf;
460 struct iam_descr *descr;
462 c = path->ip_container;
463 leaf = &path->ip_leaf;
464 descr = iam_path_descr(path);
465 block = path->ip_frame->leaf;
468 printk(KERN_EMERG "wrong leaf: %lu %d [%p %p %p]\n",
469 (long unsigned)path->ip_frame->leaf,
470 dx_get_count(dx_node_get_entries(path, path->ip_frame)),
471 path->ip_frames[0].bh, path->ip_frames[1].bh,
472 path->ip_frames[2].bh);
474 err = descr->id_ops->id_node_read(c, block, NULL, &bh);
477 leaf->il_curidx = block;
478 err = iam_leaf_ops(leaf)->init(leaf);
483 static void iam_unlock_htree(struct iam_container *ic,
484 struct dynlock_handle *lh)
487 dynlock_unlock(&ic->ic_tree_lock, lh);
491 static void iam_leaf_unlock(struct iam_leaf *leaf)
493 if (leaf->il_lock != NULL) {
494 iam_unlock_htree(iam_leaf_container(leaf),
497 leaf->il_lock = NULL;
501 static void iam_leaf_fini(struct iam_leaf *leaf)
503 if (leaf->il_path != NULL) {
504 iam_leaf_unlock(leaf);
505 iam_leaf_ops(leaf)->fini(leaf);
514 static void iam_leaf_start(struct iam_leaf *folio)
516 iam_leaf_ops(folio)->start(folio);
519 void iam_leaf_next(struct iam_leaf *folio)
521 iam_leaf_ops(folio)->next(folio);
524 static void iam_leaf_rec_add(struct iam_leaf *leaf, const struct iam_key *key,
525 const struct iam_rec *rec)
527 iam_leaf_ops(leaf)->rec_add(leaf, key, rec);
530 static void iam_rec_del(struct iam_leaf *leaf, int shift)
532 iam_leaf_ops(leaf)->rec_del(leaf, shift);
535 int iam_leaf_at_end(const struct iam_leaf *leaf)
537 return iam_leaf_ops(leaf)->at_end(leaf);
540 static void iam_leaf_split(struct iam_leaf *l, struct buffer_head **bh,
543 iam_leaf_ops(l)->split(l, bh, nr);
546 static inline int iam_leaf_empty(struct iam_leaf *l)
548 return iam_leaf_ops(l)->leaf_empty(l);
551 int iam_leaf_can_add(const struct iam_leaf *l,
552 const struct iam_key *k, const struct iam_rec *r)
554 return iam_leaf_ops(l)->can_add(l, k, r);
557 static int iam_txn_dirty(handle_t *handle,
558 struct iam_path *path, struct buffer_head *bh)
562 result = ldiskfs_handle_dirty_metadata(handle, NULL, bh);
564 ldiskfs_std_error(iam_path_obj(path)->i_sb, result);
568 static int iam_txn_add(handle_t *handle,
569 struct iam_path *path, struct buffer_head *bh)
573 result = ldiskfs_journal_get_write_access(handle, bh);
575 ldiskfs_std_error(iam_path_obj(path)->i_sb, result);
579 /***********************************************************************/
580 /* iterator interface */
581 /***********************************************************************/
583 static enum iam_it_state it_state(const struct iam_iterator *it)
589 * Helper function returning scratch key.
591 static struct iam_container *iam_it_container(const struct iam_iterator *it)
593 return it->ii_path.ip_container;
596 static inline int it_keycmp(const struct iam_iterator *it,
597 const struct iam_key *k)
599 return iam_leaf_keycmp(&it->ii_path.ip_leaf, k);
602 static inline int it_keyeq(const struct iam_iterator *it,
603 const struct iam_key *k)
605 return iam_leaf_keyeq(&it->ii_path.ip_leaf, k);
608 static int it_ikeycmp(const struct iam_iterator *it, const struct iam_ikey *ik)
610 return iam_ikeycmp(it->ii_path.ip_container,
611 iam_leaf_ikey(&it->ii_path.ip_leaf,
612 iam_path_ikey(&it->ii_path, 0)), ik);
615 static inline int it_at_rec(const struct iam_iterator *it)
617 return !iam_leaf_at_end(&it->ii_path.ip_leaf);
620 static inline int it_before(const struct iam_iterator *it)
622 return it_state(it) == IAM_IT_SKEWED && it_at_rec(it);
626 * Helper wrapper around iam_it_get(): returns 0 (success) only when record
627 * with exactly the same key as asked is found.
629 static int iam_it_get_exact(struct iam_iterator *it, const struct iam_key *k)
633 result = iam_it_get(it, k);
636 else if (result == 0)
638 * Return -ENOENT if cursor is located above record with a key
639 * different from one specified, or in the empty leaf.
641 * XXX returning -ENOENT only works if iam_it_get() never
642 * returns -ENOENT as a legitimate error.
648 void iam_container_write_lock(struct iam_container *ic)
650 down_write(&ic->ic_sem);
653 void iam_container_write_unlock(struct iam_container *ic)
655 up_write(&ic->ic_sem);
658 void iam_container_read_lock(struct iam_container *ic)
660 down_read(&ic->ic_sem);
663 void iam_container_read_unlock(struct iam_container *ic)
665 up_read(&ic->ic_sem);
669 * Initialize iterator to IAM_IT_DETACHED state.
671 * postcondition: it_state(it) == IAM_IT_DETACHED
673 int iam_it_init(struct iam_iterator *it, struct iam_container *c, __u32 flags,
674 struct iam_path_descr *pd)
676 memset(it, 0, sizeof *it);
677 it->ii_flags = flags;
678 it->ii_state = IAM_IT_DETACHED;
679 iam_path_init(&it->ii_path, c, pd);
684 * Finalize iterator and release all resources.
686 * precondition: it_state(it) == IAM_IT_DETACHED
688 void iam_it_fini(struct iam_iterator *it)
690 assert_corr(it_state(it) == IAM_IT_DETACHED);
691 iam_path_fini(&it->ii_path);
695 * this locking primitives are used to protect parts
696 * of dir's htree. protection unit is block: leaf or index
698 static struct dynlock_handle *iam_lock_htree(struct iam_container *ic,
700 enum dynlock_type lt)
702 return dynlock_lock(&ic->ic_tree_lock, value, lt, GFP_NOFS);
705 static int iam_index_lock(struct iam_path *path, struct dynlock_handle **lh)
709 for (f = path->ip_frame; f >= path->ip_frames; --f, ++lh) {
711 *lh = iam_lock_htree(path->ip_container, f->curidx, DLT_READ);
719 * Fast check for frame consistency.
721 static int iam_check_fast(struct iam_path *path, struct iam_frame *frame)
723 struct iam_container *bag;
724 struct iam_entry *next;
725 struct iam_entry *last;
726 struct iam_entry *entries;
727 struct iam_entry *at;
729 bag = path->ip_container;
731 entries = frame->entries;
732 last = iam_entry_shift(path, entries, dx_get_count(entries) - 1);
734 if (unlikely(at > last))
737 if (unlikely(dx_get_block(path, at) != frame->leaf))
740 if (unlikely(iam_ikeycmp(bag, iam_ikey_at(path, at),
741 path->ip_ikey_target) > 0))
744 next = iam_entry_shift(path, at, +1);
746 if (unlikely(iam_ikeycmp(bag, iam_ikey_at(path, next),
747 path->ip_ikey_target) <= 0))
753 int dx_index_is_compat(struct iam_path *path)
755 return iam_path_descr(path) == NULL;
761 * search position of specified hash in index
765 static struct iam_entry *iam_find_position(struct iam_path *path,
766 struct iam_frame *frame)
773 count = dx_get_count(frame->entries);
774 assert_corr(count && count <= dx_get_limit(frame->entries));
775 p = iam_entry_shift(path, frame->entries,
776 dx_index_is_compat(path) ? 1 : 2);
777 q = iam_entry_shift(path, frame->entries, count - 1);
779 m = iam_entry_shift(path, p, iam_entry_diff(path, q, p) / 2);
780 if (iam_ikeycmp(path->ip_container, iam_ikey_at(path, m),
781 path->ip_ikey_target) > 0)
782 q = iam_entry_shift(path, m, -1);
784 p = iam_entry_shift(path, m, +1);
786 return iam_entry_shift(path, p, -1);
791 static iam_ptr_t iam_find_ptr(struct iam_path *path, struct iam_frame *frame)
793 return dx_get_block(path, iam_find_position(path, frame));
796 void iam_insert_key(struct iam_path *path, struct iam_frame *frame,
797 const struct iam_ikey *key, iam_ptr_t ptr)
799 struct iam_entry *entries = frame->entries;
800 struct iam_entry *new = iam_entry_shift(path, frame->at, +1);
801 int count = dx_get_count(entries);
804 * Unfortunately we cannot assert this, as this function is sometimes
805 * called by VFS under i_sem and without pdirops lock.
807 assert_corr(1 || iam_frame_is_locked(path, frame));
808 assert_corr(count < dx_get_limit(entries));
809 assert_corr(frame->at < iam_entry_shift(path, entries, count));
810 assert_inv(dx_node_check(path, frame));
812 memmove(iam_entry_shift(path, new, 1), new,
813 (char *)iam_entry_shift(path, entries, count) - (char *)new);
814 dx_set_ikey(path, new, key);
815 dx_set_block(path, new, ptr);
816 dx_set_count(entries, count + 1);
817 assert_inv(dx_node_check(path, frame));
820 void iam_insert_key_lock(struct iam_path *path, struct iam_frame *frame,
821 const struct iam_ikey *key, iam_ptr_t ptr)
823 iam_lock_bh(frame->bh);
824 iam_insert_key(path, frame, key, ptr);
825 iam_unlock_bh(frame->bh);
828 * returns 0 if path was unchanged, -EAGAIN otherwise.
830 static int iam_check_path(struct iam_path *path, struct iam_frame *frame)
834 iam_lock_bh(frame->bh);
835 equal = iam_check_fast(path, frame) == 0 ||
836 frame->leaf == iam_find_ptr(path, frame);
837 DX_DEVAL(iam_lock_stats.dls_bh_again += !equal);
838 iam_unlock_bh(frame->bh);
840 return equal ? 0 : -EAGAIN;
843 static int iam_lookup_try(struct iam_path *path)
849 struct iam_descr *param;
850 struct iam_frame *frame;
851 struct iam_container *c;
853 param = iam_path_descr(path);
854 c = path->ip_container;
856 ptr = param->id_ops->id_root_ptr(c);
857 for (frame = path->ip_frames, i = 0; i <= path->ip_indirect;
859 err = param->id_ops->id_node_read(c, (iam_ptr_t)ptr, NULL,
863 iam_lock_bh(frame->bh);
865 * node must be initialized under bh lock because concurrent
866 * creation procedure may change it and iam_lookup_try() will
867 * see obsolete tree height. -bzzz
872 if (LDISKFS_INVARIANT_ON) {
873 err = param->id_ops->id_node_check(path, frame);
878 err = param->id_ops->id_node_load(path, frame);
882 assert_inv(dx_node_check(path, frame));
884 * splitting may change root index block and move hash we're
885 * looking for into another index block so, we have to check
886 * this situation and repeat from begining if path got changed
890 err = iam_check_path(path, frame - 1);
895 frame->at = iam_find_position(path, frame);
897 frame->leaf = ptr = dx_get_block(path, frame->at);
899 iam_unlock_bh(frame->bh);
903 iam_unlock_bh(frame->bh);
904 path->ip_frame = --frame;
908 static int __iam_path_lookup(struct iam_path *path)
913 for (i = 0; i < DX_MAX_TREE_HEIGHT; ++ i)
914 assert(path->ip_frames[i].bh == NULL);
917 err = iam_lookup_try(path);
921 } while (err == -EAGAIN);
927 * returns 0 if path was unchanged, -EAGAIN otherwise.
929 static int iam_check_full_path(struct iam_path *path, int search)
931 struct iam_frame *bottom;
932 struct iam_frame *scan;
938 for (bottom = path->ip_frames, i = 0;
939 i < DX_MAX_TREE_HEIGHT && bottom->bh != NULL; ++bottom, ++i) {
940 ; /* find last filled in frame */
944 * Lock frames, bottom to top.
946 for (scan = bottom - 1; scan >= path->ip_frames; --scan)
947 iam_lock_bh(scan->bh);
949 * Check them top to bottom.
952 for (scan = path->ip_frames; scan < bottom; ++scan) {
953 struct iam_entry *pos;
956 if (iam_check_fast(path, scan) == 0)
959 pos = iam_find_position(path, scan);
960 if (scan->leaf != dx_get_block(path, pos)) {
966 pos = iam_entry_shift(path, scan->entries,
967 dx_get_count(scan->entries) - 1);
968 if (scan->at > pos ||
969 scan->leaf != dx_get_block(path, scan->at)) {
977 * Unlock top to bottom.
979 for (scan = path->ip_frames; scan < bottom; ++scan)
980 iam_unlock_bh(scan->bh);
981 DX_DEVAL(iam_lock_stats.dls_bh_full_again += !!result);
989 * Performs path lookup and returns with found leaf (if any) locked by htree
992 static int iam_lookup_lock(struct iam_path *path,
993 struct dynlock_handle **dl, enum dynlock_type lt)
997 while ((result = __iam_path_lookup(path)) == 0) {
999 *dl = iam_lock_htree(path->ip_container, path->ip_frame->leaf,
1002 iam_path_fini(path);
1006 do_corr(schedule());
1008 * while locking leaf we just found may get split so we need
1009 * to check this -bzzz
1011 if (iam_check_full_path(path, 1) == 0)
1013 iam_unlock_htree(path->ip_container, *dl);
1015 iam_path_fini(path);
1020 * Performs tree top-to-bottom traversal starting from root, and loads leaf
1023 static int iam_path_lookup(struct iam_path *path, int index)
1025 struct iam_leaf *leaf;
1028 leaf = &path->ip_leaf;
1029 result = iam_lookup_lock(path, &leaf->il_lock, DLT_WRITE);
1030 assert_inv(iam_path_check(path));
1031 do_corr(schedule());
1033 result = iam_leaf_load(path);
1035 do_corr(schedule());
1037 result = iam_leaf_ops(leaf)->
1038 ilookup(leaf, path->ip_ikey_target);
1040 result = iam_leaf_ops(leaf)->
1041 lookup(leaf, path->ip_key_target);
1042 do_corr(schedule());
1045 iam_leaf_unlock(leaf);
1051 * Common part of iam_it_{i,}get().
1053 static int __iam_it_get(struct iam_iterator *it, int index)
1057 assert_corr(it_state(it) == IAM_IT_DETACHED);
1059 result = iam_path_lookup(&it->ii_path, index);
1063 collision = result & IAM_LOOKUP_LAST;
1064 switch (result & ~IAM_LOOKUP_LAST) {
1065 case IAM_LOOKUP_EXACT:
1067 it->ii_state = IAM_IT_ATTACHED;
1071 it->ii_state = IAM_IT_ATTACHED;
1073 case IAM_LOOKUP_BEFORE:
1074 case IAM_LOOKUP_EMPTY:
1076 it->ii_state = IAM_IT_SKEWED;
1081 result |= collision;
1084 * See iam_it_get_exact() for explanation.
1086 assert_corr(result != -ENOENT);
1091 * Correct hash, but not the same key was found, iterate through hash
1092 * collision chain, looking for correct record.
1094 static int iam_it_collision(struct iam_iterator *it)
1098 assert(ergo(it_at_rec(it), !it_keyeq(it, it->ii_path.ip_key_target)));
1100 while ((result = iam_it_next(it)) == 0) {
1101 do_corr(schedule());
1102 if (it_ikeycmp(it, it->ii_path.ip_ikey_target) != 0)
1104 if (it_keyeq(it, it->ii_path.ip_key_target))
1111 * Attach iterator. After successful completion, @it points to record with
1112 * least key not larger than @k.
1114 * Return value: 0: positioned on existing record,
1115 * +ve: exact position found,
1118 * precondition: it_state(it) == IAM_IT_DETACHED
1119 * postcondition: ergo(result == 0 && it_state(it) == IAM_IT_ATTACHED,
1120 * it_keycmp(it, k) <= 0)
1122 int iam_it_get(struct iam_iterator *it, const struct iam_key *k)
1126 assert_corr(it_state(it) == IAM_IT_DETACHED);
1128 it->ii_path.ip_ikey_target = NULL;
1129 it->ii_path.ip_key_target = k;
1131 result = __iam_it_get(it, 0);
1133 if (result == IAM_LOOKUP_LAST) {
1134 result = iam_it_collision(it);
1138 result = __iam_it_get(it, 0);
1143 result &= ~IAM_LOOKUP_LAST;
1145 assert_corr(ergo(result > 0, it_keycmp(it, k) == 0));
1146 assert_corr(ergo(result == 0 && it_state(it) == IAM_IT_ATTACHED,
1147 it_keycmp(it, k) <= 0));
1152 * Attach iterator by index key.
1154 static int iam_it_iget(struct iam_iterator *it, const struct iam_ikey *k)
1156 assert_corr(it_state(it) == IAM_IT_DETACHED);
1158 it->ii_path.ip_ikey_target = k;
1159 return __iam_it_get(it, 1) & ~IAM_LOOKUP_LAST;
1163 * Attach iterator, and assure it points to the record (not skewed).
1165 * Return value: 0: positioned on existing record,
1166 * +ve: exact position found,
1169 * precondition: it_state(it) == IAM_IT_DETACHED &&
1170 * !(it->ii_flags&IAM_IT_WRITE)
1171 * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED)
1173 int iam_it_get_at(struct iam_iterator *it, const struct iam_key *k)
1177 assert_corr(it_state(it) == IAM_IT_DETACHED &&
1178 !(it->ii_flags&IAM_IT_WRITE));
1179 result = iam_it_get(it, k);
1181 if (it_state(it) != IAM_IT_ATTACHED) {
1182 assert_corr(it_state(it) == IAM_IT_SKEWED);
1183 result = iam_it_next(it);
1186 assert_corr(ergo(result >= 0, it_state(it) == IAM_IT_ATTACHED));
1191 * Duplicates iterator.
1193 * postcondition: it_state(dst) == it_state(src) &&
1194 * iam_it_container(dst) == iam_it_container(src) &&
1195 * dst->ii_flags = src->ii_flags &&
1196 * ergo(it_state(src) == IAM_IT_ATTACHED,
1197 * iam_it_rec_get(dst) == iam_it_rec_get(src) &&
1198 * iam_it_key_get(dst) == iam_it_key_get(src))
1200 void iam_it_dup(struct iam_iterator *dst, const struct iam_iterator *src)
1202 dst->ii_flags = src->ii_flags;
1203 dst->ii_state = src->ii_state;
1204 /* XXX not yet. iam_path_dup(&dst->ii_path, &src->ii_path); */
1206 * XXX: duplicate lock.
1208 assert_corr(it_state(dst) == it_state(src));
1209 assert_corr(iam_it_container(dst) == iam_it_container(src));
1210 assert_corr(dst->ii_flags = src->ii_flags);
1211 assert_corr(ergo(it_state(src) == IAM_IT_ATTACHED,
1212 iam_it_rec_get(dst) == iam_it_rec_get(src) &&
1213 iam_it_key_get(dst) == iam_it_key_get(src)));
1217 * Detach iterator. Does nothing it detached state.
1219 * postcondition: it_state(it) == IAM_IT_DETACHED
1221 void iam_it_put(struct iam_iterator *it)
1223 if (it->ii_state != IAM_IT_DETACHED) {
1224 it->ii_state = IAM_IT_DETACHED;
1225 iam_leaf_fini(&it->ii_path.ip_leaf);
1229 static struct iam_ikey *iam_it_ikey_get(const struct iam_iterator *it,
1230 struct iam_ikey *ikey);
1234 * This function increments the frame pointer to search the next leaf
1235 * block, and reads in the necessary intervening nodes if the search
1236 * should be necessary. Whether or not the search is necessary is
1237 * controlled by the hash parameter. If the hash value is even, then
1238 * the search is only continued if the next block starts with that
1239 * hash value. This is used if we are searching for a specific file.
1241 * If the hash value is HASH_NB_ALWAYS, then always go to the next block.
1243 * This function returns 1 if the caller should continue to search,
1244 * or 0 if it should not. If there is an error reading one of the
1245 * index blocks, it will a negative error code.
1247 * If start_hash is non-null, it will be filled in with the starting
1248 * hash of the next page.
1250 static int iam_htree_advance(struct inode *dir, __u32 hash,
1251 struct iam_path *path, __u32 *start_hash,
1254 struct iam_frame *p;
1255 struct buffer_head *bh;
1256 int err, num_frames = 0;
1261 * Find the next leaf page by incrementing the frame pointer.
1262 * If we run out of entries in the interior node, loop around and
1263 * increment pointer in the parent node. When we break out of
1264 * this loop, num_frames indicates the number of interior
1265 * nodes need to be read.
1268 do_corr(schedule());
1273 p->at = iam_entry_shift(path, p->at, +1);
1274 if (p->at < iam_entry_shift(path, p->entries,
1275 dx_get_count(p->entries))) {
1276 p->leaf = dx_get_block(path, p->at);
1277 iam_unlock_bh(p->bh);
1280 iam_unlock_bh(p->bh);
1281 if (p == path->ip_frames)
1293 * If the hash is 1, then continue only if the next page has a
1294 * continuation hash of any value. This is used for readdir
1295 * handling. Otherwise, check to see if the hash matches the
1296 * desired contiuation hash. If it doesn't, return since
1297 * there's no point to read in the successive index pages.
1299 dx_get_ikey(path, p->at, (struct iam_ikey *)&bhash);
1301 *start_hash = bhash;
1302 if ((hash & 1) == 0) {
1303 if ((bhash & ~1) != hash)
1308 * If the hash is HASH_NB_ALWAYS, we always go to the next
1309 * block so no check is necessary
1311 while (num_frames--) {
1314 do_corr(schedule());
1316 idx = p->leaf = dx_get_block(path, p->at);
1317 iam_unlock_bh(p->bh);
1318 err = iam_path_descr(path)->id_ops->
1319 id_node_read(path->ip_container, idx, NULL, &bh);
1321 return err; /* Failure */
1324 assert_corr(p->bh != bh);
1326 p->entries = dx_node_get_entries(path, p);
1327 p->at = iam_entry_shift(path, p->entries, !compat);
1328 assert_corr(p->curidx != idx);
1331 assert_corr(p->leaf != dx_get_block(path, p->at));
1332 p->leaf = dx_get_block(path, p->at);
1333 iam_unlock_bh(p->bh);
1334 assert_inv(dx_node_check(path, p));
1339 static inline int iam_index_advance(struct iam_path *path)
1341 return iam_htree_advance(iam_path_obj(path), 0, path, NULL, 0);
1344 static void iam_unlock_array(struct iam_container *ic,
1345 struct dynlock_handle **lh)
1349 for (i = 0; i < DX_MAX_TREE_HEIGHT; ++i, ++lh) {
1351 iam_unlock_htree(ic, *lh);
1357 * Advance index part of @path to point to the next leaf. Returns 1 on
1358 * success, 0, when end of container was reached. Leaf node is locked.
1360 int iam_index_next(struct iam_container *c, struct iam_path *path)
1363 struct dynlock_handle *lh[DX_MAX_TREE_HEIGHT] = { NULL, };
1367 * Locking for iam_index_next()... is to be described.
1370 cursor = path->ip_frame->leaf;
1373 result = iam_index_lock(path, lh);
1374 do_corr(schedule());
1378 result = iam_check_full_path(path, 0);
1379 if (result == 0 && cursor == path->ip_frame->leaf) {
1380 result = iam_index_advance(path);
1382 assert_corr(result == 0 ||
1383 cursor != path->ip_frame->leaf);
1387 iam_unlock_array(c, lh);
1389 iam_path_release(path);
1390 do_corr(schedule());
1392 result = __iam_path_lookup(path);
1396 while (path->ip_frame->leaf != cursor) {
1397 do_corr(schedule());
1399 result = iam_index_lock(path, lh);
1400 do_corr(schedule());
1404 result = iam_check_full_path(path, 0);
1408 result = iam_index_advance(path);
1410 CERROR("cannot find cursor : %u\n",
1416 result = iam_check_full_path(path, 0);
1419 iam_unlock_array(c, lh);
1421 } while (result == -EAGAIN);
1425 iam_unlock_array(c, lh);
1430 * Move iterator one record right.
1432 * Return value: 0: success,
1433 * +1: end of container reached
1436 * precondition: (it_state(it) == IAM_IT_ATTACHED ||
1437 * it_state(it) == IAM_IT_SKEWED) && it->ii_flags&IAM_IT_MOVE
1438 * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED) &&
1439 * ergo(result > 0, it_state(it) == IAM_IT_DETACHED)
1441 int iam_it_next(struct iam_iterator *it)
1444 struct iam_path *path;
1445 struct iam_leaf *leaf;
1447 do_corr(struct iam_ikey *ik_orig);
1449 /* assert_corr(it->ii_flags&IAM_IT_MOVE); */
1450 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1451 it_state(it) == IAM_IT_SKEWED);
1453 path = &it->ii_path;
1454 leaf = &path->ip_leaf;
1456 assert_corr(iam_leaf_is_locked(leaf));
1459 do_corr(ik_orig = it_at_rec(it) ?
1460 iam_it_ikey_get(it, iam_path_ikey(path, 2)) : NULL);
1461 if (it_before(it)) {
1462 assert_corr(!iam_leaf_at_end(leaf));
1463 it->ii_state = IAM_IT_ATTACHED;
1465 if (!iam_leaf_at_end(leaf))
1466 /* advance within leaf node */
1467 iam_leaf_next(leaf);
1469 * multiple iterations may be necessary due to empty leaves.
1471 while (result == 0 && iam_leaf_at_end(leaf)) {
1472 do_corr(schedule());
1473 /* advance index portion of the path */
1474 result = iam_index_next(iam_it_container(it), path);
1475 assert_corr(iam_leaf_is_locked(leaf));
1477 struct dynlock_handle *lh;
1478 lh = iam_lock_htree(iam_it_container(it),
1479 path->ip_frame->leaf,
1482 iam_leaf_fini(leaf);
1484 result = iam_leaf_load(path);
1486 iam_leaf_start(leaf);
1489 } else if (result == 0)
1490 /* end of container reached */
1496 it->ii_state = IAM_IT_ATTACHED;
1498 assert_corr(ergo(result == 0, it_state(it) == IAM_IT_ATTACHED));
1499 assert_corr(ergo(result > 0, it_state(it) == IAM_IT_DETACHED));
1500 assert_corr(ergo(result == 0 && ik_orig != NULL,
1501 it_ikeycmp(it, ik_orig) >= 0));
1506 * Return pointer to the record under iterator.
1508 * precondition: it_state(it) == IAM_IT_ATTACHED && it_at_rec(it)
1509 * postcondition: it_state(it) == IAM_IT_ATTACHED
1511 struct iam_rec *iam_it_rec_get(const struct iam_iterator *it)
1513 assert_corr(it_state(it) == IAM_IT_ATTACHED);
1514 assert_corr(it_at_rec(it));
1515 return iam_leaf_rec(&it->ii_path.ip_leaf);
1518 static void iam_it_reccpy(struct iam_iterator *it, const struct iam_rec *r)
1520 struct iam_leaf *folio;
1522 folio = &it->ii_path.ip_leaf;
1523 iam_leaf_ops(folio)->rec_set(folio, r);
1527 * Replace contents of record under iterator.
1529 * precondition: it_state(it) == IAM_IT_ATTACHED &&
1530 * it->ii_flags&IAM_IT_WRITE
1531 * postcondition: it_state(it) == IAM_IT_ATTACHED &&
1532 * ergo(result == 0, !memcmp(iam_it_rec_get(it), r, ...))
1534 int iam_it_rec_set(handle_t *h,
1535 struct iam_iterator *it, const struct iam_rec *r)
1538 struct iam_path *path;
1539 struct buffer_head *bh;
1541 assert_corr(it_state(it) == IAM_IT_ATTACHED &&
1542 it->ii_flags&IAM_IT_WRITE);
1543 assert_corr(it_at_rec(it));
1545 path = &it->ii_path;
1546 bh = path->ip_leaf.il_bh;
1547 result = iam_txn_add(h, path, bh);
1549 iam_it_reccpy(it, r);
1550 result = iam_txn_dirty(h, path, bh);
1556 * Return pointer to the index key under iterator.
1558 * precondition: it_state(it) == IAM_IT_ATTACHED ||
1559 * it_state(it) == IAM_IT_SKEWED
1561 static struct iam_ikey *iam_it_ikey_get(const struct iam_iterator *it,
1562 struct iam_ikey *ikey)
1564 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1565 it_state(it) == IAM_IT_SKEWED);
1566 assert_corr(it_at_rec(it));
1567 return iam_leaf_ikey(&it->ii_path.ip_leaf, ikey);
1571 * Return pointer to the key under iterator.
1573 * precondition: it_state(it) == IAM_IT_ATTACHED ||
1574 * it_state(it) == IAM_IT_SKEWED
1576 struct iam_key *iam_it_key_get(const struct iam_iterator *it)
1578 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1579 it_state(it) == IAM_IT_SKEWED);
1580 assert_corr(it_at_rec(it));
1581 return iam_leaf_key(&it->ii_path.ip_leaf);
1585 * Return size of key under iterator (in bytes)
1587 * precondition: it_state(it) == IAM_IT_ATTACHED ||
1588 * it_state(it) == IAM_IT_SKEWED
1590 int iam_it_key_size(const struct iam_iterator *it)
1592 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
1593 it_state(it) == IAM_IT_SKEWED);
1594 assert_corr(it_at_rec(it));
1595 return iam_leaf_key_size(&it->ii_path.ip_leaf);
1598 static struct buffer_head *
1599 iam_new_node(handle_t *h, struct iam_container *c, iam_ptr_t *b, int *e)
1601 struct inode *inode = c->ic_object;
1602 struct buffer_head *bh = NULL;
1603 struct iam_idle_head *head;
1604 struct buffer_head *idle;
1608 if (c->ic_idle_bh == NULL)
1611 mutex_lock(&c->ic_idle_mutex);
1612 if (unlikely(c->ic_idle_bh == NULL)) {
1613 mutex_unlock(&c->ic_idle_mutex);
1617 head = (struct iam_idle_head *)(c->ic_idle_bh->b_data);
1618 count = le16_to_cpu(head->iih_count);
1620 *e = ldiskfs_journal_get_write_access(h, c->ic_idle_bh);
1625 *b = le32_to_cpu(head->iih_blks[count]);
1626 head->iih_count = cpu_to_le16(count);
1627 *e = ldiskfs_handle_dirty_metadata(h, inode, c->ic_idle_bh);
1631 mutex_unlock(&c->ic_idle_mutex);
1632 bh = __ldiskfs_bread(NULL, inode, *b, 0);
1633 if (IS_ERR_OR_NULL(bh)) {
1643 /* The block itself which contains the iam_idle_head is
1644 * also an idle block, and can be used as the new node. */
1645 idle_blocks = (__u32 *)(c->ic_root_bh->b_data +
1646 c->ic_descr->id_root_gap +
1647 sizeof(struct dx_countlimit));
1648 *e = ldiskfs_journal_get_write_access(h, c->ic_root_bh);
1652 *b = le32_to_cpu(*idle_blocks);
1653 iam_lock_bh(c->ic_root_bh);
1654 *idle_blocks = head->iih_next;
1655 iam_unlock_bh(c->ic_root_bh);
1656 *e = ldiskfs_handle_dirty_metadata(h, inode, c->ic_root_bh);
1658 iam_lock_bh(c->ic_root_bh);
1659 *idle_blocks = cpu_to_le32(*b);
1660 iam_unlock_bh(c->ic_root_bh);
1665 idle = iam_load_idle_blocks(c, le32_to_cpu(*idle_blocks));
1666 if (idle != NULL && IS_ERR(idle)) {
1668 c->ic_idle_bh = NULL;
1673 c->ic_idle_bh = idle;
1674 mutex_unlock(&c->ic_idle_mutex);
1677 /* get write access for the found buffer head */
1678 *e = ldiskfs_journal_get_write_access(h, bh);
1682 ldiskfs_std_error(inode->i_sb, *e);
1684 /* Clear the reused node as new node does. */
1685 memset(bh->b_data, 0, inode->i_sb->s_blocksize);
1686 set_buffer_uptodate(bh);
1691 bh = osd_ldiskfs_append(h, inode, b);
1700 mutex_unlock(&c->ic_idle_mutex);
1701 ldiskfs_std_error(inode->i_sb, *e);
1706 * Insertion of new record. Interaction with jbd during non-trivial case (when
1707 * split happens) is as following:
1709 * - new leaf node is involved into transaction by iam_new_node();
1711 * - old leaf node is involved into transaction by iam_add_rec();
1713 * - leaf where insertion point ends in, is marked dirty by iam_add_rec();
1715 * - leaf without insertion point is marked dirty (as @new_leaf) by
1718 * - split index nodes are involved into transaction and marked dirty by
1719 * split_index_node().
1721 * - "safe" index node, which is no split, but where new pointer is inserted
1722 * is involved into transaction and marked dirty by split_index_node().
1724 * - index node where pointer to new leaf is inserted is involved into
1725 * transaction by split_index_node() and marked dirty by iam_add_rec().
1727 * - inode is marked dirty by iam_add_rec().
1731 static int iam_new_leaf(handle_t *handle, struct iam_leaf *leaf)
1735 struct buffer_head *new_leaf;
1736 struct buffer_head *old_leaf;
1737 struct iam_container *c;
1739 struct iam_path *path;
1741 c = iam_leaf_container(leaf);
1742 path = leaf->il_path;
1745 new_leaf = iam_new_node(handle, c, &blknr, &err);
1746 do_corr(schedule());
1747 if (new_leaf != NULL) {
1748 struct dynlock_handle *lh;
1750 lh = iam_lock_htree(c, blknr, DLT_WRITE);
1751 do_corr(schedule());
1753 iam_leaf_ops(leaf)->init_new(c, new_leaf);
1754 do_corr(schedule());
1755 old_leaf = leaf->il_bh;
1756 iam_leaf_split(leaf, &new_leaf, blknr);
1757 if (old_leaf != leaf->il_bh) {
1759 * Switched to the new leaf.
1761 iam_leaf_unlock(leaf);
1763 path->ip_frame->leaf = blknr;
1765 iam_unlock_htree(path->ip_container, lh);
1766 do_corr(schedule());
1767 err = iam_txn_dirty(handle, path, new_leaf);
1769 err = ldiskfs_mark_inode_dirty(handle, obj);
1770 do_corr(schedule());
1775 assert_inv(iam_path_check(iam_leaf_path(leaf)));
1779 static inline void dx_set_limit(struct iam_entry *entries, unsigned value)
1781 ((struct dx_countlimit *) entries)->limit = cpu_to_le16(value);
1784 static int iam_shift_entries(struct iam_path *path,
1785 struct iam_frame *frame, unsigned count,
1786 struct iam_entry *entries, struct iam_entry *entries2,
1793 struct iam_frame *parent = frame - 1;
1794 struct iam_ikey *pivot = iam_path_ikey(path, 3);
1796 delta = dx_index_is_compat(path) ? 0 : +1;
1798 count1 = count/2 + delta;
1799 count2 = count - count1;
1800 dx_get_ikey(path, iam_entry_shift(path, entries, count1), pivot);
1802 dxtrace(printk("Split index %d/%d\n", count1, count2));
1804 memcpy((char *) iam_entry_shift(path, entries2, delta),
1805 (char *) iam_entry_shift(path, entries, count1),
1806 count2 * iam_entry_size(path));
1808 dx_set_count(entries2, count2 + delta);
1809 dx_set_limit(entries2, dx_node_limit(path));
1812 * NOTE: very subtle piece of code competing dx_probe() may find 2nd
1813 * level index in root index, then we insert new index here and set
1814 * new count in that 2nd level index. so, dx_probe() may see 2nd level
1815 * index w/o hash it looks for. the solution is to check root index
1816 * after we locked just founded 2nd level index -bzzz
1818 iam_insert_key_lock(path, parent, pivot, newblock);
1821 * now old and new 2nd level index blocks contain all pointers, so
1822 * dx_probe() may find it in the both. it's OK -bzzz
1824 iam_lock_bh(frame->bh);
1825 dx_set_count(entries, count1);
1826 iam_unlock_bh(frame->bh);
1829 * now old 2nd level index block points to first half of leafs. it's
1830 * importand that dx_probe() must check root index block for changes
1831 * under dx_lock_bh(frame->bh) -bzzz
1838 int split_index_node(handle_t *handle, struct iam_path *path,
1839 struct dynlock_handle **lh)
1841 struct iam_entry *entries; /* old block contents */
1842 struct iam_entry *entries2; /* new block contents */
1843 struct iam_frame *frame, *safe;
1844 struct buffer_head *bh_new[DX_MAX_TREE_HEIGHT] = {NULL};
1845 u32 newblock[DX_MAX_TREE_HEIGHT] = {0};
1846 struct dynlock_handle *lock[DX_MAX_TREE_HEIGHT] = {NULL,};
1847 struct dynlock_handle *new_lock[DX_MAX_TREE_HEIGHT] = {NULL,};
1848 struct inode *dir = iam_path_obj(path);
1849 struct iam_descr *descr;
1853 descr = iam_path_descr(path);
1855 * Algorithm below depends on this.
1857 assert_corr(dx_root_limit(path) < dx_node_limit(path));
1859 frame = path->ip_frame;
1860 entries = frame->entries;
1863 * Tall-tree handling: we might have to split multiple index blocks
1864 * all the way up to tree root. Tricky point here is error handling:
1865 * to avoid complicated undo/rollback we
1867 * - first allocate all necessary blocks
1869 * - insert pointers into them atomically.
1873 * Locking: leaf is already locked. htree-locks are acquired on all
1874 * index nodes that require split bottom-to-top, on the "safe" node,
1875 * and on all new nodes
1878 dxtrace(printk("using %u of %u node entries\n",
1879 dx_get_count(entries), dx_get_limit(entries)));
1881 /* What levels need split? */
1882 for (nr_splet = 0; frame >= path->ip_frames &&
1883 dx_get_count(frame->entries) == dx_get_limit(frame->entries);
1884 --frame, ++nr_splet) {
1885 do_corr(schedule());
1886 if (nr_splet == DX_MAX_TREE_HEIGHT) {
1888 * CWARN(dir->i_sb, __FUNCTION__,
1889 * "Directory index full!\n");
1899 * Lock all nodes, bottom to top.
1901 for (frame = path->ip_frame, i = nr_splet; i >= 0; --i, --frame) {
1902 do_corr(schedule());
1903 lock[i] = iam_lock_htree(path->ip_container, frame->curidx,
1905 if (lock[i] == NULL) {
1912 * Check for concurrent index modification.
1914 err = iam_check_full_path(path, 1);
1918 * And check that the same number of nodes is to be split.
1920 for (i = 0, frame = path->ip_frame; frame >= path->ip_frames &&
1921 dx_get_count(frame->entries) == dx_get_limit(frame->entries);
1925 if (i != nr_splet) {
1931 * Go back down, allocating blocks, locking them, and adding into
1934 for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
1935 bh_new[i] = iam_new_node(handle, path->ip_container,
1936 &newblock[i], &err);
1937 do_corr(schedule());
1939 descr->id_ops->id_node_init(path->ip_container,
1943 new_lock[i] = iam_lock_htree(path->ip_container, newblock[i],
1945 if (new_lock[i] == NULL) {
1949 do_corr(schedule());
1950 BUFFER_TRACE(frame->bh, "get_write_access");
1951 err = ldiskfs_journal_get_write_access(handle, frame->bh);
1955 /* Add "safe" node to transaction too */
1956 if (safe + 1 != path->ip_frames) {
1957 do_corr(schedule());
1958 err = ldiskfs_journal_get_write_access(handle, safe->bh);
1963 /* Go through nodes once more, inserting pointers */
1964 for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
1967 struct buffer_head *bh2;
1968 struct buffer_head *bh;
1970 entries = frame->entries;
1971 count = dx_get_count(entries);
1972 idx = iam_entry_diff(path, frame->at, entries);
1975 entries2 = dx_get_entries(path, bh2->b_data, 0);
1978 if (frame == path->ip_frames) {
1979 /* splitting root node. Tricky point:
1981 * In the "normal" B-tree we'd split root *and* add
1982 * new root to the tree with pointers to the old root
1983 * and its sibling (thus introducing two new nodes).
1985 * In htree it's enough to add one node, because
1986 * capacity of the root node is smaller than that of
1989 struct iam_frame *frames;
1990 struct iam_entry *next;
1992 assert_corr(i == 0);
1994 do_corr(schedule());
1996 frames = path->ip_frames;
1997 memcpy((char *) entries2, (char *) entries,
1998 count * iam_entry_size(path));
1999 dx_set_limit(entries2, dx_node_limit(path));
2002 iam_lock_bh(frame->bh);
2003 next = descr->id_ops->id_root_inc(path->ip_container,
2005 dx_set_block(path, next, newblock[0]);
2006 iam_unlock_bh(frame->bh);
2008 do_corr(schedule());
2009 /* Shift frames in the path */
2010 memmove(frames + 2, frames + 1,
2011 (sizeof path->ip_frames) - 2 * sizeof frames[0]);
2012 /* Add new access path frame */
2013 frames[1].at = iam_entry_shift(path, entries2, idx);
2014 frames[1].entries = entries = entries2;
2016 assert_inv(dx_node_check(path, frame));
2019 assert_inv(dx_node_check(path, frame));
2020 bh_new[0] = NULL; /* buffer head is "consumed" */
2021 err = ldiskfs_handle_dirty_metadata(handle, NULL, bh2);
2024 do_corr(schedule());
2026 /* splitting non-root index node. */
2027 struct iam_frame *parent = frame - 1;
2029 do_corr(schedule());
2030 count = iam_shift_entries(path, frame, count,
2031 entries, entries2, newblock[i]);
2032 /* Which index block gets the new entry? */
2034 int d = dx_index_is_compat(path) ? 0 : +1;
2036 frame->at = iam_entry_shift(path, entries2,
2038 frame->entries = entries = entries2;
2039 frame->curidx = newblock[i];
2040 swap(frame->bh, bh2);
2041 assert_corr(lock[i + 1] != NULL);
2042 assert_corr(new_lock[i] != NULL);
2043 swap(lock[i + 1], new_lock[i]);
2045 parent->at = iam_entry_shift(path,
2048 assert_inv(dx_node_check(path, frame));
2049 assert_inv(dx_node_check(path, parent));
2050 dxtrace(dx_show_index("node", frame->entries));
2051 dxtrace(dx_show_index("node",
2052 ((struct dx_node *) bh2->b_data)->entries));
2053 err = ldiskfs_handle_dirty_metadata(handle, NULL, bh2);
2056 do_corr(schedule());
2057 err = ldiskfs_handle_dirty_metadata(handle, NULL,
2062 do_corr(schedule());
2063 err = ldiskfs_handle_dirty_metadata(handle, NULL, bh);
2068 * This function was called to make insertion of new leaf
2069 * possible. Check that it fulfilled its obligations.
2071 assert_corr(dx_get_count(path->ip_frame->entries) <
2072 dx_get_limit(path->ip_frame->entries));
2073 assert_corr(lock[nr_splet] != NULL);
2074 *lh = lock[nr_splet];
2075 lock[nr_splet] = NULL;
2078 * Log ->i_size modification.
2080 err = ldiskfs_mark_inode_dirty(handle, dir);
2086 ldiskfs_std_error(dir->i_sb, err);
2089 iam_unlock_array(path->ip_container, lock);
2090 iam_unlock_array(path->ip_container, new_lock);
2092 assert_corr(err || iam_frame_is_locked(path, path->ip_frame));
2094 do_corr(schedule());
2095 for (i = 0; i < ARRAY_SIZE(bh_new); ++i) {
2096 if (bh_new[i] != NULL)
2102 static int iam_add_rec(handle_t *handle, struct iam_iterator *it,
2103 struct iam_path *path,
2104 const struct iam_key *k, const struct iam_rec *r)
2107 struct iam_leaf *leaf;
2109 leaf = &path->ip_leaf;
2110 assert_inv(iam_path_check(path));
2111 err = iam_txn_add(handle, path, leaf->il_bh);
2113 do_corr(schedule());
2114 if (!iam_leaf_can_add(leaf, k, r)) {
2115 struct dynlock_handle *lh = NULL;
2118 assert_corr(lh == NULL);
2119 do_corr(schedule());
2120 err = split_index_node(handle, path, &lh);
2121 if (err == -EAGAIN) {
2122 assert_corr(lh == NULL);
2124 iam_path_fini(path);
2125 it->ii_state = IAM_IT_DETACHED;
2127 do_corr(schedule());
2128 err = iam_it_get_exact(it, k);
2130 err = +1; /* repeat split */
2135 assert_inv(iam_path_check(path));
2137 assert_corr(lh != NULL);
2138 do_corr(schedule());
2139 err = iam_new_leaf(handle, leaf);
2141 err = iam_txn_dirty(handle, path,
2142 path->ip_frame->bh);
2144 iam_unlock_htree(path->ip_container, lh);
2145 do_corr(schedule());
2148 iam_leaf_rec_add(leaf, k, r);
2149 err = iam_txn_dirty(handle, path, leaf->il_bh);
2152 assert_inv(iam_path_check(path));
2157 * Insert new record with key @k and contents from @r, shifting records to the
2158 * right. On success, iterator is positioned on the newly inserted record.
2160 * precondition: it->ii_flags&IAM_IT_WRITE &&
2161 * (it_state(it) == IAM_IT_ATTACHED ||
2162 * it_state(it) == IAM_IT_SKEWED) &&
2163 * ergo(it_state(it) == IAM_IT_ATTACHED,
2164 * it_keycmp(it, k) <= 0) &&
2165 * ergo(it_before(it), it_keycmp(it, k) > 0));
2166 * postcondition: ergo(result == 0,
2167 * it_state(it) == IAM_IT_ATTACHED &&
2168 * it_keycmp(it, k) == 0 &&
2169 * !memcmp(iam_it_rec_get(it), r, ...))
2171 int iam_it_rec_insert(handle_t *h, struct iam_iterator *it,
2172 const struct iam_key *k, const struct iam_rec *r)
2175 struct iam_path *path;
2177 path = &it->ii_path;
2179 assert_corr(it->ii_flags&IAM_IT_WRITE);
2180 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
2181 it_state(it) == IAM_IT_SKEWED);
2182 assert_corr(ergo(it_state(it) == IAM_IT_ATTACHED,
2183 it_keycmp(it, k) <= 0));
2184 assert_corr(ergo(it_before(it), it_keycmp(it, k) > 0));
2185 result = iam_add_rec(h, it, path, k, r);
2187 it->ii_state = IAM_IT_ATTACHED;
2188 assert_corr(ergo(result == 0,
2189 it_state(it) == IAM_IT_ATTACHED &&
2190 it_keycmp(it, k) == 0));
2194 static inline int iam_idle_blocks_limit(struct inode *inode)
2196 return (inode->i_sb->s_blocksize - sizeof(struct iam_idle_head)) >> 2;
2200 * If the leaf cannnot be recycled, we will lose one block for reusing.
2201 * It is not a serious issue because it almost the same of non-recycle.
2203 static iam_ptr_t iam_index_shrink(handle_t *h, struct iam_path *p,
2204 struct iam_leaf *l, struct buffer_head **bh)
2206 struct iam_container *c = p->ip_container;
2207 struct inode *inode = c->ic_object;
2208 struct iam_frame *frame = p->ip_frame;
2209 struct iam_entry *entries;
2210 struct iam_entry *pos;
2211 struct dynlock_handle *lh;
2215 if (c->ic_idle_failed)
2218 if (unlikely(frame == NULL))
2221 if (!iam_leaf_empty(l))
2224 lh = iam_lock_htree(c, frame->curidx, DLT_WRITE);
2226 CWARN("%s: No memory to recycle idle blocks\n",
2227 osd_ino2name(inode));
2231 rc = iam_txn_add(h, p, frame->bh);
2233 iam_unlock_htree(c, lh);
2237 iam_lock_bh(frame->bh);
2238 entries = frame->entries;
2239 count = dx_get_count(entries);
2241 * NOT shrink the last entry in the index node, which can be reused
2242 * directly by next new node.
2245 iam_unlock_bh(frame->bh);
2246 iam_unlock_htree(c, lh);
2250 pos = iam_find_position(p, frame);
2252 * There may be some new leaf nodes have been added or empty leaf nodes
2253 * have been shrinked during my delete operation.
2255 * If the empty leaf is not under current index node because the index
2256 * node has been split, then just skip the empty leaf, which is rare.
2258 if (unlikely(frame->leaf != dx_get_block(p, pos))) {
2259 iam_unlock_bh(frame->bh);
2260 iam_unlock_htree(c, lh);
2265 if (frame->at < iam_entry_shift(p, entries, count - 1)) {
2266 struct iam_entry *n = iam_entry_shift(p, frame->at, 1);
2268 memmove(frame->at, n,
2269 (char *)iam_entry_shift(p, entries, count) - (char *)n);
2270 frame->at_shifted = 1;
2272 dx_set_count(entries, count - 1);
2273 iam_unlock_bh(frame->bh);
2274 rc = iam_txn_dirty(h, p, frame->bh);
2275 iam_unlock_htree(c, lh);
2285 iam_install_idle_blocks(handle_t *h, struct iam_path *p, struct buffer_head *bh,
2286 __u32 *idle_blocks, iam_ptr_t blk)
2288 struct iam_container *c = p->ip_container;
2289 struct buffer_head *old = c->ic_idle_bh;
2290 struct iam_idle_head *head;
2293 head = (struct iam_idle_head *)(bh->b_data);
2294 head->iih_magic = cpu_to_le16(IAM_IDLE_HEADER_MAGIC);
2295 head->iih_count = 0;
2296 head->iih_next = *idle_blocks;
2297 /* The bh already get_write_accessed. */
2298 rc = iam_txn_dirty(h, p, bh);
2302 rc = iam_txn_add(h, p, c->ic_root_bh);
2306 iam_lock_bh(c->ic_root_bh);
2307 *idle_blocks = cpu_to_le32(blk);
2308 iam_unlock_bh(c->ic_root_bh);
2309 rc = iam_txn_dirty(h, p, c->ic_root_bh);
2311 /* NOT release old before new assigned. */
2316 iam_lock_bh(c->ic_root_bh);
2317 *idle_blocks = head->iih_next;
2318 iam_unlock_bh(c->ic_root_bh);
2324 * If the leaf cannnot be recycled, we will lose one block for reusing.
2325 * It is not a serious issue because it almost the same of non-recycle.
2327 static void iam_recycle_leaf(handle_t *h, struct iam_path *p,
2328 struct buffer_head *bh, iam_ptr_t blk)
2330 struct iam_container *c = p->ip_container;
2331 struct inode *inode = c->ic_object;
2332 struct iam_idle_head *head;
2337 mutex_lock(&c->ic_idle_mutex);
2338 if (unlikely(c->ic_idle_failed)) {
2343 idle_blocks = (__u32 *)(c->ic_root_bh->b_data +
2344 c->ic_descr->id_root_gap +
2345 sizeof(struct dx_countlimit));
2346 /* It is the first idle block. */
2347 if (c->ic_idle_bh == NULL) {
2348 rc = iam_install_idle_blocks(h, p, bh, idle_blocks, blk);
2352 head = (struct iam_idle_head *)(c->ic_idle_bh->b_data);
2353 count = le16_to_cpu(head->iih_count);
2354 /* Current ic_idle_bh is full, to be replaced by the leaf. */
2355 if (count == iam_idle_blocks_limit(inode)) {
2356 rc = iam_install_idle_blocks(h, p, bh, idle_blocks, blk);
2360 /* Just add to ic_idle_bh. */
2361 rc = iam_txn_add(h, p, c->ic_idle_bh);
2365 head->iih_blks[count] = cpu_to_le32(blk);
2366 head->iih_count = cpu_to_le16(count + 1);
2367 rc = iam_txn_dirty(h, p, c->ic_idle_bh);
2370 mutex_unlock(&c->ic_idle_mutex);
2372 CWARN("%s: idle blocks failed, will lose the blk %u\n",
2373 osd_ino2name(inode), blk);
2377 * Delete record under iterator.
2379 * precondition: it_state(it) == IAM_IT_ATTACHED &&
2380 * it->ii_flags&IAM_IT_WRITE &&
2382 * postcondition: it_state(it) == IAM_IT_ATTACHED ||
2383 * it_state(it) == IAM_IT_DETACHED
2385 int iam_it_rec_delete(handle_t *h, struct iam_iterator *it)
2388 struct iam_leaf *leaf;
2389 struct iam_path *path;
2391 assert_corr(it_state(it) == IAM_IT_ATTACHED &&
2392 it->ii_flags&IAM_IT_WRITE);
2393 assert_corr(it_at_rec(it));
2395 path = &it->ii_path;
2396 leaf = &path->ip_leaf;
2398 assert_inv(iam_path_check(path));
2400 result = iam_txn_add(h, path, leaf->il_bh);
2402 * no compaction for now.
2405 iam_rec_del(leaf, it->ii_flags&IAM_IT_MOVE);
2406 result = iam_txn_dirty(h, path, leaf->il_bh);
2407 if (result == 0 && iam_leaf_at_end(leaf)) {
2408 struct buffer_head *bh = NULL;
2411 blk = iam_index_shrink(h, path, leaf, &bh);
2412 if (it->ii_flags & IAM_IT_MOVE) {
2413 result = iam_it_next(it);
2419 iam_recycle_leaf(h, path, bh, blk);
2424 assert_inv(iam_path_check(path));
2425 assert_corr(it_state(it) == IAM_IT_ATTACHED ||
2426 it_state(it) == IAM_IT_DETACHED);
2431 * Convert iterator to cookie.
2433 * precondition: it_state(it) == IAM_IT_ATTACHED &&
2434 * iam_path_descr(it->ii_path)->id_key_size <= sizeof(iam_pos_t)
2435 * postcondition: it_state(it) == IAM_IT_ATTACHED
2437 iam_pos_t iam_it_store(const struct iam_iterator *it)
2441 assert_corr(it_state(it) == IAM_IT_ATTACHED);
2442 assert_corr(it_at_rec(it));
2443 assert_corr(iam_it_container(it)->ic_descr->id_ikey_size <=
2447 return *(iam_pos_t *)iam_it_ikey_get(it, (void *)&result);
2451 * Restore iterator from cookie.
2453 * precondition: it_state(it) == IAM_IT_DETACHED && it->ii_flags&IAM_IT_MOVE &&
2454 * iam_path_descr(it->ii_path)->id_key_size <= sizeof(iam_pos_t)
2455 * postcondition: ergo(result == 0, it_state(it) == IAM_IT_ATTACHED &&
2456 * iam_it_store(it) == pos)
2458 int iam_it_load(struct iam_iterator *it, iam_pos_t pos)
2460 assert_corr(it_state(it) == IAM_IT_DETACHED &&
2461 it->ii_flags&IAM_IT_MOVE);
2462 assert_corr(iam_it_container(it)->ic_descr->id_ikey_size <= sizeof pos);
2463 return iam_it_iget(it, (struct iam_ikey *)&pos);
2466 /***********************************************************************/
2468 /***********************************************************************/
2470 static inline int ptr_inside(void *base, size_t size, void *ptr)
2472 return (base <= ptr) && (ptr < base + size);
2475 static int iam_frame_invariant(struct iam_frame *f)
2479 f->bh->b_data != NULL &&
2480 ptr_inside(f->bh->b_data, f->bh->b_size, f->entries) &&
2481 ptr_inside(f->bh->b_data, f->bh->b_size, f->at) &&
2482 f->entries <= f->at);
2485 static int iam_leaf_invariant(struct iam_leaf *l)
2489 l->il_bh->b_data != NULL &&
2490 ptr_inside(l->il_bh->b_data, l->il_bh->b_size, l->il_entries) &&
2491 ptr_inside(l->il_bh->b_data, l->il_bh->b_size, l->il_at) &&
2492 l->il_entries <= l->il_at;
2495 static int iam_path_invariant(struct iam_path *p)
2499 if (p->ip_container == NULL ||
2500 p->ip_indirect < 0 || p->ip_indirect > DX_MAX_TREE_HEIGHT - 1 ||
2501 p->ip_frame != p->ip_frames + p->ip_indirect ||
2502 !iam_leaf_invariant(&p->ip_leaf))
2504 for (i = 0; i < ARRAY_SIZE(p->ip_frames); ++i) {
2505 if (i <= p->ip_indirect) {
2506 if (!iam_frame_invariant(&p->ip_frames[i]))
2513 int iam_it_invariant(struct iam_iterator *it)
2516 (it->ii_state == IAM_IT_DETACHED ||
2517 it->ii_state == IAM_IT_ATTACHED ||
2518 it->ii_state == IAM_IT_SKEWED) &&
2519 !(it->ii_flags & ~(IAM_IT_MOVE | IAM_IT_WRITE)) &&
2520 ergo(it->ii_state == IAM_IT_ATTACHED ||
2521 it->ii_state == IAM_IT_SKEWED,
2522 iam_path_invariant(&it->ii_path) &&
2523 equi(it_at_rec(it), it->ii_state == IAM_IT_SKEWED));
2527 * Search container @c for record with key @k. If record is found, its data
2528 * are moved into @r.
2530 * Return values: 0: found, -ENOENT: not-found, -ve: error
2532 int iam_lookup(struct iam_container *c, const struct iam_key *k,
2533 struct iam_rec *r, struct iam_path_descr *pd)
2535 struct iam_iterator it;
2538 iam_it_init(&it, c, 0, pd);
2540 result = iam_it_get_exact(&it, k);
2543 * record with required key found, copy it into user buffer
2545 iam_reccpy(&it.ii_path.ip_leaf, r);
2552 * Insert new record @r with key @k into container @c (within context of
2555 * Return values: 0: success, -ve: error, including -EEXIST when record with
2556 * given key is already present.
2558 * postcondition: ergo(result == 0 || result == -EEXIST,
2559 * iam_lookup(c, k, r2) > 0;
2561 int iam_insert(handle_t *h, struct iam_container *c, const struct iam_key *k,
2562 const struct iam_rec *r, struct iam_path_descr *pd)
2564 struct iam_iterator it;
2567 iam_it_init(&it, c, IAM_IT_WRITE, pd);
2569 result = iam_it_get_exact(&it, k);
2570 if (result == -ENOENT)
2571 result = iam_it_rec_insert(h, &it, k, r);
2572 else if (result == 0)
2580 * Update record with the key @k in container @c (within context of
2581 * transaction @h), new record is given by @r.
2583 * Return values: +1: skip because of the same rec value, 0: success,
2584 * -ve: error, including -ENOENT if no record with the given key found.
2586 int iam_update(handle_t *h, struct iam_container *c, const struct iam_key *k,
2587 const struct iam_rec *r, struct iam_path_descr *pd)
2589 struct iam_iterator it;
2590 struct iam_leaf *folio;
2593 iam_it_init(&it, c, IAM_IT_WRITE, pd);
2595 result = iam_it_get_exact(&it, k);
2597 folio = &it.ii_path.ip_leaf;
2598 result = iam_leaf_ops(folio)->rec_eq(folio, r);
2600 iam_it_rec_set(h, &it, r);
2610 * Delete existing record with key @k.
2612 * Return values: 0: success, -ENOENT: not-found, -ve: other error.
2614 * postcondition: ergo(result == 0 || result == -ENOENT,
2615 * !iam_lookup(c, k, *));
2617 int iam_delete(handle_t *h, struct iam_container *c, const struct iam_key *k,
2618 struct iam_path_descr *pd)
2620 struct iam_iterator it;
2623 iam_it_init(&it, c, IAM_IT_WRITE, pd);
2625 result = iam_it_get_exact(&it, k);
2627 iam_it_rec_delete(h, &it);
2633 int iam_root_limit(int rootgap, int blocksize, int size)
2638 limit = (blocksize - rootgap) / size;
2639 nlimit = blocksize / size;
2640 if (limit == nlimit)