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->invalid_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, empty_dentry_count = 0;
 360         int retval;
 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                 if (!IS_EXFAT_DELETED(dentry->type)) {
 382                         if (filter->in.dentry_count == 0 ||
 383                             empty_dentry_count < filter->in.dentry_count)
 384                                 empty_dentry_count = 0;
 385                 }
 386
 387                 dentry_count = 1;
 388                 if (dentry->type == filter->in.type) {
 389                         retval = 0;
 390                         if (filter->in.filter)
 391                                 retval = filter->in.filter(&de_iter,
 392                                                         filter->in.param,
 393                                                         &dentry_count);
 394
 395                         if (retval == 0) {
 396                                 struct exfat_dentry *d;
 397                                 int i;
 398
 399                                 filter->out.dentry_set = calloc(dentry_count,
 400                                                                 sizeof(struct exfat_dentry));
 401                                 if (!filter->out.dentry_set) {
 402                                         retval = -ENOMEM;
 403                                         goto out;
 404                                 }
 405                                 for (i = 0; i < dentry_count; i++) {
 406                                         exfat_de_iter_get(&de_iter, i, &d);
 407                                         memcpy(filter->out.dentry_set + i, d,
 408                                                sizeof(struct exfat_dentry));
 409                                 }
 410                                 filter->out.dentry_count = dentry_count;
 411                                 goto out;
 412                         } else if (retval < 0) {
 413                                 goto out;
 414                         }
 415                 } else if (IS_EXFAT_DELETED(dentry->type)) {
 416                         if (empty_dentry_count == 0) {
 417                                 free_file_offset =
 418                                         exfat_de_iter_file_offset(&de_iter);
 419                                 free_dev_offset =
 420                                         exfat_de_iter_device_offset(&de_iter);
 421                         }
 422
 423                         if (filter->in.dentry_count == 0 ||
 424                             empty_dentry_count < filter->in.dentry_count)
 425                                 empty_dentry_count++;
 426                 }
 427
 428                 exfat_de_iter_advance(&de_iter, dentry_count);
 429         }
 430
 431 out:
 432         if (retval == 0) {
 433                 filter->out.file_offset =
 434                         exfat_de_iter_file_offset(&de_iter);
 435                 filter->out.dev_offset =
 436                         exfat_de_iter_device_offset(&de_iter);
 437         } else if (retval == EOF && empty_dentry_count) {
 438                 filter->out.file_offset = free_file_offset;
 439                 filter->out.dev_offset = free_dev_offset;
 440         } else {
 441                 filter->out.file_offset = exfat_de_iter_file_offset(&de_iter);
 442                 filter->out.dev_offset = EOF;
 443         }
 444         if (bd)
 445                 exfat_free_buffer(bd, 2);
 446         return retval;
 447 }
 448
 449 static int filter_lookup_file(struct exfat_de_iter *de_iter,
 450                               void *param, int *dentry_count)
 451 {
 452         struct exfat_dentry *file_de, *stream_de, *name_de;
 453         __le16 *name;
 454         int retval, name_len;
 455         int i;
 456
 457         retval = exfat_de_iter_get(de_iter, 0, &file_de);
 458         if (retval || file_de->type != EXFAT_FILE)
 459                 return 1;
 460
 461         retval = exfat_de_iter_get(de_iter, 1, &stream_de);
 462         if (retval || stream_de->type != EXFAT_STREAM)
 463                 return 1;
 464
 465         name = (__le16 *)param;
 466         name_len = (int)exfat_utf16_len(name, PATH_MAX);
 467
 468         if (file_de->dentry.file.num_ext <
 469                 1 + (name_len + ENTRY_NAME_MAX - 1) / ENTRY_NAME_MAX)
 470                 return 1;
 471
 472         for (i = 2; i <= file_de->dentry.file.num_ext && name_len > 0; i++) {
 473                 int len;
 474
 475                 retval = exfat_de_iter_get(de_iter, i, &name_de);
 476                 if (retval || name_de->type != EXFAT_NAME)
 477                         return 1;
 478
 479                 len = MIN(name_len + 1, ENTRY_NAME_MAX);
 480                 if (memcmp(name_de->dentry.name.unicode_0_14,
 481                            name, len * 2) != 0)
 482                         return 1;
 483
 484                 name += len;
 485                 name_len -= len;
 486         }
 487
 488         *dentry_count = i;
 489         return 0;
 490 }
 491
 492 int exfat_lookup_file_by_utf16name(struct exfat *exfat,
 493                                  struct exfat_inode *parent,
 494                                  __le16 *utf16_name,
 495                                  struct exfat_lookup_filter *filter_out)
 496 {
 497         int retval;
 498
 499         filter_out->in.type = EXFAT_FILE;
 500         filter_out->in.filter = filter_lookup_file;
 501         filter_out->in.param = utf16_name;
 502         filter_out->in.dentry_count = 0;
 503
 504         retval = exfat_lookup_dentry_set(exfat, parent, filter_out);
 505         if (retval < 0)
 506                 return retval;
 507
 508         return 0;
 509 }
 510
 511 int exfat_lookup_file(struct exfat *exfat, struct exfat_inode *parent,
 512                       const char *name, struct exfat_lookup_filter *filter_out)
 513 {
 514         int retval;
 515         __le16 utf16_name[PATH_MAX + 2] = {0, };
 516
 517         retval = (int)exfat_utf16_enc(name, utf16_name, sizeof(utf16_name));
 518         if (retval < 0)
 519                 return retval;
 520
 521         return exfat_lookup_file_by_utf16name(exfat, parent, utf16_name,
 522                         filter_out);
 523 }
 524
 525 void exfat_calc_dentry_checksum(struct exfat_dentry *dentry,
 526                                 uint16_t *checksum, bool primary)
 527 {
 528         unsigned int i;
 529         uint8_t *bytes;
 530
 531         bytes = (uint8_t *)dentry;
 532
 533         /* use += to avoid promotion to int; UBSan complaints about signed overflow */
 534         *checksum = (*checksum << 15) | (*checksum >> 1);
 535         *checksum += bytes[0];
 536         *checksum = (*checksum << 15) | (*checksum >> 1);
 537         *checksum += bytes[1];
 538
 539         i = primary ? 4 : 2;
 540         for (; i < sizeof(*dentry); i++) {
 541                 *checksum = (*checksum << 15) | (*checksum >> 1);
 542                 *checksum += bytes[i];
 543         }
 544 }
 545
 546 static uint16_t calc_dentry_set_checksum(struct exfat_dentry *dset, int dcount)
 547 {
 548         uint16_t checksum;
 549         int i;
 550
 551         if (dcount < MIN_FILE_DENTRIES)
 552                 return 0;
 553
 554         checksum = 0;
 555         exfat_calc_dentry_checksum(&dset[0], &checksum, true);
 556         for (i = 1; i < dcount; i++)
 557                 exfat_calc_dentry_checksum(&dset[i], &checksum, false);
 558         return checksum;
 559 }
 560
 561 uint16_t exfat_calc_name_hash(struct exfat *exfat,
 562                               __le16 *name, int len)
 563 {
 564         int i;
 565         __le16 ch;
 566         uint16_t chksum = 0;
 567
 568         for (i = 0; i < len; i++) {
 569                 ch = exfat->upcase_table[le16_to_cpu(name[i])];
 570                 ch = cpu_to_le16(ch);
 571
 572                 /* use += to avoid promotion to int; UBSan complaints about signed overflow */
 573                 chksum = (chksum << 15) | (chksum >> 1);
 574                 chksum += ch & 0xFF;
 575                 chksum = (chksum << 15) | (chksum >> 1);
 576                 chksum += ch >> 8;
 577         }
 578         return chksum;
 579 }
 580
 581 static void unix_time_to_exfat_time(time_t unix_time, __u8 *tz, __le16 *date,
 582                                     __le16 *time, __u8 *time_ms)
 583 {
 584         struct tm tm;
 585         __u16 t, d;
 586
 587         gmtime_r(&unix_time, &tm);
 588         d = ((tm.tm_year - 80) << 9) | ((tm.tm_mon + 1) << 5) | tm.tm_mday;
 589         t = (tm.tm_hour << 11) | (tm.tm_min << 5) | (tm.tm_sec >> 1);
 590
 591         *tz = 0x80;
 592         *date = cpu_to_le16(d);
 593         *time = cpu_to_le16(t);
 594         if (time_ms)
 595                 *time_ms = (tm.tm_sec & 1) * 100;
 596 }
 597
 598 int exfat_build_file_dentry_set(struct exfat *exfat, const char *name,
 599                                 unsigned short attr, struct exfat_dentry **dentry_set,
 600                                 int *dentry_count)
 601 {
 602         struct exfat_dentry *dset;
 603         __le16 utf16_name[PATH_MAX + 2];
 604         int retval;
 605         int dcount, name_len, i;
 606         __le16 e_date, e_time;
 607         __u8 tz, e_time_ms;
 608
 609         memset(utf16_name, 0, sizeof(utf16_name));
 610         retval = exfat_utf16_enc(name, utf16_name, sizeof(utf16_name));
 611         if (retval < 0)
 612                 return retval;
 613
 614         name_len = retval / 2;
 615         dcount = 2 + DIV_ROUND_UP(name_len, ENTRY_NAME_MAX);
 616         dset = calloc(1, dcount * DENTRY_SIZE);
 617         if (!dset)
 618                 return -ENOMEM;
 619
 620         dset[0].type = EXFAT_FILE;
 621         dset[0].dentry.file.num_ext = dcount - 1;
 622         dset[0].dentry.file.attr = cpu_to_le16(attr);
 623
 624         unix_time_to_exfat_time(time(NULL), &tz,
 625                                 &e_date, &e_time, &e_time_ms);
 626
 627         dset[0].dentry.file.create_date = e_date;
 628         dset[0].dentry.file.create_time = e_time;
 629         dset[0].dentry.file.create_time_ms = e_time_ms;
 630         dset[0].dentry.file.create_tz = tz;
 631
 632         dset[0].dentry.file.modify_date = e_date;
 633         dset[0].dentry.file.modify_time = e_time;
 634         dset[0].dentry.file.modify_time_ms = e_time_ms;
 635         dset[0].dentry.file.modify_tz = tz;
 636
 637         dset[0].dentry.file.access_date = e_date;
 638         dset[0].dentry.file.access_time = e_time;
 639         dset[0].dentry.file.access_tz = tz;
 640
 641         dset[1].type = EXFAT_STREAM;
 642         dset[1].dentry.stream.flags = 0x01;
 643         dset[1].dentry.stream.name_len = (__u8)name_len;
 644         dset[1].dentry.stream.name_hash =
 645                 cpu_to_le16(exfat_calc_name_hash(exfat, utf16_name, name_len));
 646
 647         for (i = 2; i < dcount; i++) {
 648                 dset[i].type = EXFAT_NAME;
 649                 memcpy(dset[i].dentry.name.unicode_0_14,
 650                        utf16_name + (i - 2) * ENTRY_NAME_MAX,
 651                        ENTRY_NAME_MAX * 2);
 652         }
 653
 654         dset[0].dentry.file.checksum =
 655                 cpu_to_le16(calc_dentry_set_checksum(dset, dcount));
 656
 657         *dentry_set = dset;
 658         *dentry_count = dcount;
 659         return 0;
 660 }
 661
 662 int exfat_update_file_dentry_set(struct exfat *exfat,
 663                                  struct exfat_dentry *dset, int dcount,
 664                                  const char *name,
 665                                  clus_t start_clu, clus_t ccount)
 666 {
 667         int i, name_len;
 668         __le16 utf16_name[PATH_MAX + 2];
 669
 670         if (dset[0].type != EXFAT_FILE || dcount < MIN_FILE_DENTRIES)
 671                 return -EINVAL;
 672
 673         if (name) {
 674                 name_len = (int)exfat_utf16_enc(name,
 675                                                 utf16_name, sizeof(utf16_name));
 676                 if (name_len < 0)
 677                         return name_len;
 678
 679                 name_len /= 2;
 680                 if (dcount != 2 + DIV_ROUND_UP(name_len, ENTRY_NAME_MAX))
 681                         return -EINVAL;
 682
 683                 dset[1].dentry.stream.name_len = (__u8)name_len;
 684                 dset[1].dentry.stream.name_hash =
 685                         exfat_calc_name_hash(exfat, utf16_name, name_len);
 686
 687                 for (i = 2; i < dcount; i++) {
 688                         dset[i].type = EXFAT_NAME;
 689                         memcpy(dset[i].dentry.name.unicode_0_14,
 690                                utf16_name + (i - 2) * ENTRY_NAME_MAX,
 691                                ENTRY_NAME_MAX * 2);
 692                 }
 693         }
 694
 695         dset[1].dentry.stream.valid_size = cpu_to_le64(ccount * exfat->clus_size);
 696         dset[1].dentry.stream.size = cpu_to_le64(ccount * exfat->clus_size);
 697         if (start_clu)
 698                 dset[1].dentry.stream.start_clu = cpu_to_le32(start_clu);
 699
 700         dset[0].dentry.file.checksum =
 701                 cpu_to_le16(calc_dentry_set_checksum(dset, dcount));
 702         return 0;
 703 }
 704
 705 static int find_free_cluster(struct exfat *exfat,
 706                              clus_t start, clus_t *new_clu)
 707 {
 708         clus_t end = le32_to_cpu(exfat->bs->bsx.clu_count) +
 709                 EXFAT_FIRST_CLUSTER;
 710
 711         if (!exfat_heap_clus(exfat, start))
 712                 return -EINVAL;
 713
 714         while (start < end) {
 715                 if (exfat_bitmap_find_zero(exfat, exfat->alloc_bitmap,
 716                                            start, new_clu))
 717                         break;
 718                 if (!exfat_bitmap_get(exfat->disk_bitmap, *new_clu))
 719                         return 0;
 720                 start = *new_clu + 1;
 721         }
 722
 723         end = start;
 724         start = EXFAT_FIRST_CLUSTER;
 725         while (start < end) {
 726                 if (exfat_bitmap_find_zero(exfat, exfat->alloc_bitmap,
 727                                            start, new_clu))
 728                         goto out_nospc;
 729                 if (!exfat_bitmap_get(exfat->disk_bitmap, *new_clu))
 730                         return 0;
 731                 start = *new_clu + 1;
 732         }
 733
 734 out_nospc:
 735         *new_clu = EXFAT_EOF_CLUSTER;
 736         return -ENOSPC;
 737 }
 738
 739 static int exfat_map_cluster(struct exfat *exfat, struct exfat_inode *inode,
 740                              off_t file_off, clus_t *mapped_clu)
 741 {
 742         clus_t clu, next, count, last_count;
 743
 744         if (!exfat_heap_clus(exfat, inode->first_clus))
 745                 return -EINVAL;
 746
 747         clu = inode->first_clus;
 748         next = EXFAT_EOF_CLUSTER;
 749         count = 1;
 750         if (file_off == EOF)
 751                 last_count = DIV_ROUND_UP(inode->size, exfat->clus_size);
 752         else
 753                 last_count = file_off / exfat->clus_size + 1;
 754
 755         while (true) {
 756                 if (count * exfat->clus_size > inode->size)
 757                         return -EINVAL;
 758
 759                 if (count == last_count) {
 760                         *mapped_clu = clu;
 761                         return 0;
 762                 }
 763
 764                 if (exfat_get_inode_next_clus(exfat, inode, clu, &next))
 765                         return -EINVAL;
 766
 767                 if (!exfat_heap_clus(exfat, clu))
 768                         return -EINVAL;
 769
 770                 clu = next;
 771                 count++;
 772         }
 773         return -EINVAL;
 774 }
 775
 776 static int exfat_write_dentry_set(struct exfat *exfat,
 777                                   struct exfat_dentry *dset, int dcount,
 778                                   off_t dev_off, off_t *next_dev_off)
 779 {
 780         clus_t clus;
 781         unsigned int clus_off, dent_len, first_half_len, sec_half_len;
 782         off_t first_half_off, sec_half_off = 0;
 783
 784         if (exfat_o2c(exfat, dev_off, &clus, &clus_off))
 785                 return -ERANGE;
 786
 787         dent_len = dcount * DENTRY_SIZE;
 788         first_half_len = MIN(dent_len, exfat->clus_size - clus_off);
 789         sec_half_len = dent_len - first_half_len;
 790
 791         first_half_off = dev_off;
 792         if (sec_half_len) {
 793                 clus_t next_clus;
 794
 795                 if (exfat_get_next_clus(exfat, clus, &next_clus))
 796                         return -EIO;
 797                 if (!exfat_heap_clus(exfat, next_clus))
 798                         return -EINVAL;
 799                 sec_half_off = exfat_c2o(exfat, next_clus);
 800         }
 801
 802         if (exfat_write(exfat->blk_dev->dev_fd, dset, first_half_len,
 803                         first_half_off) != (ssize_t)first_half_len)
 804                 return -EIO;
 805
 806         if (sec_half_len) {
 807                 dset = (struct exfat_dentry *)((char *)dset + first_half_len);
 808                 if (exfat_write(exfat->blk_dev->dev_fd, dset, sec_half_len,
 809                                 sec_half_off) != (ssize_t)sec_half_len)
 810                         return -EIO;
 811         }
 812
 813         if (next_dev_off) {
 814                 if (sec_half_len)
 815                         *next_dev_off = sec_half_off + sec_half_len;
 816                 else
 817                         *next_dev_off = first_half_off + first_half_len;
 818         }
 819         return 0;
 820 }
 821
 822 static int exfat_alloc_cluster(struct exfat *exfat, struct exfat_inode *inode,
 823                                clus_t *new_clu)
 824 {
 825         clus_t last_clu;
 826         int err;
 827         bool need_dset = inode != exfat->root;
 828
 829         if ((need_dset && !inode->dentry_set) || inode->is_contiguous)
 830                 return -EINVAL;
 831
 832         err = find_free_cluster(exfat, exfat->start_clu, new_clu);
 833         if (err) {
 834                 exfat->start_clu = EXFAT_FIRST_CLUSTER;
 835                 exfat_err("failed to find an free cluster\n");
 836                 return -ENOSPC;
 837         }
 838         exfat->start_clu = *new_clu;
 839
 840         if (exfat_set_fat(exfat, *new_clu, EXFAT_EOF_CLUSTER))
 841                 return -EIO;
 842
 843         /* zero out the new cluster */
 844         if (exfat_write(exfat->blk_dev->dev_fd, exfat->zero_cluster,
 845                         exfat->clus_size, exfat_c2o(exfat, *new_clu)) !=
 846             (ssize_t)exfat->clus_size) {
 847                 exfat_err("failed to fill new cluster with zeroes\n");
 848                 return -EIO;
 849         }
 850
 851         if (inode->size) {
 852                 err = exfat_map_cluster(exfat, inode, EOF, &last_clu);
 853                 if (err) {
 854                         exfat_err("failed to get the last cluster\n");
 855                         return err;
 856                 }
 857
 858                 if (exfat_set_fat(exfat, last_clu, *new_clu))
 859                         return -EIO;
 860
 861                 if (need_dset) {
 862                         err = exfat_update_file_dentry_set(exfat,
 863                                                            inode->dentry_set,
 864                                                            inode->dentry_count,
 865                                                            NULL, 0,
 866                                                            DIV_ROUND_UP(inode->size,
 867                                                                         exfat->clus_size) + 1);
 868                         if (err)
 869                                 return -EINVAL;
 870                 }
 871         } else {
 872                 if (need_dset) {
 873                         err = exfat_update_file_dentry_set(exfat,
 874                                                            inode->dentry_set,
 875                                                            inode->dentry_count,
 876                                                            NULL, *new_clu, 1);
 877                         if (err)
 878                                 return -EINVAL;
 879                 }
 880         }
 881
 882         if (need_dset && exfat_write_dentry_set(exfat, inode->dentry_set,
 883                                                 inode->dentry_count,
 884                                                 inode->dev_offset, NULL))
 885                 return -EIO;
 886
 887         exfat_bitmap_set(exfat->alloc_bitmap, *new_clu);
 888         if (inode->size == 0)
 889                 inode->first_clus = *new_clu;
 890         inode->size += exfat->clus_size;
 891         return 0;
 892 }
 893
 894 int exfat_add_dentry_set(struct exfat *exfat, struct exfat_dentry_loc *loc,
 895                          struct exfat_dentry *dset, int dcount,
 896                          bool need_next_loc)
 897 {
 898         struct exfat_inode *parent = loc->parent;
 899         off_t dev_off, next_dev_off;
 900
 901         if (parent->is_contiguous ||
 902             (uint64_t)loc->file_offset > parent->size ||
 903             (unsigned int)dcount * DENTRY_SIZE > exfat->clus_size)
 904                 return -EINVAL;
 905
 906         dev_off = loc->dev_offset;
 907         if ((uint64_t)loc->file_offset + dcount * DENTRY_SIZE > parent->size) {
 908                 clus_t new_clus;
 909
 910                 if (exfat_alloc_cluster(exfat, parent, &new_clus))
 911                         return -EIO;
 912                 if ((uint64_t)loc->file_offset == parent->size - exfat->clus_size)
 913                         dev_off = exfat_c2o(exfat, new_clus);
 914         }
 915
 916         if (exfat_write_dentry_set(exfat, dset, dcount, dev_off, &next_dev_off))
 917                 return -EIO;
 918
 919         if (need_next_loc) {
 920                 loc->file_offset += dcount * DENTRY_SIZE;
 921                 loc->dev_offset = next_dev_off;
 922         }
 923         return 0;
 924 }
 925
 926 int exfat_create_file(struct exfat *exfat, struct exfat_inode *parent,
 927                       const char *name, unsigned short attr)
 928 {
 929         struct exfat_dentry *dset;
 930         int err, dcount;
 931         struct exfat_lookup_filter filter;
 932         struct exfat_dentry_loc loc;
 933
 934         err = exfat_lookup_file(exfat, parent, name, &filter);
 935         if (err == 0) {
 936                 dset = filter.out.dentry_set;
 937                 dcount = filter.out.dentry_count;
 938                 if ((le16_to_cpu(dset->dentry.file.attr) & attr) != attr)
 939                         err = -EEXIST;
 940                 goto out;
 941         }
 942
 943         err = exfat_build_file_dentry_set(exfat, name, attr,
 944                                           &dset, &dcount);
 945         if (err)
 946                 return err;
 947
 948         loc.parent = parent;
 949         loc.file_offset = filter.out.file_offset;
 950         loc.dev_offset = filter.out.dev_offset;
 951         err = exfat_add_dentry_set(exfat, &loc, dset, dcount, false);
 952 out:
 953         free(dset);
 954         return err;
 955 }