+static int splitting_at_eof(struct ext2_extent_handle *handle,
+ struct extent_path *path)
+{
+ struct extent_path *ppp = path;
+ dump_path(__func__, handle, path);
+
+ if (handle->level == 0)
+ return 0;
+
+ do {
+ if (ppp->left)
+ return 0;
+ ppp--;
+ } while (ppp >= handle->path);
+
+ return 1;
+}
+
+/*
+ * allocate a new block, move half the current node to it, and update parent
+ *
+ * handle will be left pointing at original record.
+ */
+static errcode_t extent_node_split(ext2_extent_handle_t handle,
+ int expand_allowed)
+{
+ errcode_t retval = 0;
+ blk64_t new_node_pblk;
+ blk64_t new_node_start;
+ blk64_t orig_lblk;
+ blk64_t goal_blk = 0;
+ int orig_height;
+ char *block_buf = NULL;
+ struct ext2fs_extent extent;
+ struct extent_path *path, *newpath = 0;
+ struct ext3_extent_header *eh, *neweh;
+ int tocopy;
+ int new_root = 0;
+ struct ext2_extent_info info;
+ int no_balance;
+
+ /* basic sanity */
+ EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
+
+ if (!(handle->fs->flags & EXT2_FLAG_RW))
+ return EXT2_ET_RO_FILSYS;
+
+ if (!handle->path)
+ return EXT2_ET_NO_CURRENT_NODE;
+
+#ifdef DEBUG
+ printf("splitting node at level %d\n", handle->level);
+#endif
+ retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
+ if (retval)
+ goto done;
+
+ retval = ext2fs_extent_get_info(handle, &info);
+ if (retval)
+ goto done;
+
+ /* save the position we were originally splitting... */
+ orig_height = info.max_depth - info.curr_level;
+ orig_lblk = extent.e_lblk;
+
+ /* Try to put the index block before the first extent */
+ path = handle->path + handle->level;
+ eh = (struct ext3_extent_header *) path->buf;
+ if (handle->level == handle->max_depth) {
+ struct ext3_extent *ex;
+
+ ex = EXT_FIRST_EXTENT(eh);
+ goal_blk = ext2fs_le32_to_cpu(ex->ee_start) +
+ ((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32);
+ } else {
+ struct ext3_extent_idx *ix;
+
+ ix = EXT_FIRST_INDEX(eh);
+ goal_blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
+ ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
+ }
+ goal_blk -= EXT2FS_CLUSTER_RATIO(handle->fs);
+ goal_blk &= ~EXT2FS_CLUSTER_MASK(handle->fs);
+
+ /* Is there room in the parent for a new entry? */
+ if (handle->level &&
+ (handle->path[handle->level - 1].entries >=
+ handle->path[handle->level - 1].max_entries)) {
+
+#ifdef DEBUG
+ printf("parent level %d full; splitting it too\n",
+ handle->level - 1);
+#endif
+ /* split the parent */
+ retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
+ if (retval)
+ goto done;
+
+ retval = extent_node_split(handle, expand_allowed);
+ if (retval)
+ goto done;
+
+ /* get handle back to our original split position */
+ retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk);
+ if (retval)
+ goto done;
+ }
+
+ /* At this point, parent should have room for this split */
+ path = handle->path + handle->level;
+ if (!path->curr)
+ return EXT2_ET_NO_CURRENT_NODE;
+
+ /*
+ * Normally, we try to split a full node in half. This doesn't turn
+ * out so well if we're tacking extents on the end of the file because
+ * then we're stuck with a tree of half-full extent blocks. This of
+ * course doesn't apply to the root level.
+ */
+ no_balance = expand_allowed ? splitting_at_eof(handle, path) : 0;
+
+ /* extent header of the current node we'll split */
+ eh = (struct ext3_extent_header *)path->buf;
+
+ /* splitting root level means moving them all out */
+ if (handle->level == 0) {
+ new_root = 1;
+ tocopy = ext2fs_le16_to_cpu(eh->eh_entries);
+ retval = ext2fs_get_memzero((handle->max_paths + 1) *
+ sizeof(struct extent_path),
+ &newpath);
+ if (retval)
+ goto done;
+ } else {
+ if (no_balance)
+ tocopy = 1;
+ else
+ tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2;
+ }
+
+#ifdef DEBUG
+ printf("will copy out %d of %d entries at level %d\n",
+ tocopy, ext2fs_le16_to_cpu(eh->eh_entries),
+ handle->level);
+#endif
+
+ if (!tocopy && !no_balance) {
+#ifdef DEBUG
+ printf("Nothing to copy to new block!\n");
+#endif
+ retval = EXT2_ET_CANT_SPLIT_EXTENT;
+ goto done;
+ }
+
+ /* first we need a new block, or can do nothing. */
+ block_buf = malloc(handle->fs->blocksize);
+ if (!block_buf) {
+ retval = ENOMEM;
+ goto done;
+ }
+
+ if (!goal_blk)
+ goal_blk = ext2fs_find_inode_goal(handle->fs, handle->ino,
+ handle->inode, 0);
+ retval = ext2fs_alloc_block2(handle->fs, goal_blk, block_buf,
+ &new_node_pblk);
+ if (retval)
+ goto done;
+
+#ifdef DEBUG
+ printf("will copy to new node at block %lu\n",
+ (unsigned long) new_node_pblk);
+#endif
+
+ /* Copy data into new block buffer */
+ /* First the header for the new block... */
+ neweh = (struct ext3_extent_header *) block_buf;
+ memcpy(neweh, eh, sizeof(struct ext3_extent_header));
+ neweh->eh_entries = ext2fs_cpu_to_le16(tocopy);
+ neweh->eh_max = ext2fs_cpu_to_le16((handle->fs->blocksize -
+ sizeof(struct ext3_extent_header)) /
+ sizeof(struct ext3_extent));
+
+ /* then the entries for the new block... */
+ memcpy(EXT_FIRST_INDEX(neweh),
+ EXT_FIRST_INDEX(eh) +
+ (ext2fs_le16_to_cpu(eh->eh_entries) - tocopy),
+ sizeof(struct ext3_extent_idx) * tocopy);
+
+ new_node_start = ext2fs_le32_to_cpu(EXT_FIRST_INDEX(neweh)->ei_block);
+
+ /* then update the checksum */
+ retval = ext2fs_extent_block_csum_set(handle->fs, handle->ino, neweh);
+ if (retval)
+ goto done;
+
+ /* ...and write the new node block out to disk. */
+ retval = io_channel_write_blk64(handle->fs->io, new_node_pblk, 1,
+ block_buf);
+
+ if (retval)
+ goto done;
+
+ /* OK! we've created the new node; now adjust the tree */
+
+ /* current path now has fewer active entries, we copied some out */
+ if (handle->level == 0) {
+ memcpy(newpath, path,
+ sizeof(struct extent_path) * handle->max_paths);
+ handle->path = newpath;
+ newpath = path;
+ path = handle->path;
+ path->entries = 1;
+ path->left = path->max_entries - 1;
+ handle->max_depth++;
+ handle->max_paths++;
+ eh->eh_depth = ext2fs_cpu_to_le16(handle->max_depth);
+ } else {
+ path->entries -= tocopy;
+ path->left -= tocopy;
+ }
+
+ eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
+ /* this writes out the node, incl. the modified header */
+ retval = update_path(handle);
+ if (retval)
+ goto done;
+
+ /* now go up and insert/replace index for new node we created */
+ if (new_root) {
+ retval = ext2fs_extent_get(handle, EXT2_EXTENT_FIRST_SIB, &extent);
+ if (retval)
+ goto done;
+
+ extent.e_lblk = new_node_start;
+ extent.e_pblk = new_node_pblk;
+ extent.e_len = handle->path[0].end_blk - extent.e_lblk;
+ retval = ext2fs_extent_replace(handle, 0, &extent);
+ if (retval)
+ goto done;
+ } else {
+ __u32 new_node_length;
+
+ retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
+ /* will insert after this one; it's length is shorter now */
+ new_node_length = new_node_start - extent.e_lblk;
+ extent.e_len -= new_node_length;
+ retval = ext2fs_extent_replace(handle, 0, &extent);
+ if (retval)
+ goto done;
+
+ /* now set up the new extent and insert it */
+ extent.e_lblk = new_node_start;
+ extent.e_pblk = new_node_pblk;
+ extent.e_len = new_node_length;
+ retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER, &extent);
+ if (retval)
+ goto done;
+ }
+
+ /* get handle back to our original position */
+ retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk);
+ if (retval)
+ goto done;
+
+ /* new node hooked in, so update inode block count (do this here?) */
+ ext2fs_iblk_add_blocks(handle->fs, handle->inode, 1);
+ retval = ext2fs_write_inode(handle->fs, handle->ino,
+ handle->inode);
+ if (retval)
+ goto done;
+
+done:
+ if (newpath)
+ ext2fs_free_mem(&newpath);
+ free(block_buf);
+
+ return retval;
+}
+
+errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
+{
+ return extent_node_split(handle, 0);
+}
+