Adding upstream version 1.2.0.upstream/1.2.0upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 930 insertions, 0 deletions

diff --git a/lib/exfat_dir.c b/lib/exfat_dir.c
new file mode 100644
index 0000000..499b672
--- /dev/null
+++ b/lib/exfat_dir.c
@@ -0,0 +1,930 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ *   Copyright (C) 2021 LG Electronics.
+ *
+ *   Author(s): Hyunchul Lee <hyc.lee@gmail.com>
+ */
+#include <stdlib.h>
+#include <stdio.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <string.h>
+#include <time.h>
+
+#include "exfat_ondisk.h"
+#include "libexfat.h"
+#include "exfat_fs.h"
+#include "exfat_dir.h"
+
+static struct path_resolve_ctx path_resolve_ctx;
+
+#define fsck_err(parent, inode, fmt, ...)		\
+({							\
+		exfat_resolve_path_parent(&path_resolve_ctx,	\
+			parent, inode);			\
+		exfat_err("ERROR: %s: " fmt,		\
+			path_resolve_ctx.local_path,	\
+			##__VA_ARGS__);			\
+})
+
+static ssize_t write_block(struct exfat_de_iter *iter, unsigned int block)
+{
+	off_t device_offset;
+	struct exfat *exfat = iter->exfat;
+	struct buffer_desc *desc;
+	unsigned int i;
+
+	desc = &iter->buffer_desc[block & 0x01];
+	device_offset = exfat_c2o(exfat, desc->p_clus) + desc->offset;
+
+	for (i = 0; i < iter->read_size / iter->write_size; i++) {
+		if (desc->dirty[i]) {
+			if (exfat_write(exfat->blk_dev->dev_fd,
+					desc->buffer + i * iter->write_size,
+					iter->write_size,
+					device_offset + i * iter->write_size)
+					!= (ssize_t)iter->write_size)
+				return -EIO;
+			desc->dirty[i] = 0;
+		}
+	}
+	return 0;
+}
+
+static int read_ahead_first_blocks(struct exfat_de_iter *iter)
+{
+#ifdef POSIX_FADV_WILLNEED
+	struct exfat *exfat = iter->exfat;
+	clus_t clus_count;
+	unsigned int size;
+
+	clus_count = iter->parent->size / exfat->clus_size;
+
+	if (clus_count > 1) {
+		iter->ra_begin_offset = 0;
+		iter->ra_next_clus = 1;
+		size = exfat->clus_size;
+	} else {
+		iter->ra_begin_offset = 0;
+		iter->ra_next_clus = 0;
+		size = iter->ra_partial_size;
+	}
+	return posix_fadvise(exfat->blk_dev->dev_fd,
+			exfat_c2o(exfat, iter->parent->first_clus), size,
+			POSIX_FADV_WILLNEED);
+#else
+	return -ENOTSUP;
+#endif
+}
+
+/**
+ * read the next fragment in advance, and assume the fragment
+ * which covers @clus is already read.
+ */
+static int read_ahead_next_blocks(struct exfat_de_iter *iter,
+		clus_t clus, unsigned int offset, clus_t p_clus)
+{
+#ifdef POSIX_FADV_WILLNEED
+	struct exfat *exfat = iter->exfat;
+	off_t device_offset;
+	clus_t clus_count, ra_clus, ra_p_clus;
+	unsigned int size;
+	int ret = 0;
+
+	clus_count = iter->parent->size / exfat->clus_size;
+	if (clus + 1 < clus_count) {
+		ra_clus = clus + 1;
+		if (ra_clus == iter->ra_next_clus &&
+				offset >= iter->ra_begin_offset) {
+			ret = exfat_get_inode_next_clus(exfat, iter->parent,
+							p_clus, &ra_p_clus);
+			if (ret)
+				return ret;
+
+			if (ra_p_clus == EXFAT_EOF_CLUSTER)
+				return -EIO;
+
+			device_offset = exfat_c2o(exfat, ra_p_clus);
+			size = ra_clus + 1 < clus_count ?
+				exfat->clus_size : iter->ra_partial_size;
+			ret = posix_fadvise(exfat->blk_dev->dev_fd,
+					device_offset, size,
+					POSIX_FADV_WILLNEED);
+			iter->ra_next_clus = ra_clus + 1;
+			iter->ra_begin_offset = 0;
+		}
+	} else {
+		if (offset >= iter->ra_begin_offset &&
+				offset + iter->ra_partial_size <=
+				exfat->clus_size) {
+			device_offset = exfat_c2o(exfat, p_clus) +
+				offset + iter->ra_partial_size;
+			ret = posix_fadvise(exfat->blk_dev->dev_fd,
+					device_offset, iter->ra_partial_size,
+					POSIX_FADV_WILLNEED);
+			iter->ra_begin_offset =
+				offset + iter->ra_partial_size;
+		}
+	}
+
+	return ret;
+#else
+	return -ENOTSUP;
+#endif
+}
+
+static int read_ahead_next_dir_blocks(struct exfat_de_iter *iter)
+{
+#ifdef POSIX_FADV_WILLNEED
+	struct exfat *exfat = iter->exfat;
+	struct list_head *current;
+	struct exfat_inode *next_inode;
+	off_t offset;
+
+	if (list_empty(&exfat->dir_list))
+		return -EINVAL;
+
+	current = exfat->dir_list.next;
+	if (iter->parent == list_entry(current, struct exfat_inode, list) &&
+			current->next != &exfat->dir_list) {
+		next_inode = list_entry(current->next, struct exfat_inode,
+				list);
+		offset = exfat_c2o(exfat, next_inode->first_clus);
+		return posix_fadvise(exfat->blk_dev->dev_fd, offset,
+				iter->ra_partial_size,
+				POSIX_FADV_WILLNEED);
+	}
+
+	return 0;
+#else
+	return -ENOTSUP;
+#endif
+}
+
+static ssize_t read_block(struct exfat_de_iter *iter, unsigned int block)
+{
+	struct exfat *exfat = iter->exfat;
+	struct buffer_desc *desc, *prev_desc;
+	off_t device_offset;
+	ssize_t ret;
+
+	desc = &iter->buffer_desc[block & 0x01];
+	if (block == 0) {
+		desc->p_clus = iter->parent->first_clus;
+		desc->offset = 0;
+	}
+
+	/* if the buffer already contains dirty dentries, write it */
+	if (write_block(iter, block))
+		return -EIO;
+
+	if (block > 0) {
+		if (block > iter->parent->size / iter->read_size)
+			return EOF;
+
+		prev_desc = &iter->buffer_desc[(block-1) & 0x01];
+		if (prev_desc->offset + 2 * iter->read_size <=
+				exfat->clus_size) {
+			desc->p_clus = prev_desc->p_clus;
+			desc->offset = prev_desc->offset + iter->read_size;
+		} else {
+			ret = exfat_get_inode_next_clus(exfat, iter->parent,
+							prev_desc->p_clus, &desc->p_clus);
+			desc->offset = 0;
+			if (ret)
+				return ret;
+			else if (desc->p_clus == EXFAT_EOF_CLUSTER)
+				return EOF;
+		}
+	}
+
+	device_offset = exfat_c2o(exfat, desc->p_clus) + desc->offset;
+	ret = exfat_read(exfat->blk_dev->dev_fd, desc->buffer,
+			iter->read_size, device_offset);
+	if (ret <= 0)
+		return ret;
+
+	/*
+	 * if a buffer is filled with dentries, read blocks ahead of time,
+	 * otherwise read blocks of the next directory in advance.
+	 */
+	if (desc->buffer[iter->read_size - 32] != EXFAT_LAST)
+		read_ahead_next_blocks(iter,
+				(block * iter->read_size) / exfat->clus_size,
+				(block * iter->read_size) % exfat->clus_size,
+				desc->p_clus);
+	else
+		read_ahead_next_dir_blocks(iter);
+	return ret;
+}
+
+int exfat_de_iter_init(struct exfat_de_iter *iter, struct exfat *exfat,
+		       struct exfat_inode *dir, struct buffer_desc *bd)
+{
+	iter->exfat = exfat;
+	iter->parent = dir;
+	iter->write_size = exfat->sect_size;
+	iter->read_size = exfat->clus_size <= 4*KB ? exfat->clus_size : 4*KB;
+	if (exfat->clus_size <= 32 * KB)
+		iter->ra_partial_size = MAX(4 * KB, exfat->clus_size / 2);
+	else
+		iter->ra_partial_size = exfat->clus_size / 4;
+	iter->ra_partial_size = MIN(iter->ra_partial_size, 8 * KB);
+
+	iter->buffer_desc = bd;
+
+	iter->de_file_offset = 0;
+	iter->next_read_offset = iter->read_size;
+	iter->max_skip_dentries = 0;
+	iter->dot_name_num = 0;
+
+	if (iter->parent->size == 0)
+		return EOF;
+
+	read_ahead_first_blocks(iter);
+	if (read_block(iter, 0) != (ssize_t)iter->read_size) {
+		exfat_err("failed to read directory entries.\n");
+		return -EIO;
+	}
+
+	return 0;
+}
+
+int exfat_de_iter_get(struct exfat_de_iter *iter,
+			int ith, struct exfat_dentry **dentry)
+{
+	off_t next_de_file_offset;
+	ssize_t ret;
+	unsigned int block;
+
+	next_de_file_offset = iter->de_file_offset +
+			ith * sizeof(struct exfat_dentry);
+	block = (unsigned int)(next_de_file_offset / iter->read_size);
+
+	if (next_de_file_offset + sizeof(struct exfat_dentry) >
+		iter->parent->size)
+		return EOF;
+	/* the dentry must be in current, or next block which will be read */
+	if (block > iter->de_file_offset / iter->read_size + 1)
+		return -ERANGE;
+
+	/* read next cluster if needed */
+	if (next_de_file_offset >= iter->next_read_offset) {
+		ret = read_block(iter, block);
+		if (ret != (ssize_t)iter->read_size)
+			return ret;
+		iter->next_read_offset += iter->read_size;
+	}
+
+	if (ith + 1 > iter->max_skip_dentries)
+		iter->max_skip_dentries = ith + 1;
+
+	*dentry = (struct exfat_dentry *)
+			(iter->buffer_desc[block & 0x01].buffer +
+			next_de_file_offset % iter->read_size);
+	return 0;
+}
+
+int exfat_de_iter_get_dirty(struct exfat_de_iter *iter,
+			int ith, struct exfat_dentry **dentry)
+{
+	off_t next_file_offset;
+	unsigned int block;
+	int ret, sect_idx;
+
+	ret = exfat_de_iter_get(iter, ith, dentry);
+	if (!ret) {
+		next_file_offset = iter->de_file_offset +
+				ith * sizeof(struct exfat_dentry);
+		block = (unsigned int)(next_file_offset / iter->read_size);
+		sect_idx = (int)((next_file_offset % iter->read_size) /
+				iter->write_size);
+		iter->buffer_desc[block & 0x01].dirty[sect_idx] = 1;
+	}
+
+	return ret;
+}
+
+int exfat_de_iter_flush(struct exfat_de_iter *iter)
+{
+	if (write_block(iter, 0) || write_block(iter, 1))
+		return -EIO;
+	return 0;
+}
+
+int exfat_de_iter_advance(struct exfat_de_iter *iter, int skip_dentries)
+{
+	if (skip_dentries > iter->max_skip_dentries)
+		return -EINVAL;
+
+	iter->max_skip_dentries = 0;
+	iter->de_file_offset = iter->de_file_offset +
+				skip_dentries * sizeof(struct exfat_dentry);
+	return 0;
+}
+
+off_t exfat_de_iter_device_offset(struct exfat_de_iter *iter)
+{
+	struct buffer_desc *bd;
+	unsigned int block;
+
+	if ((uint64_t)iter->de_file_offset >= iter->parent->size)
+		return EOF;
+
+	block = iter->de_file_offset / iter->read_size;
+	bd = &iter->buffer_desc[block & 0x01];
+	return exfat_c2o(iter->exfat, bd->p_clus) + bd->offset +
+		iter->de_file_offset % iter->read_size;
+}
+
+off_t exfat_de_iter_file_offset(struct exfat_de_iter *iter)
+{
+	return iter->de_file_offset;
+}
+
+/*
+ * try to find the dentry set matched with @filter. this function
+ * doesn't verify the dentry set.
+ *
+ * if found, return 0. if not found, return EOF. otherwise return errno.
+ */
+int exfat_lookup_dentry_set(struct exfat *exfat, struct exfat_inode *parent,
+			    struct exfat_lookup_filter *filter)
+{
+	struct buffer_desc *bd = NULL;
+	struct exfat_dentry *dentry = NULL;
+	off_t free_file_offset = 0, free_dev_offset = 0;
+	struct exfat_de_iter de_iter;
+	int dentry_count;
+	int retval;
+	bool last_is_free = false;
+
+	bd = exfat_alloc_buffer(2, exfat->clus_size, exfat->sect_size);
+	if (!bd)
+		return -ENOMEM;
+
+	retval = exfat_de_iter_init(&de_iter, exfat, parent, bd);
+	if (retval == EOF || retval)
+		goto out;
+
+	filter->out.dentry_set = NULL;
+	while (1) {
+		retval = exfat_de_iter_get(&de_iter, 0, &dentry);
+		if (retval == EOF) {
+			break;
+		} else if (retval) {
+			fsck_err(parent->parent, parent,
+				 "failed to get a dentry. %d\n", retval);
+			goto out;
+		}
+
+		dentry_count = 1;
+		if (dentry->type == filter->in.type) {
+			retval = 0;
+			if (filter->in.filter)
+				retval = filter->in.filter(&de_iter,
+							filter->in.param,
+							&dentry_count);
+
+			if (retval == 0) {
+				struct exfat_dentry *d;
+				int i;
+
+				filter->out.dentry_set = calloc(dentry_count,
+								sizeof(struct exfat_dentry));
+				if (!filter->out.dentry_set) {
+					retval = -ENOMEM;
+					goto out;
+				}
+				for (i = 0; i < dentry_count; i++) {
+					exfat_de_iter_get(&de_iter, i, &d);
+					memcpy(filter->out.dentry_set + i, d,
+					       sizeof(struct exfat_dentry));
+				}
+				filter->out.dentry_count = dentry_count;
+				goto out;
+			} else if (retval < 0) {
+				goto out;
+			}
+			last_is_free = false;
+		} else if ((dentry->type == EXFAT_LAST ||
+			    IS_EXFAT_DELETED(dentry->type))) {
+			if (!last_is_free) {
+				free_file_offset =
+					exfat_de_iter_file_offset(&de_iter);
+				free_dev_offset =
+					exfat_de_iter_device_offset(&de_iter);
+				last_is_free = true;
+			}
+		} else {
+			last_is_free = false;
+		}
+
+		exfat_de_iter_advance(&de_iter, dentry_count);
+	}
+
+out:
+	if (retval == 0) {
+		filter->out.file_offset =
+			exfat_de_iter_file_offset(&de_iter);
+		filter->out.dev_offset =
+			exfat_de_iter_device_offset(&de_iter);
+	} else if (retval == EOF && last_is_free) {
+		filter->out.file_offset = free_file_offset;
+		filter->out.dev_offset = free_dev_offset;
+	} else {
+		filter->out.file_offset = exfat_de_iter_file_offset(&de_iter);
+		filter->out.dev_offset = EOF;
+	}
+	if (bd)
+		exfat_free_buffer(bd, 2);
+	return retval;
+}
+
+static int filter_lookup_file(struct exfat_de_iter *de_iter,
+			      void *param, int *dentry_count)
+{
+	struct exfat_dentry *file_de, *stream_de, *name_de;
+	__le16 *name;
+	int retval, name_len;
+	int i;
+
+	retval = exfat_de_iter_get(de_iter, 0, &file_de);
+	if (retval || file_de->type != EXFAT_FILE)
+		return 1;
+
+	retval = exfat_de_iter_get(de_iter, 1, &stream_de);
+	if (retval || stream_de->type != EXFAT_STREAM)
+		return 1;
+
+	name = (__le16 *)param;
+	name_len = (int)exfat_utf16_len(name, PATH_MAX);
+
+	if (file_de->dentry.file.num_ext <
+		1 + (name_len + ENTRY_NAME_MAX - 1) / ENTRY_NAME_MAX)
+		return 1;
+
+	for (i = 2; i <= file_de->dentry.file.num_ext && name_len > 0; i++) {
+		int len;
+
+		retval = exfat_de_iter_get(de_iter, i, &name_de);
+		if (retval || name_de->type != EXFAT_NAME)
+			return 1;
+
+		len = MIN(name_len, ENTRY_NAME_MAX);
+		if (memcmp(name_de->dentry.name.unicode_0_14,
+			   name, len * 2) != 0)
+			return 1;
+
+		name += len;
+		name_len -= len;
+	}
+
+	*dentry_count = i;
+	return 0;
+}
+
+int exfat_lookup_file(struct exfat *exfat, struct exfat_inode *parent,
+		      const char *name, struct exfat_lookup_filter *filter_out)
+{
+	int retval;
+	__le16 utf16_name[PATH_MAX + 2] = {0, };
+
+	retval = (int)exfat_utf16_enc(name, utf16_name, sizeof(utf16_name));
+	if (retval < 0)
+		return retval;
+
+	filter_out->in.type = EXFAT_FILE;
+	filter_out->in.filter = filter_lookup_file;
+	filter_out->in.param = utf16_name;
+
+	retval = exfat_lookup_dentry_set(exfat, parent, filter_out);
+	if (retval < 0)
+		return retval;
+
+	return 0;
+}
+
+void exfat_calc_dentry_checksum(struct exfat_dentry *dentry,
+				uint16_t *checksum, bool primary)
+{
+	unsigned int i;
+	uint8_t *bytes;
+
+	bytes = (uint8_t *)dentry;
+
+	*checksum = ((*checksum << 15) | (*checksum >> 1)) + bytes[0];
+	*checksum = ((*checksum << 15) | (*checksum >> 1)) + bytes[1];
+
+	i = primary ? 4 : 2;
+	for (; i < sizeof(*dentry); i++)
+		*checksum = ((*checksum << 15) | (*checksum >> 1)) + bytes[i];
+}
+
+static uint16_t calc_dentry_set_checksum(struct exfat_dentry *dset, int dcount)
+{
+	uint16_t checksum;
+	int i;
+
+	if (dcount < MIN_FILE_DENTRIES)
+		return 0;
+
+	checksum = 0;
+	exfat_calc_dentry_checksum(&dset[0], &checksum, true);
+	for (i = 1; i < dcount; i++)
+		exfat_calc_dentry_checksum(&dset[i], &checksum, false);
+	return checksum;
+}
+
+uint16_t exfat_calc_name_hash(struct exfat *exfat,
+			      __le16 *name, int len)
+{
+	int i;
+	__le16 ch;
+	uint16_t chksum = 0;
+
+	for (i = 0; i < len; i++) {
+		ch = exfat->upcase_table[le16_to_cpu(name[i])];
+		ch = cpu_to_le16(ch);
+
+		chksum = ((chksum << 15) | (chksum >> 1)) + (ch & 0xFF);
+		chksum = ((chksum << 15) | (chksum >> 1)) + (ch >> 8);
+	}
+	return chksum;
+}
+
+static void unix_time_to_exfat_time(time_t unix_time, __u8 *tz, __le16 *date,
+				    __le16 *time, __u8 *time_ms)
+{
+	struct tm tm;
+	__u16 t, d;
+
+	gmtime_r(&unix_time, &tm);
+	d = ((tm.tm_year - 80) << 9) | ((tm.tm_mon + 1) << 5) | tm.tm_mday;
+	t = (tm.tm_hour << 11) | (tm.tm_min << 5) | (tm.tm_sec >> 1);
+
+	*tz = 0x80;
+	*date = cpu_to_le16(d);
+	*time = cpu_to_le16(t);
+	if (time_ms)
+		*time_ms = (tm.tm_sec & 1) * 100;
+}
+
+int exfat_build_file_dentry_set(struct exfat *exfat, const char *name,
+				unsigned short attr, struct exfat_dentry **dentry_set,
+				int *dentry_count)
+{
+	struct exfat_dentry *dset;
+	__le16 utf16_name[PATH_MAX + 2];
+	int retval;
+	int dcount, name_len, i;
+	__le16 e_date, e_time;
+	__u8 tz, e_time_ms;
+
+	memset(utf16_name, 0, sizeof(utf16_name));
+	retval = exfat_utf16_enc(name, utf16_name, sizeof(utf16_name));
+	if (retval < 0)
+		return retval;
+
+	name_len = retval / 2;
+	dcount = 2 + DIV_ROUND_UP(name_len, ENTRY_NAME_MAX);
+	dset = calloc(1, dcount * DENTRY_SIZE);
+	if (!dset)
+		return -ENOMEM;
+
+	dset[0].type = EXFAT_FILE;
+	dset[0].dentry.file.num_ext = dcount - 1;
+	dset[0].dentry.file.attr = cpu_to_le16(attr);
+
+	unix_time_to_exfat_time(time(NULL), &tz,
+				&e_date, &e_time, &e_time_ms);
+
+	dset[0].dentry.file.create_date = e_date;
+	dset[0].dentry.file.create_time = e_time;
+	dset[0].dentry.file.create_time_ms = e_time_ms;
+	dset[0].dentry.file.create_tz = tz;
+
+	dset[0].dentry.file.modify_date = e_date;
+	dset[0].dentry.file.modify_time = e_time;
+	dset[0].dentry.file.modify_time_ms = e_time_ms;
+	dset[0].dentry.file.modify_tz = tz;
+
+	dset[0].dentry.file.access_date = e_date;
+	dset[0].dentry.file.access_time = e_time;
+	dset[0].dentry.file.access_tz = tz;
+
+	dset[1].type = EXFAT_STREAM;
+	dset[1].dentry.stream.flags = 0x01;
+	dset[1].dentry.stream.name_len = (__u8)name_len;
+	dset[1].dentry.stream.name_hash =
+		cpu_to_le16(exfat_calc_name_hash(exfat, utf16_name, name_len));
+
+	for (i = 2; i < dcount; i++) {
+		dset[i].type = EXFAT_NAME;
+		memcpy(dset[i].dentry.name.unicode_0_14,
+		       utf16_name + (i - 2) * ENTRY_NAME_MAX,
+		       ENTRY_NAME_MAX * 2);
+	}
+
+	dset[0].dentry.file.checksum =
+		cpu_to_le16(calc_dentry_set_checksum(dset, dcount));
+
+	*dentry_set = dset;
+	*dentry_count = dcount;
+	return 0;
+}
+
+int exfat_update_file_dentry_set(struct exfat *exfat,
+				 struct exfat_dentry *dset, int dcount,
+				 const char *name,
+				 clus_t start_clu, clus_t ccount)
+{
+	int i, name_len;
+	__le16 utf16_name[PATH_MAX + 2];
+
+	if (dset[0].type != EXFAT_FILE || dcount < MIN_FILE_DENTRIES)
+		return -EINVAL;
+
+	if (name) {
+		name_len = (int)exfat_utf16_enc(name,
+						utf16_name, sizeof(utf16_name));
+		if (name_len < 0)
+			return name_len;
+
+		name_len /= 2;
+		if (dcount != 2 + DIV_ROUND_UP(name_len, ENTRY_NAME_MAX))
+			return -EINVAL;
+
+		dset[1].dentry.stream.name_len = (__u8)name_len;
+		dset[1].dentry.stream.name_hash =
+			exfat_calc_name_hash(exfat, utf16_name, name_len);
+
+		for (i = 2; i < dcount; i++) {
+			dset[i].type = EXFAT_NAME;
+			memcpy(dset[i].dentry.name.unicode_0_14,
+			       utf16_name + (i - 2) * ENTRY_NAME_MAX,
+			       ENTRY_NAME_MAX * 2);
+		}
+	}
+
+	dset[1].dentry.stream.valid_size = cpu_to_le64(ccount * exfat->clus_size);
+	dset[1].dentry.stream.size = cpu_to_le64(ccount * exfat->clus_size);
+	if (start_clu)
+		dset[1].dentry.stream.start_clu = cpu_to_le32(start_clu);
+
+	dset[0].dentry.file.checksum =
+		cpu_to_le16(calc_dentry_set_checksum(dset, dcount));
+	return 0;
+}
+
+static int find_free_cluster(struct exfat *exfat,
+			     clus_t start, clus_t *new_clu)
+{
+	clus_t end = le32_to_cpu(exfat->bs->bsx.clu_count) +
+		EXFAT_FIRST_CLUSTER;
+
+	if (!exfat_heap_clus(exfat, start))
+		return -EINVAL;
+
+	while (start < end) {
+		if (exfat_bitmap_find_zero(exfat, exfat->alloc_bitmap,
+					   start, new_clu))
+			break;
+		if (!exfat_bitmap_get(exfat->disk_bitmap, *new_clu))
+			return 0;
+		start = *new_clu + 1;
+	}
+
+	end = start;
+	start = EXFAT_FIRST_CLUSTER;
+	while (start < end) {
+		if (exfat_bitmap_find_zero(exfat, exfat->alloc_bitmap,
+					   start, new_clu))
+			goto out_nospc;
+		if (!exfat_bitmap_get(exfat->disk_bitmap, *new_clu))
+			return 0;
+		start = *new_clu + 1;
+	}
+
+out_nospc:
+	*new_clu = EXFAT_EOF_CLUSTER;
+	return -ENOSPC;
+}
+
+static int exfat_map_cluster(struct exfat *exfat, struct exfat_inode *inode,
+			     off_t file_off, clus_t *mapped_clu)
+{
+	clus_t clu, next, count, last_count;
+
+	if (!exfat_heap_clus(exfat, inode->first_clus))
+		return -EINVAL;
+
+	clu = inode->first_clus;
+	next = EXFAT_EOF_CLUSTER;
+	count = 1;
+	if (file_off == EOF)
+		last_count = DIV_ROUND_UP(inode->size, exfat->clus_size);
+	else
+		last_count = file_off / exfat->clus_size + 1;
+
+	while (true) {
+		if (count * exfat->clus_size > inode->size)
+			return -EINVAL;
+
+		if (count == last_count) {
+			*mapped_clu = clu;
+			return 0;
+		}
+
+		if (exfat_get_inode_next_clus(exfat, inode, clu, &next))
+			return -EINVAL;
+
+		if (!exfat_heap_clus(exfat, clu))
+			return -EINVAL;
+
+		clu = next;
+		count++;
+	}
+	return -EINVAL;
+}
+
+static int exfat_write_dentry_set(struct exfat *exfat,
+				  struct exfat_dentry *dset, int dcount,
+				  off_t dev_off, off_t *next_dev_off)
+{
+	clus_t clus;
+	unsigned int clus_off, dent_len, first_half_len, sec_half_len;
+	off_t first_half_off, sec_half_off = 0;
+
+	if (exfat_o2c(exfat, dev_off, &clus, &clus_off))
+		return -ERANGE;
+
+	dent_len = dcount * DENTRY_SIZE;
+	first_half_len = MIN(dent_len, exfat->clus_size - clus_off);
+	sec_half_len = dent_len - first_half_len;
+
+	first_half_off = dev_off;
+	if (sec_half_len) {
+		clus_t next_clus;
+
+		if (exfat_get_next_clus(exfat, clus, &next_clus))
+			return -EIO;
+		if (!exfat_heap_clus(exfat, next_clus))
+			return -EINVAL;
+		sec_half_off = exfat_c2o(exfat, next_clus);
+	}
+
+	if (exfat_write(exfat->blk_dev->dev_fd, dset, first_half_len,
+			first_half_off) != (ssize_t)first_half_len)
+		return -EIO;
+
+	if (sec_half_len) {
+		dset = (struct exfat_dentry *)((char *)dset + first_half_len);
+		if (exfat_write(exfat->blk_dev->dev_fd, dset, sec_half_len,
+				sec_half_off) != (ssize_t)sec_half_len)
+			return -EIO;
+	}
+
+	if (next_dev_off) {
+		if (sec_half_len)
+			*next_dev_off = sec_half_off + sec_half_len;
+		else
+			*next_dev_off = first_half_off + first_half_len;
+	}
+	return 0;
+}
+
+static int exfat_alloc_cluster(struct exfat *exfat, struct exfat_inode *inode,
+			       clus_t *new_clu)
+{
+	clus_t last_clu;
+	int err;
+	bool need_dset = inode != exfat->root;
+
+	if ((need_dset && !inode->dentry_set) || inode->is_contiguous)
+		return -EINVAL;
+
+	err = find_free_cluster(exfat, exfat->start_clu, new_clu);
+	if (err) {
+		exfat->start_clu = EXFAT_FIRST_CLUSTER;
+		exfat_err("failed to find an free cluster\n");
+		return -ENOSPC;
+	}
+	exfat->start_clu = *new_clu;
+
+	if (exfat_set_fat(exfat, *new_clu, EXFAT_EOF_CLUSTER))
+		return -EIO;
+
+	/* zero out the new cluster */
+	if (exfat_write(exfat->blk_dev->dev_fd, exfat->zero_cluster,
+			exfat->clus_size, exfat_c2o(exfat, *new_clu)) !=
+	    (ssize_t)exfat->clus_size) {
+		exfat_err("failed to fill new cluster with zeroes\n");
+		return -EIO;
+	}
+
+	if (inode->size) {
+		err = exfat_map_cluster(exfat, inode, EOF, &last_clu);
+		if (err) {
+			exfat_err("failed to get the last cluster\n");
+			return err;
+		}
+
+		if (exfat_set_fat(exfat, last_clu, *new_clu))
+			return -EIO;
+
+		if (need_dset) {
+			err = exfat_update_file_dentry_set(exfat,
+							   inode->dentry_set,
+							   inode->dentry_count,
+							   NULL, 0,
+							   DIV_ROUND_UP(inode->size,
+									exfat->clus_size) + 1);
+			if (err)
+				return -EINVAL;
+		}
+	} else {
+		if (need_dset) {
+			err = exfat_update_file_dentry_set(exfat,
+							   inode->dentry_set,
+							   inode->dentry_count,
+							   NULL, *new_clu, 1);
+			if (err)
+				return -EINVAL;
+		}
+	}
+
+	if (need_dset && exfat_write_dentry_set(exfat, inode->dentry_set,
+						inode->dentry_count,
+						inode->dev_offset, NULL))
+		return -EIO;
+
+	exfat_bitmap_set(exfat->alloc_bitmap, *new_clu);
+	if (inode->size == 0)
+		inode->first_clus = *new_clu;
+	inode->size += exfat->clus_size;
+	return 0;
+}
+
+int exfat_add_dentry_set(struct exfat *exfat, struct exfat_dentry_loc *loc,
+			 struct exfat_dentry *dset, int dcount,
+			 bool need_next_loc)
+{
+	struct exfat_inode *parent = loc->parent;
+	off_t dev_off, next_dev_off;
+
+	if (parent->is_contiguous ||
+	    (uint64_t)loc->file_offset > parent->size ||
+	    (unsigned int)dcount * DENTRY_SIZE > exfat->clus_size)
+		return -EINVAL;
+
+	dev_off = loc->dev_offset;
+	if ((uint64_t)loc->file_offset + dcount * DENTRY_SIZE > parent->size) {
+		clus_t new_clus;
+
+		if (exfat_alloc_cluster(exfat, parent, &new_clus))
+			return -EIO;
+		if ((uint64_t)loc->file_offset == parent->size - exfat->clus_size)
+			dev_off = exfat_c2o(exfat, new_clus);
+	}
+
+	if (exfat_write_dentry_set(exfat, dset, dcount, dev_off, &next_dev_off))
+		return -EIO;
+
+	if (need_next_loc) {
+		loc->file_offset += dcount * DENTRY_SIZE;
+		loc->dev_offset = next_dev_off;
+	}
+	return 0;
+}
+
+int exfat_create_file(struct exfat *exfat, struct exfat_inode *parent,
+		      const char *name, unsigned short attr)
+{
+	struct exfat_dentry *dset;
+	int err, dcount;
+	struct exfat_lookup_filter filter;
+	struct exfat_dentry_loc loc;
+
+	err = exfat_lookup_file(exfat, parent, name, &filter);
+	if (err == 0) {
+		dset = filter.out.dentry_set;
+		dcount = filter.out.dentry_count;
+		if ((le16_to_cpu(dset->dentry.file.attr) & attr) != attr)
+			err = -EEXIST;
+		goto out;
+	}
+
+	err = exfat_build_file_dentry_set(exfat, name, attr,
+					  &dset, &dcount);
+	if (err)
+		return err;
+
+	loc.parent = parent;
+	loc.file_offset = filter.out.file_offset;
+	loc.dev_offset = filter.out.dev_offset;
+	err = exfat_add_dentry_set(exfat, &loc, dset, dcount, false);
+out:
+	free(dset);
+	return err;
+}