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