lib/exfat_dir.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  *   Copyright (C) 2021 LG Electronics.
   4  *
   5  *   Author(s): Hyunchul Lee <hyc.lee@gmail.com>
   6  */
   7 #include <stdlib.h>
   8 #include <stdio.h>
   9 #include <errno.h>
  10 #include <fcntl.h>
  11 #include <string.h>
  12 #include <time.h>
  13
  14 #include "exfat_ondisk.h"
  15 #include "libexfat.h"
  16 #include "exfat_fs.h"
  17 #include "exfat_dir.h"
  18
  19 static struct path_resolve_ctx path_resolve_ctx;
  20
  21 #define fsck_err(parent, inode, fmt, ...)               \
  22 ({                                                      \
  23                 exfat_resolve_path_parent(&path_resolve_ctx,    \
  24                         parent, inode);                 \
  25                 exfat_err("ERROR: %s: " fmt,            \
  26                         path_resolve_ctx.local_path,    \
  27                         ##__VA_ARGS__);                 \
  28 })
  29
  30 static ssize_t write_block(struct exfat_de_iter *iter, unsigned int block)
  31 {
  32         off_t device_offset;
  33         struct exfat *exfat = iter->exfat;
  34         struct buffer_desc *desc;
  35         unsigned int i;
  36
  37         desc = &iter->buffer_desc[block & 0x01];
  38         device_offset = exfat_c2o(exfat, desc->p_clus) + desc->offset;
  39
  40         for (i = 0; i < iter->read_size / iter->write_size; i++) {
  41                 if (desc->dirty[i]) {
  42                         if (exfat_write(exfat->blk_dev->dev_fd,
  43                                         desc->buffer + i * iter->write_size,
  44                                         iter->write_size,
  45                                         device_offset + i * iter->write_size)
  46                                         != (ssize_t)iter->write_size)
  47                                 return -EIO;
  48                         desc->dirty[i] = 0;
  49                 }
  50         }
  51         return 0;
  52 }
  53
  54 static int read_ahead_first_blocks(struct exfat_de_iter *iter)
  55 {
  56 #ifdef POSIX_FADV_WILLNEED
  57         struct exfat *exfat = iter->exfat;
  58         clus_t clus_count;
  59         unsigned int size;
  60
  61         clus_count = iter->parent->size / exfat->clus_size;
  62
  63         if (clus_count > 1) {
  64                 iter->ra_begin_offset = 0;
  65                 iter->ra_next_clus = 1;
  66                 size = exfat->clus_size;
  67         } else {
  68                 iter->ra_begin_offset = 0;
  69                 iter->ra_next_clus = 0;
  70                 size = iter->ra_partial_size;
  71         }
  72         return posix_fadvise(exfat->blk_dev->dev_fd,
  73                         exfat_c2o(exfat, iter->parent->first_clus), size,
  74                         POSIX_FADV_WILLNEED);
  75 #else
  76         return -ENOTSUP;
  77 #endif
  78 }
  79
  80 /**
  81  * read the next fragment in advance, and assume the fragment
  82  * which covers @clus is already read.
  83  */
  84 static int read_ahead_next_blocks(struct exfat_de_iter *iter,
  85                 clus_t clus, unsigned int offset, clus_t p_clus)
  86 {
  87 #ifdef POSIX_FADV_WILLNEED
  88         struct exfat *exfat = iter->exfat;
  89         off_t device_offset;
  90         clus_t clus_count, ra_clus, ra_p_clus;
  91         unsigned int size;
  92         int ret = 0;
  93
  94         clus_count = iter->parent->size / exfat->clus_size;
  95         if (clus + 1 < clus_count) {
  96                 ra_clus = clus + 1;
  97                 if (ra_clus == iter->ra_next_clus &&
  98                                 offset >= iter->ra_begin_offset) {
  99                         ret = exfat_get_inode_next_clus(exfat, iter->parent,
 100                                                         p_clus, &ra_p_clus);
 101                         if (ret)
 102                                 return ret;
 103
 104                         if (ra_p_clus == EXFAT_EOF_CLUSTER)
 105                                 return -EIO;
 106
 107                         device_offset = exfat_c2o(exfat, ra_p_clus);
 108                         size = ra_clus + 1 < clus_count ?
 109                                 exfat->clus_size : iter->ra_partial_size;
 110                         ret = posix_fadvise(exfat->blk_dev->dev_fd,
 111                                         device_offset, size,
 112                                         POSIX_FADV_WILLNEED);
 113                         iter->ra_next_clus = ra_clus + 1;
 114                         iter->ra_begin_offset = 0;
 115                 }
 116         } else {
 117                 if (offset >= iter->ra_begin_offset &&
 118                                 offset + iter->ra_partial_size <=
 119                                 exfat->clus_size) {
 120                         device_offset = exfat_c2o(exfat, p_clus) +
 121                                 offset + iter->ra_partial_size;
 122                         ret = posix_fadvise(exfat->blk_dev->dev_fd,
 123                                         device_offset, iter->ra_partial_size,
 124                                         POSIX_FADV_WILLNEED);
 125                         iter->ra_begin_offset =
 126                                 offset + iter->ra_partial_size;
 127                 }
 128         }
 129
 130         return ret;
 131 #else
 132         return -ENOTSUP;
 133 #endif
 134 }
 135
 136 static int read_ahead_next_dir_blocks(struct exfat_de_iter *iter)
 137 {
 138 #ifdef POSIX_FADV_WILLNEED
 139         struct exfat *exfat = iter->exfat;
 140         struct list_head *current;
 141         struct exfat_inode *next_inode;
 142         off_t offset;
 143
 144         if (list_empty(&exfat->dir_list))
 145                 return -EINVAL;
 146
 147         current = exfat->dir_list.next;
 148         if (iter->parent == list_entry(current, struct exfat_inode, list) &&
 149                         current->next != &exfat->dir_list) {
 150                 next_inode = list_entry(current->next, struct exfat_inode,
 151                                 list);
 152                 offset = exfat_c2o(exfat, next_inode->first_clus);
 153                 return posix_fadvise(exfat->blk_dev->dev_fd, offset,
 154                                 iter->ra_partial_size,
 155                                 POSIX_FADV_WILLNEED);
 156         }
 157
 158         return 0;
 159 #else
 160         return -ENOTSUP;
 161 #endif
 162 }
 163
 164 static ssize_t read_block(struct exfat_de_iter *iter, unsigned int block)
 165 {
 166         struct exfat *exfat = iter->exfat;
 167         struct buffer_desc *desc, *prev_desc;
 168         off_t device_offset;
 169         ssize_t ret;
 170
 171         desc = &iter->buffer_desc[block & 0x01];
 172         if (block == 0) {
 173                 desc->p_clus = iter->parent->first_clus;
 174                 desc->offset = 0;
 175         }
 176
 177         /* if the buffer already contains dirty dentries, write it */
 178         if (write_block(iter, block))
 179                 return -EIO;
 180
 181         if (block > 0) {
 182                 if (block > iter->parent->size / iter->read_size)
 183                         return EOF;
 184
 185                 prev_desc = &iter->buffer_desc[(block-1) & 0x01];
 186                 if (prev_desc->offset + 2 * iter->read_size <=
 187                                 exfat->clus_size) {
 188                         desc->p_clus = prev_desc->p_clus;
 189                         desc->offset = prev_desc->offset + iter->read_size;
 190                 } else {
 191                         ret = exfat_get_inode_next_clus(exfat, iter->parent,
 192                                                         prev_desc->p_clus, &desc->p_clus);
 193                         desc->offset = 0;
 194                         if (ret)
 195                                 return ret;
 196                         else if (desc->p_clus == EXFAT_EOF_CLUSTER)
 197                                 return EOF;
 198                 }
 199         }
 200
 201         device_offset = exfat_c2o(exfat, desc->p_clus) + desc->offset;
 202         ret = exfat_read(exfat->blk_dev->dev_fd, desc->buffer,
 203                         iter->read_size, device_offset);
 204         if (ret <= 0)
 205                 return ret;
 206
 207         /*
 208          * if a buffer is filled with dentries, read blocks ahead of time,
 209          * otherwise read blocks of the next directory in advance.
 210          */
 211         if (desc->buffer[iter->read_size - 32] != EXFAT_LAST)
 212                 read_ahead_next_blocks(iter,
 213                                 (block * iter->read_size) / exfat->clus_size,
 214                                 (block * iter->read_size) % exfat->clus_size,
 215                                 desc->p_clus);
 216         else
 217                 read_ahead_next_dir_blocks(iter);
 218         return ret;
 219 }
 220
 221 int exfat_de_iter_init(struct exfat_de_iter *iter, struct exfat *exfat,
 222                        struct exfat_inode *dir, struct buffer_desc *bd)
 223 {
 224         iter->exfat = exfat;
 225         iter->parent = dir;
 226         iter->write_size = exfat->sect_size;
 227         iter->read_size = exfat->clus_size <= 4*KB ? exfat->clus_size : 4*KB;
 228         if (exfat->clus_size <= 32 * KB)
 229                 iter->ra_partial_size = MAX(4 * KB, exfat->clus_size / 2);
 230         else
 231                 iter->ra_partial_size = exfat->clus_size / 4;
 232         iter->ra_partial_size = MIN(iter->ra_partial_size, 8 * KB);
 233
 234         iter->buffer_desc = bd;
 235
 236         iter->de_file_offset = 0;
 237         iter->next_read_offset = iter->read_size;
 238         iter->max_skip_dentries = 0;
 239         iter->dot_name_num = 0;
 240
 241         if (iter->parent->size == 0)
 242                 return EOF;
 243
 244         read_ahead_first_blocks(iter);
 245         if (read_block(iter, 0) != (ssize_t)iter->read_size) {
 246                 exfat_err("failed to read directory entries.\n");
 247                 return -EIO;
 248         }
 249
 250         return 0;
 251 }
 252
 253 int exfat_de_iter_get(struct exfat_de_iter *iter,
 254                         int ith, struct exfat_dentry **dentry)
 255 {
 256         off_t next_de_file_offset;
 257         ssize_t ret;
 258         unsigned int block;
 259
 260         next_de_file_offset = iter->de_file_offset +
 261                         ith * sizeof(struct exfat_dentry);
 262         block = (unsigned int)(next_de_file_offset / iter->read_size);
 263
 264         if (next_de_file_offset + sizeof(struct exfat_dentry) >
 265                 iter->parent->size)
 266                 return EOF;
 267         /* the dentry must be in current, or next block which will be read */
 268         if (block > iter->de_file_offset / iter->read_size + 1)
 269                 return -ERANGE;
 270
 271         /* read next cluster if needed */
 272         if (next_de_file_offset >= iter->next_read_offset) {
 273                 ret = read_block(iter, block);
 274                 if (ret != (ssize_t)iter->read_size)
 275                         return ret;
 276                 iter->next_read_offset += iter->read_size;
 277         }
 278
 279         if (ith + 1 > iter->max_skip_dentries)
 280                 iter->max_skip_dentries = ith + 1;
 281
 282         *dentry = (struct exfat_dentry *)
 283                         (iter->buffer_desc[block & 0x01].buffer +
 284                         next_de_file_offset % iter->read_size);
 285         return 0;
 286 }
 287
 288 int exfat_de_iter_get_dirty(struct exfat_de_iter *iter,
 289                         int ith, struct exfat_dentry **dentry)
 290 {
 291         off_t next_file_offset;
 292         unsigned int block;
 293         int ret, sect_idx;
 294
 295         ret = exfat_de_iter_get(iter, ith, dentry);
 296         if (!ret) {
 297                 next_file_offset = iter->de_file_offset +
 298                                 ith * sizeof(struct exfat_dentry);
 299                 block = (unsigned int)(next_file_offset / iter->read_size);
 300                 sect_idx = (int)((next_file_offset % iter->read_size) /
 301                                 iter->write_size);
 302                 iter->buffer_desc[block & 0x01].dirty[sect_idx] = 1;
 303         }
 304
 305         return ret;
 306 }
 307
 308 int exfat_de_iter_flush(struct exfat_de_iter *iter)
 309 {
 310         if (write_block(iter, 0) || write_block(iter, 1))
 311                 return -EIO;
 312         return 0;
 313 }
 314
 315 int exfat_de_iter_advance(struct exfat_de_iter *iter, int skip_dentries)
 316 {
 317         if (skip_dentries > iter->max_skip_dentries)
 318                 return -EINVAL;
 319
 320         iter->max_skip_dentries = 0;
 321         iter->de_file_offset = iter->de_file_offset +
 322                                 skip_dentries * sizeof(struct exfat_dentry);
 323         return 0;
 324 }
 325
 326 off_t exfat_de_iter_device_offset(struct exfat_de_iter *iter)
 327 {
 328         struct buffer_desc *bd;
 329         unsigned int block;
 330
 331         if ((uint64_t)iter->de_file_offset >= iter->parent->size)
 332                 return EOF;
 333
 334         block = iter->de_file_offset / iter->read_size;
 335         bd = &iter->buffer_desc[block & 0x01];
 336         return exfat_c2o(iter->exfat, bd->p_clus) + bd->offset +
 337                 iter->de_file_offset % iter->read_size;
 338 }
 339
 340 off_t exfat_de_iter_file_offset(struct exfat_de_iter *iter)
 341 {
 342         return iter->de_file_offset;
 343 }
 344
 345 /*
 346  * try to find the dentry set matched with @filter. this function
 347  * doesn't verify the dentry set.
 348  *
 349  * if found, return 0. if not found, return EOF. otherwise return errno.
 350  */
 351 int exfat_lookup_dentry_set(struct exfat *exfat, struct exfat_inode *parent,
 352                             struct exfat_lookup_filter *filter)
 353 {
 354         struct buffer_desc *bd = NULL;
 355         struct exfat_dentry *dentry = NULL;
 356         off_t free_file_offset = 0, free_dev_offset = 0;
 357         struct exfat_de_iter de_iter;
 358         int dentry_count;
 359         int retval;
 360         bool last_is_free = false;
 361
 362         bd = exfat_alloc_buffer(2, exfat->clus_size, exfat->sect_size);
 363         if (!bd)
 364                 return -ENOMEM;
 365
 366         retval = exfat_de_iter_init(&de_iter, exfat, parent, bd);
 367         if (retval == EOF || retval)
 368                 goto out;
 369
 370         filter->out.dentry_set = NULL;
 371         while (1) {
 372                 retval = exfat_de_iter_get(&de_iter, 0, &dentry);
 373                 if (retval == EOF) {
 374                         break;
 375                 } else if (retval) {
 376                         fsck_err(parent->parent, parent,
 377                                  "failed to get a dentry. %d\n", retval);
 378                         goto out;
 379                 }
 380
 381                 dentry_count = 1;
 382                 if (dentry->type == filter->in.type) {
 383                         retval = 0;
 384                         if (filter->in.filter)
 385                                 retval = filter->in.filter(&de_iter,
 386                                                         filter->in.param,
 387                                                         &dentry_count);
 388
 389                         if (retval == 0) {
 390                                 struct exfat_dentry *d;
 391                                 int i;
 392
 393                                 filter->out.dentry_set = calloc(dentry_count,
 394                                                                 sizeof(struct exfat_dentry));
 395                                 if (!filter->out.dentry_set) {
 396                                         retval = -ENOMEM;
 397                                         goto out;
 398                                 }
 399                                 for (i = 0; i < dentry_count; i++) {
 400                                         exfat_de_iter_get(&de_iter, i, &d);
 401                                         memcpy(filter->out.dentry_set + i, d,
 402                                                sizeof(struct exfat_dentry));
 403                                 }
 404                                 filter->out.dentry_count = dentry_count;
 405                                 goto out;
 406                         } else if (retval < 0) {
 407                                 goto out;
 408                         }
 409                         last_is_free = false;
 410                 } else if ((dentry->type == EXFAT_LAST ||
 411                             IS_EXFAT_DELETED(dentry->type))) {
 412                         if (!last_is_free) {
 413                                 free_file_offset =
 414                                         exfat_de_iter_file_offset(&de_iter);
 415                                 free_dev_offset =
 416                                         exfat_de_iter_device_offset(&de_iter);
 417                                 last_is_free = true;
 418                         }
 419                 } else {
 420                         last_is_free = false;
 421                 }
 422
 423                 exfat_de_iter_advance(&de_iter, dentry_count);
 424         }
 425
 426 out:
 427         if (retval == 0) {
 428                 filter->out.file_offset =
 429                         exfat_de_iter_file_offset(&de_iter);
 430                 filter->out.dev_offset =
 431                         exfat_de_iter_device_offset(&de_iter);
 432         } else if (retval == EOF && last_is_free) {
 433                 filter->out.file_offset = free_file_offset;
 434                 filter->out.dev_offset = free_dev_offset;
 435         } else {
 436                 filter->out.file_offset = exfat_de_iter_file_offset(&de_iter);
 437                 filter->out.dev_offset = EOF;
 438         }
 439         if (bd)
 440                 exfat_free_buffer(bd, 2);
 441         return retval;
 442 }
 443
 444 static int filter_lookup_file(struct exfat_de_iter *de_iter,
 445                               void *param, int *dentry_count)
 446 {
 447         struct exfat_dentry *file_de, *stream_de, *name_de;
 448         __le16 *name;
 449         int retval, name_len;
 450         int i;
 451
 452         retval = exfat_de_iter_get(de_iter, 0, &file_de);
 453         if (retval || file_de->type != EXFAT_FILE)
 454                 return 1;
 455
 456         retval = exfat_de_iter_get(de_iter, 1, &stream_de);
 457         if (retval || stream_de->type != EXFAT_STREAM)
 458                 return 1;
 459
 460         name = (__le16 *)param;
 461         name_len = (int)exfat_utf16_len(name, PATH_MAX);
 462
 463         if (file_de->dentry.file.num_ext <
 464                 1 + (name_len + ENTRY_NAME_MAX - 1) / ENTRY_NAME_MAX)
 465                 return 1;
 466
 467         for (i = 2; i <= file_de->dentry.file.num_ext && name_len > 0; i++) {
 468                 int len;
 469
 470                 retval = exfat_de_iter_get(de_iter, i, &name_de);
 471                 if (retval || name_de->type != EXFAT_NAME)
 472                         return 1;
 473
 474                 len = MIN(name_len, ENTRY_NAME_MAX);
 475                 if (memcmp(name_de->dentry.name.unicode_0_14,
 476                            name, len * 2) != 0)
 477                         return 1;
 478
 479                 name += len;
 480                 name_len -= len;
 481         }
 482
 483         *dentry_count = i;
 484         return 0;
 485 }
 486
 487 int exfat_lookup_file(struct exfat *exfat, struct exfat_inode *parent,
 488                       const char *name, struct exfat_lookup_filter *filter_out)
 489 {
 490         int retval;
 491         __le16 utf16_name[PATH_MAX + 2] = {0, };
 492
 493         retval = (int)exfat_utf16_enc(name, utf16_name, sizeof(utf16_name));
 494         if (retval < 0)
 495                 return retval;
 496
 497         filter_out->in.type = EXFAT_FILE;
 498         filter_out->in.filter = filter_lookup_file;
 499         filter_out->in.param = utf16_name;
 500
 501         retval = exfat_lookup_dentry_set(exfat, parent, filter_out);
 502         if (retval < 0)
 503                 return retval;
 504
 505         return 0;
 506 }
 507
 508 void exfat_calc_dentry_checksum(struct exfat_dentry *dentry,
 509                                 uint16_t *checksum, bool primary)
 510 {
 511         unsigned int i;
 512         uint8_t *bytes;
 513
 514         bytes = (uint8_t *)dentry;
 515
 516         *checksum = ((*checksum << 15) | (*checksum >> 1)) + bytes[0];
 517         *checksum = ((*checksum << 15) | (*checksum >> 1)) + bytes[1];
 518
 519         i = primary ? 4 : 2;
 520         for (; i < sizeof(*dentry); i++)
 521                 *checksum = ((*checksum << 15) | (*checksum >> 1)) + bytes[i];
 522 }
 523
 524 static uint16_t calc_dentry_set_checksum(struct exfat_dentry *dset, int dcount)
 525 {
 526         uint16_t checksum;
 527         int i;
 528
 529         if (dcount < MIN_FILE_DENTRIES)
 530                 return 0;
 531
 532         checksum = 0;
 533         exfat_calc_dentry_checksum(&dset[0], &checksum, true);
 534         for (i = 1; i < dcount; i++)
 535                 exfat_calc_dentry_checksum(&dset[i], &checksum, false);
 536         return checksum;
 537 }
 538
 539 uint16_t exfat_calc_name_hash(struct exfat *exfat,
 540                               __le16 *name, int len)
 541 {
 542         int i;
 543         __le16 ch;
 544         uint16_t chksum = 0;
 545
 546         for (i = 0; i < len; i++) {
 547                 ch = exfat->upcase_table[le16_to_cpu(name[i])];
 548                 ch = cpu_to_le16(ch);
 549
 550                 chksum = ((chksum << 15) | (chksum >> 1)) + (ch & 0xFF);
 551                 chksum = ((chksum << 15) | (chksum >> 1)) + (ch >> 8);
 552         }
 553         return chksum;
 554 }
 555
 556 static void unix_time_to_exfat_time(time_t unix_time, __u8 *tz, __le16 *date,
 557                                     __le16 *time, __u8 *time_ms)
 558 {
 559         struct tm tm;
 560         __u16 t, d;
 561
 562         gmtime_r(&unix_time, &tm);
 563         d = ((tm.tm_year - 80) << 9) | ((tm.tm_mon + 1) << 5) | tm.tm_mday;
 564         t = (tm.tm_hour << 11) | (tm.tm_min << 5) | (tm.tm_sec >> 1);
 565
 566         *tz = 0x80;
 567         *date = cpu_to_le16(d);
 568         *time = cpu_to_le16(t);
 569         if (time_ms)
 570                 *time_ms = (tm.tm_sec & 1) * 100;
 571 }
 572
 573 int exfat_build_file_dentry_set(struct exfat *exfat, const char *name,
 574                                 unsigned short attr, struct exfat_dentry **dentry_set,
 575                                 int *dentry_count)
 576 {
 577         struct exfat_dentry *dset;
 578         __le16 utf16_name[PATH_MAX + 2];
 579         int retval;
 580         int dcount, name_len, i;
 581         __le16 e_date, e_time;
 582         __u8 tz, e_time_ms;
 583
 584         memset(utf16_name, 0, sizeof(utf16_name));
 585         retval = exfat_utf16_enc(name, utf16_name, sizeof(utf16_name));
 586         if (retval < 0)
 587                 return retval;
 588
 589         name_len = retval / 2;
 590         dcount = 2 + DIV_ROUND_UP(name_len, ENTRY_NAME_MAX);
 591         dset = calloc(1, dcount * DENTRY_SIZE);
 592         if (!dset)
 593                 return -ENOMEM;
 594
 595         dset[0].type = EXFAT_FILE;
 596         dset[0].dentry.file.num_ext = dcount - 1;
 597         dset[0].dentry.file.attr = cpu_to_le16(attr);
 598
 599         unix_time_to_exfat_time(time(NULL), &tz,
 600                                 &e_date, &e_time, &e_time_ms);
 601
 602         dset[0].dentry.file.create_date = e_date;
 603         dset[0].dentry.file.create_time = e_time;
 604         dset[0].dentry.file.create_time_ms = e_time_ms;
 605         dset[0].dentry.file.create_tz = tz;
 606
 607         dset[0].dentry.file.modify_date = e_date;
 608         dset[0].dentry.file.modify_time = e_time;
 609         dset[0].dentry.file.modify_time_ms = e_time_ms;
 610         dset[0].dentry.file.modify_tz = tz;
 611
 612         dset[0].dentry.file.access_date = e_date;
 613         dset[0].dentry.file.access_time = e_time;
 614         dset[0].dentry.file.access_tz = tz;
 615
 616         dset[1].type = EXFAT_STREAM;
 617         dset[1].dentry.stream.flags = 0x01;
 618         dset[1].dentry.stream.name_len = (__u8)name_len;
 619         dset[1].dentry.stream.name_hash =
 620                 cpu_to_le16(exfat_calc_name_hash(exfat, utf16_name, name_len));
 621
 622         for (i = 2; i < dcount; i++) {
 623                 dset[i].type = EXFAT_NAME;
 624                 memcpy(dset[i].dentry.name.unicode_0_14,
 625                        utf16_name + (i - 2) * ENTRY_NAME_MAX,
 626                        ENTRY_NAME_MAX * 2);
 627         }
 628
 629         dset[0].dentry.file.checksum =
 630                 cpu_to_le16(calc_dentry_set_checksum(dset, dcount));
 631
 632         *dentry_set = dset;
 633         *dentry_count = dcount;
 634         return 0;
 635 }
 636
 637 int exfat_update_file_dentry_set(struct exfat *exfat,
 638                                  struct exfat_dentry *dset, int dcount,
 639                                  const char *name,
 640                                  clus_t start_clu, clus_t ccount)
 641 {
 642         int i, name_len;
 643         __le16 utf16_name[PATH_MAX + 2];
 644
 645         if (dset[0].type != EXFAT_FILE || dcount < MIN_FILE_DENTRIES)
 646                 return -EINVAL;
 647
 648         if (name) {
 649                 name_len = (int)exfat_utf16_enc(name,
 650                                                 utf16_name, sizeof(utf16_name));
 651                 if (name_len < 0)
 652                         return name_len;
 653
 654                 name_len /= 2;
 655                 if (dcount != 2 + DIV_ROUND_UP(name_len, ENTRY_NAME_MAX))
 656                         return -EINVAL;
 657
 658                 dset[1].dentry.stream.name_len = (__u8)name_len;
 659                 dset[1].dentry.stream.name_hash =
 660                         exfat_calc_name_hash(exfat, utf16_name, name_len);
 661
 662                 for (i = 2; i < dcount; i++) {
 663                         dset[i].type = EXFAT_NAME;
 664                         memcpy(dset[i].dentry.name.unicode_0_14,
 665                                utf16_name + (i - 2) * ENTRY_NAME_MAX,
 666                                ENTRY_NAME_MAX * 2);
 667                 }
 668         }
 669
 670         dset[1].dentry.stream.valid_size = cpu_to_le64(ccount * exfat->clus_size);
 671         dset[1].dentry.stream.size = cpu_to_le64(ccount * exfat->clus_size);
 672         if (start_clu)
 673                 dset[1].dentry.stream.start_clu = cpu_to_le32(start_clu);
 674
 675         dset[0].dentry.file.checksum =
 676                 cpu_to_le16(calc_dentry_set_checksum(dset, dcount));
 677         return 0;
 678 }
 679
 680 static int find_free_cluster(struct exfat *exfat,
 681                              clus_t start, clus_t *new_clu)
 682 {
 683         clus_t end = le32_to_cpu(exfat->bs->bsx.clu_count) +
 684                 EXFAT_FIRST_CLUSTER;
 685
 686         if (!exfat_heap_clus(exfat, start))
 687                 return -EINVAL;
 688
 689         while (start < end) {
 690                 if (exfat_bitmap_find_zero(exfat, exfat->alloc_bitmap,
 691                                            start, new_clu))
 692                         break;
 693                 if (!exfat_bitmap_get(exfat->disk_bitmap, *new_clu))
 694                         return 0;
 695                 start = *new_clu + 1;
 696         }
 697
 698         end = start;
 699         start = EXFAT_FIRST_CLUSTER;
 700         while (start < end) {
 701                 if (exfat_bitmap_find_zero(exfat, exfat->alloc_bitmap,
 702                                            start, new_clu))
 703                         goto out_nospc;
 704                 if (!exfat_bitmap_get(exfat->disk_bitmap, *new_clu))
 705                         return 0;
 706                 start = *new_clu + 1;
 707         }
 708
 709 out_nospc:
 710         *new_clu = EXFAT_EOF_CLUSTER;
 711         return -ENOSPC;
 712 }
 713
 714 static int exfat_map_cluster(struct exfat *exfat, struct exfat_inode *inode,
 715                              off_t file_off, clus_t *mapped_clu)
 716 {
 717         clus_t clu, next, count, last_count;
 718
 719         if (!exfat_heap_clus(exfat, inode->first_clus))
 720                 return -EINVAL;
 721
 722         clu = inode->first_clus;
 723         next = EXFAT_EOF_CLUSTER;
 724         count = 1;
 725         if (file_off == EOF)
 726                 last_count = DIV_ROUND_UP(inode->size, exfat->clus_size);
 727         else
 728                 last_count = file_off / exfat->clus_size + 1;
 729
 730         while (true) {
 731                 if (count * exfat->clus_size > inode->size)
 732                         return -EINVAL;
 733
 734                 if (count == last_count) {
 735                         *mapped_clu = clu;
 736                         return 0;
 737                 }
 738
 739                 if (exfat_get_inode_next_clus(exfat, inode, clu, &next))
 740                         return -EINVAL;
 741
 742                 if (!exfat_heap_clus(exfat, clu))
 743                         return -EINVAL;
 744
 745                 clu = next;
 746                 count++;
 747         }
 748         return -EINVAL;
 749 }
 750
 751 static int exfat_write_dentry_set(struct exfat *exfat,
 752                                   struct exfat_dentry *dset, int dcount,
 753                                   off_t dev_off, off_t *next_dev_off)
 754 {
 755         clus_t clus;
 756         unsigned int clus_off, dent_len, first_half_len, sec_half_len;
 757         off_t first_half_off, sec_half_off = 0;
 758
 759         if (exfat_o2c(exfat, dev_off, &clus, &clus_off))
 760                 return -ERANGE;
 761
 762         dent_len = dcount * DENTRY_SIZE;
 763         first_half_len = MIN(dent_len, exfat->clus_size - clus_off);
 764         sec_half_len = dent_len - first_half_len;
 765
 766         first_half_off = dev_off;
 767         if (sec_half_len) {
 768                 clus_t next_clus;
 769
 770                 if (exfat_get_next_clus(exfat, clus, &next_clus))
 771                         return -EIO;
 772                 if (!exfat_heap_clus(exfat, next_clus))
 773                         return -EINVAL;
 774                 sec_half_off = exfat_c2o(exfat, next_clus);
 775         }
 776
 777         if (exfat_write(exfat->blk_dev->dev_fd, dset, first_half_len,
 778                         first_half_off) != (ssize_t)first_half_len)
 779                 return -EIO;
 780
 781         if (sec_half_len) {
 782                 dset = (struct exfat_dentry *)((char *)dset + first_half_len);
 783                 if (exfat_write(exfat->blk_dev->dev_fd, dset, sec_half_len,
 784                                 sec_half_off) != (ssize_t)sec_half_len)
 785                         return -EIO;
 786         }
 787
 788         if (next_dev_off) {
 789                 if (sec_half_len)
 790                         *next_dev_off = sec_half_off + sec_half_len;
 791                 else
 792                         *next_dev_off = first_half_off + first_half_len;
 793         }
 794         return 0;
 795 }
 796
 797 static int exfat_alloc_cluster(struct exfat *exfat, struct exfat_inode *inode,
 798                                clus_t *new_clu)
 799 {
 800         clus_t last_clu;
 801         int err;
 802         bool need_dset = inode != exfat->root;
 803
 804         if ((need_dset && !inode->dentry_set) || inode->is_contiguous)
 805                 return -EINVAL;
 806
 807         err = find_free_cluster(exfat, exfat->start_clu, new_clu);
 808         if (err) {
 809                 exfat->start_clu = EXFAT_FIRST_CLUSTER;
 810                 exfat_err("failed to find an free cluster\n");
 811                 return -ENOSPC;
 812         }
 813         exfat->start_clu = *new_clu;
 814
 815         if (exfat_set_fat(exfat, *new_clu, EXFAT_EOF_CLUSTER))
 816                 return -EIO;
 817
 818         /* zero out the new cluster */
 819         if (exfat_write(exfat->blk_dev->dev_fd, exfat->zero_cluster,
 820                         exfat->clus_size, exfat_c2o(exfat, *new_clu)) !=
 821             (ssize_t)exfat->clus_size) {
 822                 exfat_err("failed to fill new cluster with zeroes\n");
 823                 return -EIO;
 824         }
 825
 826         if (inode->size) {
 827                 err = exfat_map_cluster(exfat, inode, EOF, &last_clu);
 828                 if (err) {
 829                         exfat_err("failed to get the last cluster\n");
 830                         return err;
 831                 }
 832
 833                 if (exfat_set_fat(exfat, last_clu, *new_clu))
 834                         return -EIO;
 835
 836                 if (need_dset) {
 837                         err = exfat_update_file_dentry_set(exfat,
 838                                                            inode->dentry_set,
 839                                                            inode->dentry_count,
 840                                                            NULL, 0,
 841                                                            DIV_ROUND_UP(inode->size,
 842                                                                         exfat->clus_size) + 1);
 843                         if (err)
 844                                 return -EINVAL;
 845                 }
 846         } else {
 847                 if (need_dset) {
 848                         err = exfat_update_file_dentry_set(exfat,
 849                                                            inode->dentry_set,
 850                                                            inode->dentry_count,
 851                                                            NULL, *new_clu, 1);
 852                         if (err)
 853                                 return -EINVAL;
 854                 }
 855         }
 856
 857         if (need_dset && exfat_write_dentry_set(exfat, inode->dentry_set,
 858                                                 inode->dentry_count,
 859                                                 inode->dev_offset, NULL))
 860                 return -EIO;
 861
 862         exfat_bitmap_set(exfat->alloc_bitmap, *new_clu);
 863         if (inode->size == 0)
 864                 inode->first_clus = *new_clu;
 865         inode->size += exfat->clus_size;
 866         return 0;
 867 }
 868
 869 int exfat_add_dentry_set(struct exfat *exfat, struct exfat_dentry_loc *loc,
 870                          struct exfat_dentry *dset, int dcount,
 871                          bool need_next_loc)
 872 {
 873         struct exfat_inode *parent = loc->parent;
 874         off_t dev_off, next_dev_off;
 875
 876         if (parent->is_contiguous ||
 877             (uint64_t)loc->file_offset > parent->size ||
 878             (unsigned int)dcount * DENTRY_SIZE > exfat->clus_size)
 879                 return -EINVAL;
 880
 881         dev_off = loc->dev_offset;
 882         if ((uint64_t)loc->file_offset + dcount * DENTRY_SIZE > parent->size) {
 883                 clus_t new_clus;
 884
 885                 if (exfat_alloc_cluster(exfat, parent, &new_clus))
 886                         return -EIO;
 887                 if ((uint64_t)loc->file_offset == parent->size - exfat->clus_size)
 888                         dev_off = exfat_c2o(exfat, new_clus);
 889         }
 890
 891         if (exfat_write_dentry_set(exfat, dset, dcount, dev_off, &next_dev_off))
 892                 return -EIO;
 893
 894         if (need_next_loc) {
 895                 loc->file_offset += dcount * DENTRY_SIZE;
 896                 loc->dev_offset = next_dev_off;
 897         }
 898         return 0;
 899 }
 900
 901 int exfat_create_file(struct exfat *exfat, struct exfat_inode *parent,
 902                       const char *name, unsigned short attr)
 903 {
 904         struct exfat_dentry *dset;
 905         int err, dcount;
 906         struct exfat_lookup_filter filter;
 907         struct exfat_dentry_loc loc;
 908
 909         err = exfat_lookup_file(exfat, parent, name, &filter);
 910         if (err == 0) {
 911                 dset = filter.out.dentry_set;
 912                 dcount = filter.out.dentry_count;
 913                 if ((le16_to_cpu(dset->dentry.file.attr) & attr) != attr)
 914                         err = -EEXIST;
 915                 goto out;
 916         }
 917
 918         err = exfat_build_file_dentry_set(exfat, name, attr,
 919                                           &dset, &dcount);
 920         if (err)
 921                 return err;
 922
 923         loc.parent = parent;
 924         loc.file_offset = filter.out.file_offset;
 925         loc.dev_offset = filter.out.dev_offset;
 926         err = exfat_add_dentry_set(exfat, &loc, dset, dcount, false);
 927 out:
 928         free(dset);
 929         return err;
 930 }