- int i;
- int result;
- struct iam_frame *f;
- struct iam_descr *param;
-
- result = 1;
- param = iam_path_descr(p);
- for (i = 0; result && i < ARRAY_SIZE(p->ip_frames); ++i) {
- f = &p->ip_frames[i];
- if (f->bh != NULL) {
- result = dx_node_check(p, f);
- if (result)
- result = !param->id_ops->id_node_check(p, f);
- }
- }
- if (result && p->ip_leaf.il_bh != NULL)
- result = iam_leaf_check(&p->ip_leaf);
- if (result == 0) {
- ldiskfs_std_error(iam_path_obj(p)->i_sb, result);
- }
- return result;
+ int i;
+ int result;
+ struct iam_frame *f;
+ struct iam_descr *param;
+
+ result = 1;
+ param = iam_path_descr(p);
+ for (i = 0; result && i < ARRAY_SIZE(p->ip_frames); ++i) {
+ f = &p->ip_frames[i];
+ if (f->bh != NULL) {
+ result = dx_node_check(p, f);
+ if (result)
+ result = !param->id_ops->id_node_check(p, f);
+ }
+ }
+ if (result && p->ip_leaf.il_bh != NULL)
+ result = 1;
+ if (result == 0)
+ ldiskfs_std_error(iam_path_obj(p)->i_sb, result);
+
+ return result;
- return iam_leaf_ops(l)->can_add(l, k, r);
-}
-
-#if LDISKFS_INVARIANT_ON
-static int iam_leaf_check(struct iam_leaf *leaf)
-{
- return 1;
-#if 0
- struct iam_lentry *orig;
- struct iam_path *path;
- struct iam_container *bag;
- struct iam_ikey *k0;
- struct iam_ikey *k1;
- int result;
- int first;
-
- orig = leaf->il_at;
- path = iam_leaf_path(leaf);
- bag = iam_leaf_container(leaf);
-
- result = iam_leaf_ops(leaf)->init(leaf);
- if (result != 0)
- return result;
-
- first = 1;
- iam_leaf_start(leaf);
- k0 = iam_path_ikey(path, 0);
- k1 = iam_path_ikey(path, 1);
- while (!iam_leaf_at_end(leaf)) {
- iam_ikeycpy(bag, k0, k1);
- iam_ikeycpy(bag, k1, iam_leaf_ikey(leaf, k1));
- if (!first && iam_ikeycmp(bag, k0, k1) > 0) {
- return 0;
- }
- first = 0;
- iam_leaf_next(leaf);
- }
- leaf->il_at = orig;
- return 1;
-#endif
+ return iam_leaf_ops(l)->can_add(l, k, r);
- int count;
- struct iam_entry *p;
- struct iam_entry *q;
- struct iam_entry *m;
-
- count = dx_get_count(frame->entries);
- assert_corr(count && count <= dx_get_limit(frame->entries));
- p = iam_entry_shift(path, frame->entries,
- dx_index_is_compat(path) ? 1 : 2);
- q = iam_entry_shift(path, frame->entries, count - 1);
- while (p <= q) {
- m = iam_entry_shift(path, p, iam_entry_diff(path, q, p) / 2);
- if (iam_ikeycmp(path->ip_container, iam_ikey_at(path, m),
- path->ip_ikey_target) > 0)
- q = iam_entry_shift(path, m, -1);
- else
- p = iam_entry_shift(path, m, +1);
- }
- return iam_entry_shift(path, p, -1);
+ int count;
+ struct iam_entry *p;
+ struct iam_entry *q;
+ struct iam_entry *m;
+
+ count = dx_get_count(frame->entries);
+ assert_corr(count && count <= dx_get_limit(frame->entries));
+ p = iam_entry_shift(path, frame->entries,
+ dx_index_is_compat(path) ? 1 : 2);
+ q = iam_entry_shift(path, frame->entries, count - 1);
+ while (p <= q) {
+ m = iam_entry_shift(path, p, iam_entry_diff(path, q, p) / 2);
+ if (iam_ikeycmp(path->ip_container, iam_ikey_at(path, m),
+ path->ip_ikey_target) > 0)
+ q = iam_entry_shift(path, m, -1);
+ else
+ p = iam_entry_shift(path, m, +1);
+ }
+ return iam_entry_shift(path, p, -1);
- /*
- * Unfortunately we cannot assert this, as this function is sometimes
- * called by VFS under i_sem and without pdirops lock.
- */
- assert_corr(1 || iam_frame_is_locked(path, frame));
- assert_corr(count < dx_get_limit(entries));
- assert_corr(frame->at < iam_entry_shift(path, entries, count));
- assert_inv(dx_node_check(path, frame));
+ /*
+ * Unfortunately we cannot assert this, as this function is sometimes
+ * called by VFS under i_sem and without pdirops lock.
+ */
+ assert_corr(1 || iam_frame_is_locked(path, frame));
+ assert_corr(count < dx_get_limit(entries));
+ assert_corr(frame->at < iam_entry_shift(path, entries, count));
+ assert_inv(dx_node_check(path, frame));
- memmove(iam_entry_shift(path, new, 1), new,
- (char *)iam_entry_shift(path, entries, count) - (char *)new);
- dx_set_ikey(path, new, key);
- dx_set_block(path, new, ptr);
- dx_set_count(entries, count + 1);
- assert_inv(dx_node_check(path, frame));
+ memmove(iam_entry_shift(path, new, 1), new,
+ (char *)iam_entry_shift(path, entries, count) - (char *)new);
+ dx_set_ikey(path, new, key);
+ dx_set_block(path, new, ptr);
+ dx_set_count(entries, count + 1);
+ assert_inv(dx_node_check(path, frame));
- u32 ptr;
- int err = 0;
- int i;
-
- struct iam_descr *param;
- struct iam_frame *frame;
- struct iam_container *c;
-
- param = iam_path_descr(path);
- c = path->ip_container;
-
- ptr = param->id_ops->id_root_ptr(c);
- for (frame = path->ip_frames, i = 0; i <= path->ip_indirect;
- ++frame, ++i) {
- err = param->id_ops->id_node_read(c, (iam_ptr_t)ptr, NULL,
- &frame->bh);
- do_corr(schedule());
-
- iam_lock_bh(frame->bh);
- /*
- * node must be initialized under bh lock because concurrent
- * creation procedure may change it and iam_lookup_try() will
- * see obsolete tree height. -bzzz
- */
- if (err != 0)
- break;
-
- if (LDISKFS_INVARIANT_ON) {
- err = param->id_ops->id_node_check(path, frame);
- if (err != 0)
- break;
- }
-
- err = param->id_ops->id_node_load(path, frame);
- if (err != 0)
- break;
-
- assert_inv(dx_node_check(path, frame));
- /*
- * splitting may change root index block and move hash we're
- * looking for into another index block so, we have to check
- * this situation and repeat from begining if path got changed
- * -bzzz
- */
- if (i > 0) {
- err = iam_check_path(path, frame - 1);
- if (err != 0)
- break;
- }
-
- frame->at = iam_find_position(path, frame);
- frame->curidx = ptr;
- frame->leaf = ptr = dx_get_block(path, frame->at);
-
- iam_unlock_bh(frame->bh);
- do_corr(schedule());
- }
- if (err != 0)
- iam_unlock_bh(frame->bh);
- path->ip_frame = --frame;
- return err;
+ u32 ptr;
+ int err = 0;
+ int i;
+
+ struct iam_descr *param;
+ struct iam_frame *frame;
+ struct iam_container *c;
+
+ param = iam_path_descr(path);
+ c = path->ip_container;
+
+ ptr = param->id_ops->id_root_ptr(c);
+ for (frame = path->ip_frames, i = 0; i <= path->ip_indirect;
+ ++frame, ++i) {
+ err = param->id_ops->id_node_read(c, (iam_ptr_t)ptr, NULL,
+ &frame->bh);
+ do_corr(schedule());
+
+ iam_lock_bh(frame->bh);
+ /*
+ * node must be initialized under bh lock because concurrent
+ * creation procedure may change it and iam_lookup_try() will
+ * see obsolete tree height. -bzzz
+ */
+ if (err != 0)
+ break;
+
+ if (LDISKFS_INVARIANT_ON) {
+ err = param->id_ops->id_node_check(path, frame);
+ if (err != 0)
+ break;
+ }
+
+ err = param->id_ops->id_node_load(path, frame);
+ if (err != 0)
+ break;
+
+ assert_inv(dx_node_check(path, frame));
+ /*
+ * splitting may change root index block and move hash we're
+ * looking for into another index block so, we have to check
+ * this situation and repeat from begining if path got changed
+ * -bzzz
+ */
+ if (i > 0) {
+ err = iam_check_path(path, frame - 1);
+ if (err != 0)
+ break;
+ }
+
+ frame->at = iam_find_position(path, frame);
+ frame->curidx = ptr;
+ frame->leaf = ptr = dx_get_block(path, frame->at);
+
+ iam_unlock_bh(frame->bh);
+ do_corr(schedule());
+ }
+ if (err != 0)
+ iam_unlock_bh(frame->bh);
+ path->ip_frame = --frame;
+ return err;
- struct iam_frame *bottom;
- struct iam_frame *scan;
- int i;
- int result;
-
- do_corr(schedule());
-
- for (bottom = path->ip_frames, i = 0;
- i < DX_MAX_TREE_HEIGHT && bottom->bh != NULL; ++bottom, ++i) {
- ; /* find last filled in frame */
- }
-
- /*
- * Lock frames, bottom to top.
- */
- for (scan = bottom - 1; scan >= path->ip_frames; --scan)
- iam_lock_bh(scan->bh);
- /*
- * Check them top to bottom.
- */
- result = 0;
- for (scan = path->ip_frames; scan < bottom; ++scan) {
- struct iam_entry *pos;
-
- if (search) {
- if (iam_check_fast(path, scan) == 0)
- continue;
-
- pos = iam_find_position(path, scan);
- if (scan->leaf != dx_get_block(path, pos)) {
- result = -EAGAIN;
- break;
- }
- scan->at = pos;
- } else {
- pos = iam_entry_shift(path, scan->entries,
- dx_get_count(scan->entries) - 1);
- if (scan->at > pos ||
- scan->leaf != dx_get_block(path, scan->at)) {
- result = -EAGAIN;
- break;
- }
- }
- }
-
- /*
- * Unlock top to bottom.
- */
- for (scan = path->ip_frames; scan < bottom; ++scan)
+ struct iam_frame *bottom;
+ struct iam_frame *scan;
+ int i;
+ int result;
+
+ do_corr(schedule());
+
+ for (bottom = path->ip_frames, i = 0;
+ i < DX_MAX_TREE_HEIGHT && bottom->bh != NULL; ++bottom, ++i) {
+ ; /* find last filled in frame */
+ }
+
+ /*
+ * Lock frames, bottom to top.
+ */
+ for (scan = bottom - 1; scan >= path->ip_frames; --scan)
+ iam_lock_bh(scan->bh);
+ /*
+ * Check them top to bottom.
+ */
+ result = 0;
+ for (scan = path->ip_frames; scan < bottom; ++scan) {
+ struct iam_entry *pos;
+
+ if (search) {
+ if (iam_check_fast(path, scan) == 0)
+ continue;
+
+ pos = iam_find_position(path, scan);
+ if (scan->leaf != dx_get_block(path, pos)) {
+ result = -EAGAIN;
+ break;
+ }
+ scan->at = pos;
+ } else {
+ pos = iam_entry_shift(path, scan->entries,
+ dx_get_count(scan->entries) - 1);
+ if (scan->at > pos ||
+ scan->leaf != dx_get_block(path, scan->at)) {
+ result = -EAGAIN;
+ break;
+ }
+ }
+ }
+
+ /*
+ * Unlock top to bottom.
+ */
+ for (scan = path->ip_frames; scan < bottom; ++scan)
- struct iam_container *c;
- struct iam_leaf *leaf;
- int result;
-
- c = path->ip_container;
- leaf = &path->ip_leaf;
- result = iam_lookup_lock(path, &leaf->il_lock, DLT_WRITE);
- assert_inv(iam_path_check(path));
- do_corr(schedule());
- if (result == 0) {
- result = iam_leaf_load(path);
- assert_inv(ergo(result == 0, iam_leaf_check(leaf)));
- if (result == 0) {
- do_corr(schedule());
- if (index)
- result = iam_leaf_ops(leaf)->
- ilookup(leaf, path->ip_ikey_target);
- else
- result = iam_leaf_ops(leaf)->
- lookup(leaf, path->ip_key_target);
- do_corr(schedule());
- }
- if (result < 0)
- iam_leaf_unlock(leaf);
- }
- return result;
+ struct iam_leaf *leaf;
+ int result;
+
+ leaf = &path->ip_leaf;
+ result = iam_lookup_lock(path, &leaf->il_lock, DLT_WRITE);
+ assert_inv(iam_path_check(path));
+ do_corr(schedule());
+ if (result == 0) {
+ result = iam_leaf_load(path);
+ if (result == 0) {
+ do_corr(schedule());
+ if (index)
+ result = iam_leaf_ops(leaf)->
+ ilookup(leaf, path->ip_ikey_target);
+ else
+ result = iam_leaf_ops(leaf)->
+ lookup(leaf, path->ip_key_target);
+ do_corr(schedule());
+ }
+ if (result < 0)
+ iam_leaf_unlock(leaf);
+ }
+ return result;
- int result;
- assert_corr(it_state(it) == IAM_IT_DETACHED);
-
- result = iam_path_lookup(&it->ii_path, index);
- if (result >= 0) {
- int collision;
-
- collision = result & IAM_LOOKUP_LAST;
- switch (result & ~IAM_LOOKUP_LAST) {
- case IAM_LOOKUP_EXACT:
- result = +1;
- it->ii_state = IAM_IT_ATTACHED;
- break;
- case IAM_LOOKUP_OK:
- result = 0;
- it->ii_state = IAM_IT_ATTACHED;
- break;
- case IAM_LOOKUP_BEFORE:
- case IAM_LOOKUP_EMPTY:
- result = 0;
- it->ii_state = IAM_IT_SKEWED;
- break;
- default:
- assert(0);
- }
- result |= collision;
- }
- /*
- * See iam_it_get_exact() for explanation.
- */
- assert_corr(result != -ENOENT);
- return result;
+ int result;
+
+ assert_corr(it_state(it) == IAM_IT_DETACHED);
+
+ result = iam_path_lookup(&it->ii_path, index);
+ if (result >= 0) {
+ int collision;
+
+ collision = result & IAM_LOOKUP_LAST;
+ switch (result & ~IAM_LOOKUP_LAST) {
+ case IAM_LOOKUP_EXACT:
+ result = +1;
+ it->ii_state = IAM_IT_ATTACHED;
+ break;
+ case IAM_LOOKUP_OK:
+ result = 0;
+ it->ii_state = IAM_IT_ATTACHED;
+ break;
+ case IAM_LOOKUP_BEFORE:
+ case IAM_LOOKUP_EMPTY:
+ result = 0;
+ it->ii_state = IAM_IT_SKEWED;
+ break;
+ default:
+ assert(0);
+ }
+ result |= collision;
+ }
+ /*
+ * See iam_it_get_exact() for explanation.
+ */
+ assert_corr(result != -ENOENT);
+ return result;
- dst->ii_flags = src->ii_flags;
- dst->ii_state = src->ii_state;
- /* XXX not yet. iam_path_dup(&dst->ii_path, &src->ii_path); */
- /*
- * XXX: duplicate lock.
- */
- assert_corr(it_state(dst) == it_state(src));
- assert_corr(iam_it_container(dst) == iam_it_container(src));
- assert_corr(dst->ii_flags = src->ii_flags);
- assert_corr(ergo(it_state(src) == IAM_IT_ATTACHED,
- iam_it_rec_get(dst) == iam_it_rec_get(src) &&
- iam_it_key_get(dst) == iam_it_key_get(src)));
-
+ dst->ii_flags = src->ii_flags;
+ dst->ii_state = src->ii_state;
+ /* XXX not yet. iam_path_dup(&dst->ii_path, &src->ii_path); */
+ /*
+ * XXX: duplicate lock.
+ */
+ assert_corr(it_state(dst) == it_state(src));
+ assert_corr(iam_it_container(dst) == iam_it_container(src));
+ assert_corr(dst->ii_flags = src->ii_flags);
+ assert_corr(ergo(it_state(src) == IAM_IT_ATTACHED,
+ iam_it_rec_get(dst) == iam_it_rec_get(src) &&
+ iam_it_key_get(dst) == iam_it_key_get(src)));
- struct iam_frame *p;
- struct buffer_head *bh;
- int err, num_frames = 0;
- __u32 bhash;
-
- p = path->ip_frame;
- /*
- * Find the next leaf page by incrementing the frame pointer.
- * If we run out of entries in the interior node, loop around and
- * increment pointer in the parent node. When we break out of
- * this loop, num_frames indicates the number of interior
- * nodes need to be read.
- */
- while (1) {
- do_corr(schedule());
- iam_lock_bh(p->bh);
+ struct iam_frame *p;
+ struct buffer_head *bh;
+ int err, num_frames = 0;
+ __u32 bhash;
+
+ p = path->ip_frame;
+ /*
+ * Find the next leaf page by incrementing the frame pointer.
+ * If we run out of entries in the interior node, loop around and
+ * increment pointer in the parent node. When we break out of
+ * this loop, num_frames indicates the number of interior
+ * nodes need to be read.
+ */
+ while (1) {
+ do_corr(schedule());
+ iam_lock_bh(p->bh);
- if (p->at < iam_entry_shift(path, p->entries,
- dx_get_count(p->entries))) {
- p->leaf = dx_get_block(path, p->at);
- iam_unlock_bh(p->bh);
- break;
- }
- iam_unlock_bh(p->bh);
- if (p == path->ip_frames)
- return 0;
- num_frames++;
- --p;
- }
-
- if (compat) {
- /*
- * Htree hash magic.
- */
- /*
- * If the hash is 1, then continue only if the next page has a
- * continuation hash of any value. This is used for readdir
- * handling. Otherwise, check to see if the hash matches the
- * desired contiuation hash. If it doesn't, return since
- * there's no point to read in the successive index pages.
- */
- dx_get_ikey(path, p->at, (struct iam_ikey *)&bhash);
- if (start_hash)
- *start_hash = bhash;
- if ((hash & 1) == 0) {
- if ((bhash & ~1) != hash)
- return 0;
- }
- }
- /*
- * If the hash is HASH_NB_ALWAYS, we always go to the next
- * block so no check is necessary
- */
- while (num_frames--) {
- iam_ptr_t idx;
-
- do_corr(schedule());
- iam_lock_bh(p->bh);
- idx = p->leaf = dx_get_block(path, p->at);
- iam_unlock_bh(p->bh);
- err = iam_path_descr(path)->id_ops->
- id_node_read(path->ip_container, idx, NULL, &bh);
- if (err != 0)
- return err; /* Failure */
- ++p;
- brelse(p->bh);
- assert_corr(p->bh != bh);
- p->bh = bh;
- p->entries = dx_node_get_entries(path, p);
- p->at = iam_entry_shift(path, p->entries, !compat);
- assert_corr(p->curidx != idx);
- p->curidx = idx;
- iam_lock_bh(p->bh);
- assert_corr(p->leaf != dx_get_block(path, p->at));
- p->leaf = dx_get_block(path, p->at);
- iam_unlock_bh(p->bh);
- assert_inv(dx_node_check(path, p));
- }
- return 1;
-}
+ if (p->at < iam_entry_shift(path, p->entries,
+ dx_get_count(p->entries))) {
+ p->leaf = dx_get_block(path, p->at);
+ iam_unlock_bh(p->bh);
+ break;
+ }
+ iam_unlock_bh(p->bh);
+ if (p == path->ip_frames)
+ return 0;
+ num_frames++;
+ --p;
+ }
+
+ if (compat) {
+ /*
+ * Htree hash magic.
+ */
+
+ /*
+ * If the hash is 1, then continue only if the next page has a
+ * continuation hash of any value. This is used for readdir
+ * handling. Otherwise, check to see if the hash matches the
+ * desired contiuation hash. If it doesn't, return since
+ * there's no point to read in the successive index pages.
+ */
+ dx_get_ikey(path, p->at, (struct iam_ikey *)&bhash);
+ if (start_hash)
+ *start_hash = bhash;
+ if ((hash & 1) == 0) {
+ if ((bhash & ~1) != hash)
+ return 0;
+ }
+ }
+ /*
+ * If the hash is HASH_NB_ALWAYS, we always go to the next
+ * block so no check is necessary
+ */
+ while (num_frames--) {
+ iam_ptr_t idx;
- int result;
- struct inode *object;
-
- /*
- * Locking for iam_index_next()... is to be described.
- */
-
- object = c->ic_object;
- cursor = path->ip_frame->leaf;
-
- while (1) {
- result = iam_index_lock(path, lh);
- do_corr(schedule());
- if (result < 0)
- break;
-
- result = iam_check_full_path(path, 0);
- if (result == 0 && cursor == path->ip_frame->leaf) {
- result = iam_index_advance(path);
-
- assert_corr(result == 0 ||
- cursor != path->ip_frame->leaf);
- break;
- }
- do {
+ int result;
+
+ /*
+ * Locking for iam_index_next()... is to be described.
+ */
+
+ cursor = path->ip_frame->leaf;
+
+ while (1) {
+ result = iam_index_lock(path, lh);
+ do_corr(schedule());
+ if (result < 0)
+ break;
+
+ result = iam_check_full_path(path, 0);
+ if (result == 0 && cursor == path->ip_frame->leaf) {
+ result = iam_index_advance(path);
+
+ assert_corr(result == 0 ||
+ cursor != path->ip_frame->leaf);
+ break;
+ }
+ do {
- iam_path_release(path);
- do_corr(schedule());
-
- result = __iam_path_lookup(path);
- if (result < 0)
- break;
-
- while (path->ip_frame->leaf != cursor) {
- do_corr(schedule());
-
- result = iam_index_lock(path, lh);
- do_corr(schedule());
- if (result < 0)
- break;
-
- result = iam_check_full_path(path, 0);
- if (result != 0)
- break;
-
- result = iam_index_advance(path);
- if (result == 0) {
- CERROR("cannot find cursor : %u\n",
- cursor);
- result = -EIO;
- }
- if (result < 0)
- break;
- result = iam_check_full_path(path, 0);
- if (result != 0)
- break;
+ iam_path_release(path);
+ do_corr(schedule());
+
+ result = __iam_path_lookup(path);
+ if (result < 0)
+ break;
+
+ while (path->ip_frame->leaf != cursor) {
+ do_corr(schedule());
+
+ result = iam_index_lock(path, lh);
+ do_corr(schedule());
+ if (result < 0)
+ break;
+
+ result = iam_check_full_path(path, 0);
+ if (result != 0)
+ break;
+
+ result = iam_index_advance(path);
+ if (result == 0) {
+ CERROR("cannot find cursor : %u\n",
+ cursor);
+ result = -EIO;
+ }
+ if (result < 0)
+ break;
+ result = iam_check_full_path(path, 0);
+ if (result != 0)
+ break;
- int result;
- struct iam_path *path;
- struct iam_leaf *leaf;
- do_corr(struct iam_ikey *ik_orig);
-
- /* assert_corr(it->ii_flags&IAM_IT_MOVE); */
- assert_corr(it_state(it) == IAM_IT_ATTACHED ||
- it_state(it) == IAM_IT_SKEWED);
-
- path = &it->ii_path;
- leaf = &path->ip_leaf;
-
- assert_corr(iam_leaf_is_locked(leaf));
-
- result = 0;
- do_corr(ik_orig = it_at_rec(it) ?
- iam_it_ikey_get(it, iam_path_ikey(path, 2)) : NULL);
- if (it_before(it)) {
- assert_corr(!iam_leaf_at_end(leaf));
- it->ii_state = IAM_IT_ATTACHED;
- } else {
- if (!iam_leaf_at_end(leaf))
- /* advance within leaf node */
- iam_leaf_next(leaf);
- /*
- * multiple iterations may be necessary due to empty leaves.
- */
- while (result == 0 && iam_leaf_at_end(leaf)) {
- do_corr(schedule());
- /* advance index portion of the path */
- result = iam_index_next(iam_it_container(it), path);
- assert_corr(iam_leaf_is_locked(leaf));
- if (result == 1) {
+ int result;
+ struct iam_path *path;
+ struct iam_leaf *leaf;
+
+ do_corr(struct iam_ikey *ik_orig);
+
+ /* assert_corr(it->ii_flags&IAM_IT_MOVE); */
+ assert_corr(it_state(it) == IAM_IT_ATTACHED ||
+ it_state(it) == IAM_IT_SKEWED);
+
+ path = &it->ii_path;
+ leaf = &path->ip_leaf;
+
+ assert_corr(iam_leaf_is_locked(leaf));
+
+ result = 0;
+ do_corr(ik_orig = it_at_rec(it) ?
+ iam_it_ikey_get(it, iam_path_ikey(path, 2)) : NULL);
+ if (it_before(it)) {
+ assert_corr(!iam_leaf_at_end(leaf));
+ it->ii_state = IAM_IT_ATTACHED;
+ } else {
+ if (!iam_leaf_at_end(leaf))
+ /* advance within leaf node */
+ iam_leaf_next(leaf);
+ /*
+ * multiple iterations may be necessary due to empty leaves.
+ */
+ while (result == 0 && iam_leaf_at_end(leaf)) {
+ do_corr(schedule());
+ /* advance index portion of the path */
+ result = iam_index_next(iam_it_container(it), path);
+ assert_corr(iam_leaf_is_locked(leaf));
+ if (result == 1) {
- if (lh != NULL) {
- iam_leaf_fini(leaf);
- leaf->il_lock = lh;
- result = iam_leaf_load(path);
- if (result == 0)
- iam_leaf_start(leaf);
- } else
- result = -ENOMEM;
- } else if (result == 0)
- /* end of container reached */
- result = +1;
- if (result != 0)
- iam_it_put(it);
- }
- if (result == 0)
- it->ii_state = IAM_IT_ATTACHED;
- }
- assert_corr(ergo(result == 0, it_state(it) == IAM_IT_ATTACHED));
- assert_corr(ergo(result > 0, it_state(it) == IAM_IT_DETACHED));
- assert_corr(ergo(result == 0 && ik_orig != NULL,
- it_ikeycmp(it, ik_orig) >= 0));
- return result;
+ if (lh != NULL) {
+ iam_leaf_fini(leaf);
+ leaf->il_lock = lh;
+ result = iam_leaf_load(path);
+ if (result == 0)
+ iam_leaf_start(leaf);
+ } else
+ result = -ENOMEM;
+ } else if (result == 0)
+ /* end of container reached */
+ result = +1;
+ if (result != 0)
+ iam_it_put(it);
+ }
+ if (result == 0)
+ it->ii_state = IAM_IT_ATTACHED;
+ }
+ assert_corr(ergo(result == 0, it_state(it) == IAM_IT_ATTACHED));
+ assert_corr(ergo(result > 0, it_state(it) == IAM_IT_DETACHED));
+ assert_corr(ergo(result == 0 && ik_orig != NULL,
+ it_ikeycmp(it, ik_orig) >= 0));
+ return result;
- /*
- * NOTE: very subtle piece of code competing dx_probe() may find 2nd
- * level index in root index, then we insert new index here and set
- * new count in that 2nd level index. so, dx_probe() may see 2nd level
- * index w/o hash it looks for. the solution is to check root index
- * after we locked just founded 2nd level index -bzzz
- */
- iam_insert_key_lock(path, parent, pivot, newblock);
+ /*
+ * NOTE: very subtle piece of code competing dx_probe() may find 2nd
+ * level index in root index, then we insert new index here and set
+ * new count in that 2nd level index. so, dx_probe() may see 2nd level
+ * index w/o hash it looks for. the solution is to check root index
+ * after we locked just founded 2nd level index -bzzz
+ */
+ iam_insert_key_lock(path, parent, pivot, newblock);
- u32 newblock[DX_MAX_TREE_HEIGHT] = {0};
- struct dynlock_handle *lock[DX_MAX_TREE_HEIGHT] = {NULL,};
- struct dynlock_handle *new_lock[DX_MAX_TREE_HEIGHT] = {NULL,};
- struct inode *dir = iam_path_obj(path);
- struct iam_descr *descr;
- int nr_splet;
- int i, err;
-
- descr = iam_path_descr(path);
- /*
- * Algorithm below depends on this.
- */
- assert_corr(dx_root_limit(path) < dx_node_limit(path));
-
- frame = path->ip_frame;
- entries = frame->entries;
-
- /*
- * Tall-tree handling: we might have to split multiple index blocks
- * all the way up to tree root. Tricky point here is error handling:
- * to avoid complicated undo/rollback we
- *
- * - first allocate all necessary blocks
- *
- * - insert pointers into them atomically.
- */
-
- /*
- * Locking: leaf is already locked. htree-locks are acquired on all
- * index nodes that require split bottom-to-top, on the "safe" node,
- * and on all new nodes
- */
-
- dxtrace(printk("using %u of %u node entries\n",
- dx_get_count(entries), dx_get_limit(entries)));
-
- /* What levels need split? */
- for (nr_splet = 0; frame >= path->ip_frames &&
- dx_get_count(frame->entries) == dx_get_limit(frame->entries);
- --frame, ++nr_splet) {
- do_corr(schedule());
- if (nr_splet == DX_MAX_TREE_HEIGHT) {
- /*
- CWARN(dir->i_sb, __FUNCTION__,
- "Directory index full!\n");
- */
- err = -ENOSPC;
- goto cleanup;
- }
- }
-
- safe = frame;
-
- /*
- * Lock all nodes, bottom to top.
- */
- for (frame = path->ip_frame, i = nr_splet; i >= 0; --i, --frame) {
+ u32 newblock[DX_MAX_TREE_HEIGHT] = {0};
+ struct dynlock_handle *lock[DX_MAX_TREE_HEIGHT] = {NULL,};
+ struct dynlock_handle *new_lock[DX_MAX_TREE_HEIGHT] = {NULL,};
+ struct inode *dir = iam_path_obj(path);
+ struct iam_descr *descr;
+ int nr_splet;
+ int i, err;
+
+ descr = iam_path_descr(path);
+ /*
+ * Algorithm below depends on this.
+ */
+ assert_corr(dx_root_limit(path) < dx_node_limit(path));
+
+ frame = path->ip_frame;
+ entries = frame->entries;
+
+ /*
+ * Tall-tree handling: we might have to split multiple index blocks
+ * all the way up to tree root. Tricky point here is error handling:
+ * to avoid complicated undo/rollback we
+ *
+ * - first allocate all necessary blocks
+ *
+ * - insert pointers into them atomically.
+ */
+
+ /*
+ * Locking: leaf is already locked. htree-locks are acquired on all
+ * index nodes that require split bottom-to-top, on the "safe" node,
+ * and on all new nodes
+ */
+
+ dxtrace(printk("using %u of %u node entries\n",
+ dx_get_count(entries), dx_get_limit(entries)));
+
+ /* What levels need split? */
+ for (nr_splet = 0; frame >= path->ip_frames &&
+ dx_get_count(frame->entries) == dx_get_limit(frame->entries);
+ --frame, ++nr_splet) {
+ do_corr(schedule());
+ if (nr_splet == DX_MAX_TREE_HEIGHT) {
+ /*
+ * CWARN(dir->i_sb, __FUNCTION__,
+ * "Directory index full!\n");
+ */
+ err = -ENOSPC;
+ goto cleanup;
+ }
+ }
+
+ safe = frame;
+
+ /*
+ * Lock all nodes, bottom to top.
+ */
+ for (frame = path->ip_frame, i = nr_splet; i >= 0; --i, --frame) {
- }
-
- /*
- * Check for concurrent index modification.
- */
- err = iam_check_full_path(path, 1);
- if (err)
- goto cleanup;
- /*
- * And check that the same number of nodes is to be split.
- */
- for (i = 0, frame = path->ip_frame; frame >= path->ip_frames &&
- dx_get_count(frame->entries) == dx_get_limit(frame->entries);
- --frame, ++i) {
- ;
- }
- if (i != nr_splet) {
- err = -EAGAIN;
- goto cleanup;
- }
-
- /* Go back down, allocating blocks, locking them, and adding into
- * transaction... */
- for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
+ }
+
+ /*
+ * Check for concurrent index modification.
+ */
+ err = iam_check_full_path(path, 1);
+ if (err)
+ goto cleanup;
+ /*
+ * And check that the same number of nodes is to be split.
+ */
+ for (i = 0, frame = path->ip_frame; frame >= path->ip_frames &&
+ dx_get_count(frame->entries) == dx_get_limit(frame->entries);
+ --frame, ++i) {
+ ;
+ }
+ if (i != nr_splet) {
+ err = -EAGAIN;
+ goto cleanup;
+ }
+
+ /*
+ * Go back down, allocating blocks, locking them, and adding into
+ * transaction...
+ */
+ for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
- do_corr(schedule());
- BUFFER_TRACE(frame->bh, "get_write_access");
- err = ldiskfs_journal_get_write_access(handle, frame->bh);
- if (err)
- goto journal_error;
- }
- /* Add "safe" node to transaction too */
- if (safe + 1 != path->ip_frames) {
- do_corr(schedule());
- err = ldiskfs_journal_get_write_access(handle, safe->bh);
- if (err)
- goto journal_error;
- }
-
- /* Go through nodes once more, inserting pointers */
- for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
- unsigned count;
- int idx;
- struct buffer_head *bh2;
- struct buffer_head *bh;
-
- entries = frame->entries;
- count = dx_get_count(entries);
- idx = iam_entry_diff(path, frame->at, entries);
-
- bh2 = bh_new[i];
- entries2 = dx_get_entries(path, bh2->b_data, 0);
-
- bh = frame->bh;
- if (frame == path->ip_frames) {
- /* splitting root node. Tricky point:
- *
- * In the "normal" B-tree we'd split root *and* add
- * new root to the tree with pointers to the old root
- * and its sibling (thus introducing two new nodes).
- *
- * In htree it's enough to add one node, because
- * capacity of the root node is smaller than that of
- * non-root one.
- */
- struct iam_frame *frames;
- struct iam_entry *next;
-
- assert_corr(i == 0);
-
- do_corr(schedule());
-
- frames = path->ip_frames;
- memcpy((char *) entries2, (char *) entries,
- count * iam_entry_size(path));
- dx_set_limit(entries2, dx_node_limit(path));
-
- /* Set up root */
- iam_lock_bh(frame->bh);
- next = descr->id_ops->id_root_inc(path->ip_container,
- path, frame);
- dx_set_block(path, next, newblock[0]);
- iam_unlock_bh(frame->bh);
-
- do_corr(schedule());
- /* Shift frames in the path */
- memmove(frames + 2, frames + 1,
- (sizeof path->ip_frames) - 2 * sizeof frames[0]);
- /* Add new access path frame */
- frames[1].at = iam_entry_shift(path, entries2, idx);
- frames[1].entries = entries = entries2;
- frames[1].bh = bh2;
- assert_inv(dx_node_check(path, frame));
- ++ path->ip_frame;
- ++ frame;
- assert_inv(dx_node_check(path, frame));
- bh_new[0] = NULL; /* buffer head is "consumed" */
+ do_corr(schedule());
+ BUFFER_TRACE(frame->bh, "get_write_access");
+ err = ldiskfs_journal_get_write_access(handle, frame->bh);
+ if (err)
+ goto journal_error;
+ }
+ /* Add "safe" node to transaction too */
+ if (safe + 1 != path->ip_frames) {
+ do_corr(schedule());
+ err = ldiskfs_journal_get_write_access(handle, safe->bh);
+ if (err)
+ goto journal_error;
+ }
+
+ /* Go through nodes once more, inserting pointers */
+ for (frame = safe + 1, i = 0; i < nr_splet; ++i, ++frame) {
+ unsigned count;
+ int idx;
+ struct buffer_head *bh2;
+ struct buffer_head *bh;
+
+ entries = frame->entries;
+ count = dx_get_count(entries);
+ idx = iam_entry_diff(path, frame->at, entries);
+
+ bh2 = bh_new[i];
+ entries2 = dx_get_entries(path, bh2->b_data, 0);
+
+ bh = frame->bh;
+ if (frame == path->ip_frames) {
+ /* splitting root node. Tricky point:
+ *
+ * In the "normal" B-tree we'd split root *and* add
+ * new root to the tree with pointers to the old root
+ * and its sibling (thus introducing two new nodes).
+ *
+ * In htree it's enough to add one node, because
+ * capacity of the root node is smaller than that of
+ * non-root one.
+ */
+ struct iam_frame *frames;
+ struct iam_entry *next;
+
+ assert_corr(i == 0);
+
+ do_corr(schedule());
+
+ frames = path->ip_frames;
+ memcpy((char *) entries2, (char *) entries,
+ count * iam_entry_size(path));
+ dx_set_limit(entries2, dx_node_limit(path));
+
+ /* Set up root */
+ iam_lock_bh(frame->bh);
+ next = descr->id_ops->id_root_inc(path->ip_container,
+ path, frame);
+ dx_set_block(path, next, newblock[0]);
+ iam_unlock_bh(frame->bh);
+
+ do_corr(schedule());
+ /* Shift frames in the path */
+ memmove(frames + 2, frames + 1,
+ (sizeof path->ip_frames) - 2 * sizeof frames[0]);
+ /* Add new access path frame */
+ frames[1].at = iam_entry_shift(path, entries2, idx);
+ frames[1].entries = entries = entries2;
+ frames[1].bh = bh2;
+ assert_inv(dx_node_check(path, frame));
+ ++ path->ip_frame;
+ ++ frame;
+ assert_inv(dx_node_check(path, frame));
+ bh_new[0] = NULL; /* buffer head is "consumed" */
- if (err)
- goto journal_error;
- do_corr(schedule());
- } else {
- /* splitting non-root index node. */
- struct iam_frame *parent = frame - 1;
-
- do_corr(schedule());
- count = iam_shift_entries(path, frame, count,
- entries, entries2, newblock[i]);
- /* Which index block gets the new entry? */
- if (idx >= count) {
- int d = dx_index_is_compat(path) ? 0 : +1;
-
- frame->at = iam_entry_shift(path, entries2,
- idx - count + d);
- frame->entries = entries = entries2;
- frame->curidx = newblock[i];
- swap(frame->bh, bh2);
- assert_corr(lock[i + 1] != NULL);
- assert_corr(new_lock[i] != NULL);
- swap(lock[i + 1], new_lock[i]);
- bh_new[i] = bh2;
- parent->at = iam_entry_shift(path,
- parent->at, +1);
- }
- assert_inv(dx_node_check(path, frame));
- assert_inv(dx_node_check(path, parent));
- dxtrace(dx_show_index ("node", frame->entries));
- dxtrace(dx_show_index ("node",
- ((struct dx_node *) bh2->b_data)->entries));
+ if (err)
+ goto journal_error;
+ do_corr(schedule());
+ } else {
+ /* splitting non-root index node. */
+ struct iam_frame *parent = frame - 1;
+
+ do_corr(schedule());
+ count = iam_shift_entries(path, frame, count,
+ entries, entries2, newblock[i]);
+ /* Which index block gets the new entry? */
+ if (idx >= count) {
+ int d = dx_index_is_compat(path) ? 0 : +1;
+
+ frame->at = iam_entry_shift(path, entries2,
+ idx - count + d);
+ frame->entries = entries = entries2;
+ frame->curidx = newblock[i];
+ swap(frame->bh, bh2);
+ assert_corr(lock[i + 1] != NULL);
+ assert_corr(new_lock[i] != NULL);
+ swap(lock[i + 1], new_lock[i]);
+ bh_new[i] = bh2;
+ parent->at = iam_entry_shift(path,
+ parent->at, +1);
+ }
+ assert_inv(dx_node_check(path, frame));
+ assert_inv(dx_node_check(path, parent));
+ dxtrace(dx_show_index("node", frame->entries));
+ dxtrace(dx_show_index("node",
+ ((struct dx_node *) bh2->b_data)->entries));
- int err;
- struct iam_leaf *leaf;
-
- leaf = &path->ip_leaf;
- assert_inv(iam_leaf_check(leaf));
- assert_inv(iam_path_check(path));
- err = iam_txn_add(handle, path, leaf->il_bh);
- if (err == 0) {
- do_corr(schedule());
- if (!iam_leaf_can_add(leaf, k, r)) {
- struct dynlock_handle *lh = NULL;
-
- do {
- assert_corr(lh == NULL);
- do_corr(schedule());
- err = split_index_node(handle, path, &lh);
- if (err == -EAGAIN) {
- assert_corr(lh == NULL);
-
- iam_path_fini(path);
- it->ii_state = IAM_IT_DETACHED;
-
- do_corr(schedule());
- err = iam_it_get_exact(it, k);
- if (err == -ENOENT)
- err = +1; /* repeat split */
- else if (err == 0)
- err = -EEXIST;
- }
- } while (err > 0);
- assert_inv(iam_path_check(path));
- if (err == 0) {
- assert_corr(lh != NULL);
- do_corr(schedule());
- err = iam_new_leaf(handle, leaf);
- if (err == 0)
- err = iam_txn_dirty(handle, path,
- path->ip_frame->bh);
- }
+ int err;
+ struct iam_leaf *leaf;
+
+ leaf = &path->ip_leaf;
+ assert_inv(iam_path_check(path));
+ err = iam_txn_add(handle, path, leaf->il_bh);
+ if (err == 0) {
+ do_corr(schedule());
+ if (!iam_leaf_can_add(leaf, k, r)) {
+ struct dynlock_handle *lh = NULL;
+
+ do {
+ assert_corr(lh == NULL);
+ do_corr(schedule());
+ err = split_index_node(handle, path, &lh);
+ if (err == -EAGAIN) {
+ assert_corr(lh == NULL);
+
+ iam_path_fini(path);
+ it->ii_state = IAM_IT_DETACHED;
+
+ do_corr(schedule());
+ err = iam_it_get_exact(it, k);
+ if (err == -ENOENT)
+ err = +1; /* repeat split */
+ else if (err == 0)
+ err = -EEXIST;
+ }
+ } while (err > 0);
+ assert_inv(iam_path_check(path));
+ if (err == 0) {
+ assert_corr(lh != NULL);
+ do_corr(schedule());
+ err = iam_new_leaf(handle, leaf);
+ if (err == 0)
+ err = iam_txn_dirty(handle, path,
+ path->ip_frame->bh);
+ }
- int result;
- struct iam_path *path;
-
- path = &it->ii_path;
-
- assert_corr(it->ii_flags&IAM_IT_WRITE);
- assert_corr(it_state(it) == IAM_IT_ATTACHED ||
- it_state(it) == IAM_IT_SKEWED);
- assert_corr(ergo(it_state(it) == IAM_IT_ATTACHED,
- it_keycmp(it, k) <= 0));
- assert_corr(ergo(it_before(it), it_keycmp(it, k) > 0));
- result = iam_add_rec(h, it, path, k, r);
- if (result == 0)
- it->ii_state = IAM_IT_ATTACHED;
- assert_corr(ergo(result == 0,
- it_state(it) == IAM_IT_ATTACHED &&
- it_keycmp(it, k) == 0));
- return result;
+ int result;
+ struct iam_path *path;
+
+ path = &it->ii_path;
+
+ assert_corr(it->ii_flags&IAM_IT_WRITE);
+ assert_corr(it_state(it) == IAM_IT_ATTACHED ||
+ it_state(it) == IAM_IT_SKEWED);
+ assert_corr(ergo(it_state(it) == IAM_IT_ATTACHED,
+ it_keycmp(it, k) <= 0));
+ assert_corr(ergo(it_before(it), it_keycmp(it, k) > 0));
+ result = iam_add_rec(h, it, path, k, r);
+ if (result == 0)
+ it->ii_state = IAM_IT_ATTACHED;
+ assert_corr(ergo(result == 0,
+ it_state(it) == IAM_IT_ATTACHED &&
+ it_keycmp(it, k) == 0));
+ return result;
- return
- (it->ii_state == IAM_IT_DETACHED ||
- it->ii_state == IAM_IT_ATTACHED ||
- it->ii_state == IAM_IT_SKEWED) &&
- !(it->ii_flags & ~(IAM_IT_MOVE | IAM_IT_WRITE)) &&
- ergo(it->ii_state == IAM_IT_ATTACHED ||
- it->ii_state == IAM_IT_SKEWED,
- iam_path_invariant(&it->ii_path) &&
- equi(it_at_rec(it), it->ii_state == IAM_IT_SKEWED));
+ return
+ (it->ii_state == IAM_IT_DETACHED ||
+ it->ii_state == IAM_IT_ATTACHED ||
+ it->ii_state == IAM_IT_SKEWED) &&
+ !(it->ii_flags & ~(IAM_IT_MOVE | IAM_IT_WRITE)) &&
+ ergo(it->ii_state == IAM_IT_ATTACHED ||
+ it->ii_state == IAM_IT_SKEWED,
+ iam_path_invariant(&it->ii_path) &&
+ equi(it_at_rec(it), it->ii_state == IAM_IT_SKEWED));