-
- struct iam_entry *entries; /* old block contents */
- struct iam_entry *entries2; /* new block contents */
- struct iam_frame *frame, *safe;
- struct buffer_head *bh_new[DX_MAX_TREE_HEIGHT] = {0};
- 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) {
- do_corr(schedule());
- lock[i] = iam_lock_htree(dir, frame->curidx, DLT_WRITE);
- if (lock[i] == NULL) {
- err = -ENOMEM;
- goto cleanup;
- }
- }
-
- /*
- * 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) {
- bh_new[i] = ldiskfs_append (handle, dir, &newblock[i], &err);
- do_corr(schedule());
- if (!bh_new[i] ||
- descr->id_ops->id_node_init(path->ip_container,
- bh_new[i], 0) != 0)
- goto cleanup;
- new_lock[i] = iam_lock_htree(dir, newblock[i], DLT_WRITE);
- if (new_lock[i] == NULL) {
- err = -ENOMEM;
- goto cleanup;
- }
- 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" */
- err = ldiskfs_journal_get_write_access(handle, bh2);
- 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));
- err = ldiskfs_journal_dirty_metadata(handle, bh2);
- if (err)
- goto journal_error;
- do_corr(schedule());
- err = ldiskfs_journal_dirty_metadata(handle, parent->bh);
- if (err)
- goto journal_error;
- }
- do_corr(schedule());
- err = ldiskfs_journal_dirty_metadata(handle, bh);
- if (err)
- goto journal_error;
- }
- /*
- * This function was called to make insertion of new leaf
- * possible. Check that it fulfilled its obligations.
- */
- assert_corr(dx_get_count(path->ip_frame->entries) <
- dx_get_limit(path->ip_frame->entries));
- assert_corr(lock[nr_splet] != NULL);
- *lh = lock[nr_splet];
- lock[nr_splet] = NULL;
- if (nr_splet > 0) {
- /*
- * Log ->i_size modification.
- */
- err = ldiskfs_mark_inode_dirty(handle, dir);
- if (err)
- goto journal_error;
- }
- goto cleanup;
+ struct iam_entry *entries; /* old block contents */
+ struct iam_entry *entries2; /* new block contents */
+ struct iam_frame *frame, *safe;
+ struct buffer_head *bh_new[DX_MAX_TREE_HEIGHT] = {NULL};
+ 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) {
+ do_corr(schedule());
+ lock[i] = iam_lock_htree(path->ip_container, frame->curidx,
+ DLT_WRITE);
+ if (lock[i] == NULL) {
+ err = -ENOMEM;
+ goto cleanup;
+ }
+ }
+
+ /*
+ * 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) {
+ bh_new[i] = iam_new_node(handle, path->ip_container,
+ &newblock[i], &err);
+ do_corr(schedule());
+ if (!bh_new[i] ||
+ descr->id_ops->id_node_init(path->ip_container,
+ bh_new[i], 0) != 0)
+ goto cleanup;
+
+ new_lock[i] = iam_lock_htree(path->ip_container, newblock[i],
+ DLT_WRITE);
+ if (new_lock[i] == NULL) {
+ err = -ENOMEM;
+ goto cleanup;
+ }
+ 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" */
+ err = ldiskfs_handle_dirty_metadata(handle, NULL, bh2);
+ 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));
+ err = ldiskfs_handle_dirty_metadata(handle, NULL, bh2);
+ if (err)
+ goto journal_error;
+ do_corr(schedule());
+ err = ldiskfs_handle_dirty_metadata(handle, NULL,
+ parent->bh);
+ if (err)
+ goto journal_error;
+ }
+ do_corr(schedule());
+ err = ldiskfs_handle_dirty_metadata(handle, NULL, bh);
+ if (err)
+ goto journal_error;
+ }
+ /*
+ * This function was called to make insertion of new leaf
+ * possible. Check that it fulfilled its obligations.
+ */
+ assert_corr(dx_get_count(path->ip_frame->entries) <
+ dx_get_limit(path->ip_frame->entries));
+ assert_corr(lock[nr_splet] != NULL);
+ *lh = lock[nr_splet];
+ lock[nr_splet] = NULL;
+ if (nr_splet > 0) {
+ /*
+ * Log ->i_size modification.
+ */
+ err = ldiskfs_mark_inode_dirty(handle, dir);
+ if (err)
+ goto journal_error;
+ }
+ goto cleanup;