fsck/fsck.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  *   Copyright (C) 2019 Namjae Jeon <linkinjeon@kernel.org>
   4  *   Copyright (C) 2020 Hyunchul Lee <hyc.lee@gmail.com>
   5  */
   6
   7 #include <unistd.h>
   8 #include <stdlib.h>
   9 #include <stdio.h>
  10 #include <getopt.h>
  11 #include <inttypes.h>
  12 #include <string.h>
  13 #include <errno.h>
  14 #include <locale.h>
  15
  16 #include "exfat_ondisk.h"
  17 #include "libexfat.h"
  18 #include "fsck.h"
  19 #include "repair.h"
  20
  21 struct fsck_user_input {
  22         struct exfat_user_input         ei;
  23         enum fsck_ui_options            options;
  24 };
  25
  26 #define EXFAT_MAX_UPCASE_CHARS  0x10000
  27
  28 #ifdef WORDS_BIGENDIAN
  29 typedef __u8    bitmap_t;
  30 #else
  31 typedef __u32   bitmap_t;
  32 #endif
  33
  34 #define BITS_PER        (sizeof(bitmap_t) * 8)
  35 #define BIT_MASK(__c)   (1 << ((__c) % BITS_PER))
  36 #define BIT_ENTRY(__c)  ((__c) / BITS_PER)
  37
  38 #define EXFAT_BITMAP_SIZE(__c_count)    \
  39         (DIV_ROUND_UP(__c_count, BITS_PER) * sizeof(bitmap_t))
  40 #define EXFAT_BITMAP_GET(__bmap, __c)   \
  41                         ((__bmap)[BIT_ENTRY(__c)] & BIT_MASK(__c))
  42 #define EXFAT_BITMAP_SET(__bmap, __c)   \
  43                         ((__bmap)[BIT_ENTRY(__c)] |= BIT_MASK(__c))
  44
  45 #define FSCK_EXIT_NO_ERRORS             0x00
  46 #define FSCK_EXIT_CORRECTED             0x01
  47 #define FSCK_EXIT_NEED_REBOOT           0x02
  48 #define FSCK_EXIT_ERRORS_LEFT           0x04
  49 #define FSCK_EXIT_OPERATION_ERROR       0x08
  50 #define FSCK_EXIT_SYNTAX_ERROR          0x10
  51 #define FSCK_EXIT_USER_CANCEL           0x20
  52 #define FSCK_EXIT_LIBRARY_ERROR         0x80
  53
  54 struct exfat_stat {
  55         long            dir_count;
  56         long            file_count;
  57         long            dir_free_count;
  58         long            file_free_count;
  59 };
  60
  61 struct path_resolve_ctx {
  62         struct exfat_inode      *ancestors[255];
  63         __le16                  utf16_path[PATH_MAX + 2];
  64         char                    local_path[PATH_MAX * MB_LEN_MAX + 1];
  65 };
  66
  67 struct exfat_stat exfat_stat;
  68 struct path_resolve_ctx path_resolve_ctx;
  69
  70 static struct option opts[] = {
  71         {"repair",      no_argument,    NULL,   'r' },
  72         {"repair-yes",  no_argument,    NULL,   'y' },
  73         {"repair-no",   no_argument,    NULL,   'n' },
  74         {"version",     no_argument,    NULL,   'V' },
  75         {"verbose",     no_argument,    NULL,   'v' },
  76         {"help",        no_argument,    NULL,   'h' },
  77         {"?",           no_argument,    NULL,   '?' },
  78         {NULL,          0,              NULL,    0  }
  79 };
  80
  81 static void usage(char *name)
  82 {
  83         fprintf(stderr, "Usage: %s\n", name);
  84         fprintf(stderr, "\t-r | --repair        Repair interactively\n");
  85         fprintf(stderr, "\t-y | --repair-yes    Repair without ask\n");
  86         fprintf(stderr, "\t-n | --repair-no     No repair\n");
  87         fprintf(stderr, "\t-V | --version       Show version\n");
  88         fprintf(stderr, "\t-v | --verbose       Print debug\n");
  89         fprintf(stderr, "\t-h | --help          Show help\n");
  90
  91         exit(FSCK_EXIT_SYNTAX_ERROR);
  92 }
  93
  94 static struct exfat_inode *alloc_exfat_inode(__u16 attr)
  95 {
  96         struct exfat_inode *node;
  97         int size;
  98
  99         size = offsetof(struct exfat_inode, name) + NAME_BUFFER_SIZE;
 100         node = (struct exfat_inode *)calloc(1, size);
 101         if (!node) {
 102                 exfat_err("failed to allocate exfat_node\n");
 103                 return NULL;
 104         }
 105
 106         node->parent = NULL;
 107         INIT_LIST_HEAD(&node->children);
 108         INIT_LIST_HEAD(&node->sibling);
 109         INIT_LIST_HEAD(&node->list);
 110
 111         node->last_pclus = EXFAT_EOF_CLUSTER;
 112         node->attr = attr;
 113         if (attr & ATTR_SUBDIR)
 114                 exfat_stat.dir_count++;
 115         else
 116                 exfat_stat.file_count++;
 117         return node;
 118 }
 119
 120 static void free_exfat_inode(struct exfat_inode *node)
 121 {
 122         if (node->attr & ATTR_SUBDIR)
 123                 exfat_stat.dir_free_count++;
 124         else
 125                 exfat_stat.file_free_count++;
 126         free(node);
 127 }
 128
 129 static void inode_free_children(struct exfat_inode *dir, bool file_only)
 130 {
 131         struct exfat_inode *node, *i;
 132
 133         list_for_each_entry_safe(node, i, &dir->children, sibling) {
 134                 if (file_only) {
 135                         if (!(node->attr & ATTR_SUBDIR)) {
 136                                 list_del(&node->sibling);
 137                                 free_exfat_inode(node);
 138                         }
 139                 } else {
 140                         list_del(&node->sibling);
 141                         list_del(&node->list);
 142                         free_exfat_inode(node);
 143                 }
 144         }
 145 }
 146
 147 static void inode_free_file_children(struct exfat_inode *dir)
 148 {
 149         inode_free_children(dir, true);
 150 }
 151
 152 /* delete @child and all ancestors that does not have
 153  * children
 154  */
 155 static void inode_free_ancestors(struct exfat_inode *child)
 156 {
 157         struct exfat_inode *parent;
 158
 159         if (!list_empty(&child->children))
 160                 return;
 161
 162         do {
 163                 if (!(child->attr & ATTR_SUBDIR)) {
 164                         exfat_err("not directory.\n");
 165                         return;
 166                 }
 167
 168                 parent = child->parent;
 169                 list_del(&child->sibling);
 170                 free_exfat_inode(child);
 171
 172                 child = parent;
 173         } while (child && list_empty(&child->children));
 174
 175         return;
 176 }
 177
 178 static struct exfat *alloc_exfat(struct exfat_blk_dev *bd)
 179 {
 180         struct exfat *exfat;
 181
 182         exfat = (struct exfat *)calloc(1, sizeof(*exfat));
 183         if (!exfat) {
 184                 exfat_err("failed to allocate exfat\n");
 185                 return NULL;
 186         }
 187
 188         exfat->blk_dev = bd;
 189         INIT_LIST_HEAD(&exfat->dir_list);
 190         return exfat;
 191 }
 192
 193 static void free_exfat(struct exfat *exfat)
 194 {
 195         if (exfat) {
 196                 if (exfat->bs)
 197                         free(exfat->bs);
 198                 if (exfat->de_iter.dentries)
 199                         free(exfat->de_iter.dentries);
 200                 if (exfat->alloc_bitmap)
 201                         free(exfat->alloc_bitmap);
 202                 free(exfat);
 203         }
 204 }
 205
 206 static void exfat_free_dir_list(struct exfat *exfat)
 207 {
 208         struct exfat_inode *dir, *i;
 209
 210         list_for_each_entry_safe(dir, i, &exfat->dir_list, list) {
 211                 inode_free_file_children(dir);
 212                 list_del(&dir->list);
 213                 free_exfat_inode(dir);
 214         }
 215 }
 216
 217 static inline bool exfat_invalid_clus(struct exfat *exfat, clus_t clus)
 218 {
 219         return clus < EXFAT_FIRST_CLUSTER ||
 220         (clus - EXFAT_FIRST_CLUSTER) > le32_to_cpu(exfat->bs->bsx.clu_count);
 221 }
 222
 223 static int inode_get_clus_next(struct exfat *exfat, struct exfat_inode *node,
 224                                 clus_t clus, clus_t *next)
 225 {
 226         off_t offset;
 227
 228         if (exfat_invalid_clus(exfat, clus))
 229                 return -EINVAL;
 230
 231         if (node->is_contiguous) {
 232                 *next = clus + 1;
 233                 return 0;
 234         }
 235
 236         offset = le32_to_cpu(exfat->bs->bsx.fat_offset) <<
 237                                 exfat->bs->bsx.sect_size_bits;
 238         offset += sizeof(clus_t) * clus;
 239
 240         if (exfat_read(exfat->blk_dev->dev_fd, next, sizeof(*next), offset)
 241                         != sizeof(*next))
 242                 return -EIO;
 243         *next = le32_to_cpu(*next);
 244         return 0;
 245 }
 246
 247 static bool inode_check_clus_chain(struct exfat *exfat, struct exfat_inode *node)
 248 {
 249         clus_t clus;
 250         clus_t clus_count;
 251
 252         clus = node->first_clus;
 253         clus_count = DIV_ROUND_UP(node->size, EXFAT_CLUSTER_SIZE(exfat->bs));
 254
 255         while (clus_count--) {
 256                 if (exfat_invalid_clus(exfat, clus)) {
 257                         exfat_err("bad cluster. 0x%x\n", clus);
 258                         return false;
 259                 }
 260
 261                 if (!EXFAT_BITMAP_GET(exfat->alloc_bitmap,
 262                                         clus - EXFAT_FIRST_CLUSTER)) {
 263                         exfat_err(
 264                                 "cluster allocated, but not in bitmap. 0x%x\n",
 265                                 clus);
 266                         return false;
 267                 }
 268
 269                 if (inode_get_clus_next(exfat, node, clus, &clus) != 0) {
 270                         exfat_err(
 271                                 "broken cluster chain. (previous cluster 0x%x)\n",
 272                                 clus);
 273                         return false;
 274                 }
 275         }
 276         return true;
 277 }
 278
 279 static bool inode_get_clus_count(struct exfat *exfat, struct exfat_inode *node,
 280                                                         clus_t *clus_count)
 281 {
 282         clus_t clus;
 283
 284         clus = node->first_clus;
 285         *clus_count = 0;
 286
 287         do {
 288                 if (exfat_invalid_clus(exfat, clus)) {
 289                         exfat_err("bad cluster. 0x%x\n", clus);
 290                         return false;
 291                 }
 292
 293                 if (inode_get_clus_next(exfat, node, clus, &clus) != 0) {
 294                         exfat_err(
 295                                 "broken cluster chain. (previous cluster 0x%x)\n",
 296                                 clus);
 297                         return false;
 298                 }
 299
 300                 (*clus_count)++;
 301         } while (clus != EXFAT_EOF_CLUSTER);
 302         return true;
 303 }
 304
 305 static off_t exfat_s2o(struct exfat *exfat, off_t sect)
 306 {
 307         return sect << exfat->bs->bsx.sect_size_bits;
 308 }
 309
 310 static off_t exfat_c2o(struct exfat *exfat, unsigned int clus)
 311 {
 312         if (clus < EXFAT_FIRST_CLUSTER)
 313                 return ~0L;
 314
 315         return exfat_s2o(exfat, le32_to_cpu(exfat->bs->bsx.clu_offset) +
 316                                 ((clus - EXFAT_FIRST_CLUSTER) <<
 317                                  exfat->bs->bsx.sect_per_clus_bits));
 318 }
 319
 320 static ssize_t exfat_file_read(struct exfat *exfat, struct exfat_inode *node,
 321                         void *buf, size_t total_size, off_t file_offset)
 322 {
 323         size_t clus_size;
 324         clus_t start_l_clus, l_clus, p_clus;
 325         unsigned int clus_offset;
 326         int ret;
 327         off_t device_offset;
 328         ssize_t read_size;
 329         size_t remain_size;
 330
 331         if (file_offset >= (off_t)node->size)
 332                 return EOF;
 333
 334         clus_size = EXFAT_CLUSTER_SIZE(exfat->bs);
 335         total_size = MIN(total_size, node->size - file_offset);
 336         remain_size = total_size;
 337
 338         if (remain_size == 0)
 339                 return 0;
 340
 341         start_l_clus = file_offset / clus_size;
 342         clus_offset = file_offset % clus_size;
 343         if (start_l_clus >= node->last_lclus &&
 344                         node->last_pclus != EXFAT_EOF_CLUSTER) {
 345                 l_clus = node->last_lclus;
 346                 p_clus = node->last_pclus;
 347         } else {
 348                 l_clus = 0;
 349                 p_clus = node->first_clus;
 350         }
 351
 352         while (p_clus != EXFAT_EOF_CLUSTER) {
 353                 if (exfat_invalid_clus(exfat, p_clus))
 354                         return -EINVAL;
 355                 if (l_clus < start_l_clus)
 356                         goto next_clus;
 357
 358                 read_size = MIN(remain_size, clus_size - clus_offset);
 359                 device_offset = exfat_c2o(exfat, p_clus) + clus_offset;
 360                 if (exfat_read(exfat->blk_dev->dev_fd, buf, read_size,
 361                                         device_offset) != read_size)
 362                         return -EIO;
 363
 364                 clus_offset = 0;
 365                 buf = (char *)buf + read_size;
 366                 remain_size -= read_size;
 367                 if (remain_size == 0)
 368                         goto out;
 369
 370 next_clus:
 371                 l_clus++;
 372                 ret = inode_get_clus_next(exfat, node, p_clus, &p_clus);
 373                 if (ret)
 374                         return ret;
 375         }
 376 out:
 377         node->last_lclus = l_clus;
 378         node->last_pclus = p_clus;
 379         return total_size - remain_size;
 380 }
 381
 382 static int boot_region_checksum(struct exfat *exfat)
 383 {
 384         __le32 checksum;
 385         unsigned short size;
 386         void *sect;
 387         unsigned int i;
 388
 389         size = EXFAT_SECTOR_SIZE(exfat->bs);
 390         sect = malloc(size);
 391         if (!sect)
 392                 return -ENOMEM;
 393
 394         checksum = 0;
 395
 396         boot_calc_checksum((unsigned char *)exfat->bs, size, true, &checksum);
 397         for (i = 1; i < 11; i++) {
 398                 if (exfat_read(exfat->blk_dev->dev_fd, sect, size, i * size) !=
 399                                 (ssize_t)size) {
 400                         free(sect);
 401                         return -EIO;
 402                 }
 403                 boot_calc_checksum(sect, size, false, &checksum);
 404         }
 405
 406         if (exfat_read(exfat->blk_dev->dev_fd, sect, size, i * size) !=
 407                         (ssize_t)size) {
 408                 free(sect);
 409                 return -EIO;
 410         }
 411         for (i = 0; i < size/sizeof(checksum); i++) {
 412                 if (le32_to_cpu(((__le32 *)sect)[i]) != checksum) {
 413                         union exfat_repair_context rctx = {
 414                                 .bs_checksum.checksum           = checksum,
 415                                 .bs_checksum.checksum_sect      = sect,
 416                         };
 417                         if (!exfat_repair(exfat, ER_BS_CHECKSUM, &rctx)) {
 418                                 exfat_err("invalid checksum. 0x%x\n",
 419                                         le32_to_cpu(((__le32 *)sect)[i]));
 420                                 free(sect);
 421                                 return -EIO;
 422                         }
 423                 }
 424         }
 425
 426         free(sect);
 427         return 0;
 428 }
 429
 430 static bool exfat_boot_region_check(struct exfat *exfat)
 431 {
 432         struct pbr *bs;
 433         ssize_t ret;
 434
 435         bs = (struct pbr *)malloc(sizeof(struct pbr));
 436         if (!bs) {
 437                 exfat_err("failed to allocate memory\n");
 438                 return false;
 439         }
 440
 441         exfat->bs = bs;
 442
 443         ret = exfat_read(exfat->blk_dev->dev_fd, bs, sizeof(*bs), 0);
 444         if (ret != sizeof(*bs)) {
 445                 exfat_err("failed to read a boot sector. %zd\n", ret);
 446                 goto err;
 447         }
 448
 449         if (memcmp(bs->bpb.oem_name, "EXFAT   ", 8) != 0) {
 450                 exfat_err("failed to find exfat file system.\n");
 451                 goto err;
 452         }
 453
 454         if (EXFAT_SECTOR_SIZE(bs) < 512 || EXFAT_SECTOR_SIZE(bs) > 4 * KB) {
 455                 exfat_err("too small or big sector size: %d\n",
 456                                 EXFAT_SECTOR_SIZE(bs));
 457                 goto err;
 458         }
 459
 460         if (EXFAT_CLUSTER_SIZE(bs) > 32 * MB) {
 461                 exfat_err("too big cluster size: %d\n", EXFAT_CLUSTER_SIZE(bs));
 462                 goto err;
 463         }
 464
 465         ret = boot_region_checksum(exfat);
 466         if (ret) {
 467                 exfat_err("failed to verify the checksum of a boot region. %zd\n",
 468                         ret);
 469                 goto err;
 470         }
 471
 472         if (bs->bsx.fs_version[1] != 1 || bs->bsx.fs_version[0] != 0) {
 473                 exfat_err("unsupported exfat version: %d.%d\n",
 474                                 bs->bsx.fs_version[1], bs->bsx.fs_version[0]);
 475                 goto err;
 476         }
 477
 478         if (bs->bsx.num_fats != 1) {
 479                 exfat_err("unsupported FAT count: %d\n", bs->bsx.num_fats);
 480                 goto err;
 481         }
 482
 483         if (le64_to_cpu(bs->bsx.vol_length) * EXFAT_SECTOR_SIZE(bs) >
 484                         exfat->blk_dev->size) {
 485                 exfat_err("too large sector count: %" PRIu64 "\n, expected: %llu\n",
 486                                 le64_to_cpu(bs->bsx.vol_length),
 487                                 exfat->blk_dev->num_sectors);
 488                 goto err;
 489         }
 490
 491         if (le32_to_cpu(bs->bsx.clu_count) * EXFAT_CLUSTER_SIZE(bs) >
 492                         exfat->blk_dev->size) {
 493                 exfat_err("too large cluster count: %u, expected: %u\n",
 494                                 le32_to_cpu(bs->bsx.clu_count),
 495                                 exfat->blk_dev->num_clusters);
 496                 goto err;
 497         }
 498
 499         return true;
 500 err:
 501         free(bs);
 502         exfat->bs = NULL;
 503         return false;
 504 }
 505
 506 static size_t utf16_len(const __le16 *str, size_t max_size)
 507 {
 508         size_t i = 0;
 509
 510         while (le16_to_cpu(str[i]) && i < max_size)
 511                 i++;
 512         return i;
 513 }
 514
 515 /*
 516  * get references of ancestors that include @child until the count of
 517  * ancesters is not larger than @count and the count of characters of
 518  * their names is not larger than @max_char_len.
 519  * return true if root is reached.
 520  */
 521 bool get_ancestors(struct exfat_inode *child,
 522                 struct exfat_inode **ancestors, int count,
 523                 int max_char_len,
 524                 int *ancestor_count)
 525 {
 526         struct exfat_inode *dir;
 527         int name_len, char_len;
 528         int root_depth, depth, i;
 529
 530         root_depth = 0;
 531         char_len = 0;
 532         max_char_len += 1;
 533
 534         dir = child;
 535         while (dir) {
 536                 name_len = utf16_len(dir->name, NAME_BUFFER_SIZE);
 537                 if (char_len + name_len > max_char_len)
 538                         break;
 539
 540                 /* include '/' */
 541                 char_len += name_len + 1;
 542                 root_depth++;
 543
 544                 dir = dir->parent;
 545         }
 546
 547         depth = MIN(root_depth, count);
 548
 549         for (dir = child, i = depth - 1; i >= 0; dir = dir->parent, i--)
 550                 ancestors[i] = dir;
 551
 552         *ancestor_count = depth;
 553         return dir == NULL;
 554 }
 555
 556 static int resolve_path(struct path_resolve_ctx *ctx, struct exfat_inode *child)
 557 {
 558         int depth, i;
 559         int name_len;
 560         __le16 *utf16_path;
 561         const __le16 utf16_slash = cpu_to_le16(0x002F);
 562         size_t in_size;
 563
 564         ctx->local_path[0] = '\0';
 565
 566         get_ancestors(child,
 567                         ctx->ancestors,
 568                         sizeof(ctx->ancestors) / sizeof(ctx->ancestors[0]),
 569                         PATH_MAX,
 570                         &depth);
 571
 572         utf16_path = ctx->utf16_path;
 573         for (i = 0; i < depth; i++) {
 574                 name_len = utf16_len(ctx->ancestors[i]->name, NAME_BUFFER_SIZE);
 575                 memcpy((char *)utf16_path, (char *)ctx->ancestors[i]->name,
 576                                 name_len * 2);
 577                 utf16_path += name_len;
 578                 memcpy((char *)utf16_path, &utf16_slash, sizeof(utf16_slash));
 579                 utf16_path++;
 580         }
 581
 582         if (depth > 0)
 583                 utf16_path--;
 584         in_size = (utf16_path - ctx->utf16_path) * sizeof(__le16);
 585         return exfat_utf16_dec(ctx->utf16_path, in_size,
 586                                 ctx->local_path, sizeof(ctx->local_path));
 587 }
 588
 589 static int resolve_path_parent(struct path_resolve_ctx *ctx,
 590                         struct exfat_inode *parent, struct exfat_inode *child)
 591 {
 592         int ret;
 593         struct exfat_inode *old;
 594
 595         old = child->parent;
 596         child->parent = parent;
 597
 598         ret = resolve_path(ctx, child);
 599         child->parent = old;
 600         return ret;
 601 }
 602
 603 static int exfat_de_iter_init(struct exfat_de_iter *iter, struct exfat *exfat,
 604                                                 struct exfat_inode *dir)
 605 {
 606         ssize_t ret;
 607
 608         if (!iter->dentries) {
 609                 iter->read_size = EXFAT_CLUSTER_SIZE(exfat->bs);
 610                 iter->dentries = malloc(iter->read_size * 2);
 611                 if (!iter->dentries) {
 612                         exfat_err("failed to allocate memory\n");
 613                         return -ENOMEM;
 614                 }
 615         }
 616
 617         ret = exfat_file_read(exfat, dir, iter->dentries, iter->read_size, 0);
 618         if (ret != iter->read_size) {
 619                 exfat_err("failed to read directory entries.\n");
 620                 return -EIO;
 621         }
 622
 623         iter->exfat = exfat;
 624         iter->parent = dir;
 625         iter->de_file_offset = 0;
 626         iter->next_read_offset = iter->read_size;
 627         iter->max_skip_dentries = 0;
 628         return 0;
 629 }
 630
 631 static int exfat_de_iter_get(struct exfat_de_iter *iter,
 632                                 int ith, struct exfat_dentry **dentry)
 633 {
 634         off_t de_next_file_offset;
 635         unsigned int de_next_offset;
 636         bool need_read_1_clus = false;
 637         int ret;
 638
 639         de_next_file_offset = iter->de_file_offset +
 640                         ith * sizeof(struct exfat_dentry);
 641
 642         if (de_next_file_offset + sizeof(struct exfat_dentry) >
 643                 round_down(iter->parent->size, sizeof(struct exfat_dentry)))
 644                 return EOF;
 645
 646         /*
 647          * dentry must be in current cluster, or next cluster which
 648          * will be read
 649          */
 650         if (de_next_file_offset -
 651                 (iter->de_file_offset / iter->read_size) * iter->read_size >=
 652                 iter->read_size * 2)
 653                 return -ERANGE;
 654
 655         de_next_offset = de_next_file_offset % (iter->read_size * 2);
 656
 657         /* read a cluster if needed */
 658         if (de_next_file_offset >= iter->next_read_offset) {
 659                 void *buf;
 660
 661                 need_read_1_clus = de_next_offset < iter->read_size;
 662                 buf = need_read_1_clus ?
 663                         iter->dentries : iter->dentries + iter->read_size;
 664
 665                 ret = exfat_file_read(iter->exfat, iter->parent, buf,
 666                         iter->read_size, iter->next_read_offset);
 667                 if (ret == EOF) {
 668                         return EOF;
 669                 } else if (ret <= 0) {
 670                         exfat_err("failed to read a cluster. %d\n", ret);
 671                         return ret;
 672                 }
 673                 iter->next_read_offset += iter->read_size;
 674         }
 675
 676         if (ith + 1 > iter->max_skip_dentries)
 677                 iter->max_skip_dentries = ith + 1;
 678
 679         *dentry = (struct exfat_dentry *) (iter->dentries + de_next_offset);
 680         return 0;
 681 }
 682
 683 /*
 684  * @skip_dentries must be the largest @ith + 1 of exfat_de_iter_get
 685  * since the last call of exfat_de_iter_advance
 686  */
 687 static int exfat_de_iter_advance(struct exfat_de_iter *iter, int skip_dentries)
 688 {
 689         if (skip_dentries != iter->max_skip_dentries)
 690                 return -EINVAL;
 691
 692         iter->max_skip_dentries = 0;
 693         iter->de_file_offset = iter->de_file_offset +
 694                                 skip_dentries * sizeof(struct exfat_dentry);
 695         return 0;
 696 }
 697
 698 static off_t exfat_de_iter_file_offset(struct exfat_de_iter *iter)
 699 {
 700         return iter->de_file_offset;
 701 }
 702
 703 static bool check_inode(struct exfat *exfat, struct exfat_inode *parent,
 704                                                 struct exfat_inode *node)
 705 {
 706         bool ret = false;
 707
 708         if (node->size == 0 && node->first_clus != EXFAT_FREE_CLUSTER) {
 709                 resolve_path_parent(&path_resolve_ctx, parent, node);
 710                 exfat_err("file is empty, but first cluster is %#x: %s\n",
 711                                 node->first_clus, path_resolve_ctx.local_path);
 712                 ret = false;
 713         }
 714
 715         if (node->size > 0 && exfat_invalid_clus(exfat, node->first_clus)) {
 716                 resolve_path_parent(&path_resolve_ctx, parent, node);
 717                 exfat_err("first cluster %#x is invalid: %s\n",
 718                                 node->first_clus, path_resolve_ctx.local_path);
 719                 ret = false;
 720         }
 721
 722         if (node->size > le32_to_cpu(exfat->bs->bsx.clu_count) *
 723                                 EXFAT_CLUSTER_SIZE(exfat->bs)) {
 724                 resolve_path_parent(&path_resolve_ctx, parent, node);
 725                 exfat_err("size %" PRIu64 " is greater than cluster heap: %s\n",
 726                                 node->size, path_resolve_ctx.local_path);
 727                 ret = false;
 728         }
 729
 730         if (node->size == 0 && node->is_contiguous) {
 731                 resolve_path_parent(&path_resolve_ctx, parent, node);
 732                 exfat_err("empty, but marked as contiguous: %s\n",
 733                                         path_resolve_ctx.local_path);
 734                 ret = false;
 735         }
 736
 737         if ((node->attr & ATTR_SUBDIR) &&
 738                         node->size % EXFAT_CLUSTER_SIZE(exfat->bs) != 0) {
 739                 resolve_path_parent(&path_resolve_ctx, parent, node);
 740                 exfat_err("directory size %" PRIu64 " is not divisible by %d: %s\n",
 741                                 node->size, EXFAT_CLUSTER_SIZE(exfat->bs),
 742                                 path_resolve_ctx.local_path);
 743                 ret = false;
 744         }
 745
 746         if (!node->is_contiguous && !inode_check_clus_chain(exfat, node)) {
 747                 resolve_path_parent(&path_resolve_ctx, parent, node);
 748                 exfat_err("corrupted cluster chain: %s\n",
 749                                 path_resolve_ctx.local_path);
 750                 ret = false;
 751         }
 752
 753         return ret;
 754 }
 755
 756 static void dentry_calc_checksum(struct exfat_dentry *dentry,
 757                                 __le16 *checksum, bool primary)
 758 {
 759         unsigned int i;
 760         uint8_t *bytes;
 761
 762         bytes = (uint8_t *)dentry;
 763
 764         *checksum = ((*checksum << 15) | (*checksum >> 1)) + bytes[0];
 765         *checksum = ((*checksum << 15) | (*checksum >> 1)) + bytes[1];
 766
 767         i = primary ? 4 : 2;
 768         for (; i < sizeof(*dentry); i++) {
 769                 *checksum = ((*checksum << 15) | (*checksum >> 1)) + bytes[i];
 770         }
 771 }
 772
 773 static __le16 file_calc_checksum(struct exfat_de_iter *iter)
 774 {
 775         __le16 checksum;
 776         struct exfat_dentry *file_de, *de;
 777         int i;
 778
 779         checksum = 0;
 780         exfat_de_iter_get(iter, 0, &file_de);
 781
 782         dentry_calc_checksum(file_de, &checksum, true);
 783         for (i = 1; i <= file_de->file_num_ext; i++) {
 784                 exfat_de_iter_get(iter, i, &de);
 785                 dentry_calc_checksum(de, &checksum, false);
 786         }
 787
 788         return checksum;
 789 }
 790
 791 static int read_file_dentries(struct exfat_de_iter *iter,
 792                         struct exfat_inode **new_node, int *skip_dentries)
 793 {
 794         struct exfat_dentry *file_de, *stream_de, *name_de;
 795         struct exfat_inode *node;
 796         int i, ret;
 797         __le16 checksum;
 798
 799         /* TODO: mtime, atime, ... */
 800
 801         ret = exfat_de_iter_get(iter, 0, &file_de);
 802         if (ret || file_de->type != EXFAT_FILE) {
 803                 exfat_err("failed to get file dentry. %d\n", ret);
 804                 return -EINVAL;
 805         }
 806         ret = exfat_de_iter_get(iter, 1, &stream_de);
 807         if (ret || stream_de->type != EXFAT_STREAM) {
 808                 exfat_err("failed to get stream dentry. %d\n", ret);
 809                 return -EINVAL;
 810         }
 811
 812         *new_node = NULL;
 813         node = alloc_exfat_inode(le16_to_cpu(file_de->file_attr));
 814         if (!node)
 815                 return -ENOMEM;
 816
 817         if (file_de->file_num_ext < 2) {
 818                 exfat_err("too few secondary count. %d\n",
 819                                 file_de->file_num_ext);
 820                 free_exfat_inode(node);
 821                 return -EINVAL;
 822         }
 823
 824         for (i = 2; i <= file_de->file_num_ext; i++) {
 825                 ret = exfat_de_iter_get(iter, i, &name_de);
 826                 if (ret || name_de->type != EXFAT_NAME) {
 827                         exfat_err("failed to get name dentry. %d\n", ret);
 828                         ret = -EINVAL;
 829                         goto err;
 830                 }
 831
 832                 memcpy(node->name +
 833                         (i-2) * ENTRY_NAME_MAX, name_de->name_unicode,
 834                         sizeof(name_de->name_unicode));
 835         }
 836
 837         checksum = file_calc_checksum(iter);
 838         if (le16_to_cpu(file_de->file_checksum) != checksum) {
 839                 exfat_err("invalid checksum. 0x%x != 0x%x\n",
 840                         le16_to_cpu(file_de->file_checksum),
 841                         le16_to_cpu(checksum));
 842                 ret = -EINVAL;
 843                 goto err;
 844         }
 845
 846         node->size = le64_to_cpu(stream_de->stream_size);
 847         node->first_clus = le32_to_cpu(stream_de->stream_start_clu);
 848         node->is_contiguous =
 849                 ((stream_de->stream_flags & EXFAT_SF_CONTIGUOUS) != 0);
 850
 851         if (le64_to_cpu(stream_de->stream_valid_size) > node->size) {
 852                 resolve_path_parent(&path_resolve_ctx, iter->parent, node);
 853                 exfat_err("valid size %" PRIu64 " greater than size %" PRIu64 ": %s\n",
 854                         le64_to_cpu(stream_de->stream_valid_size), node->size,
 855                         path_resolve_ctx.local_path);
 856                 ret = -EINVAL;
 857                 goto err;
 858         }
 859
 860         *skip_dentries = (file_de->file_num_ext + 1);
 861         *new_node = node;
 862         return 0;
 863 err:
 864         *skip_dentries = 0;
 865         *new_node = NULL;
 866         free_exfat_inode(node);
 867         return ret;
 868 }
 869
 870 static int read_file(struct exfat_de_iter *de_iter,
 871                 struct exfat_inode **new_node, int *dentry_count)
 872 {
 873         struct exfat_inode *node;
 874         int ret;
 875
 876         *new_node = NULL;
 877
 878         ret = read_file_dentries(de_iter, &node, dentry_count);
 879         if (ret) {
 880                 exfat_err("corrupted file directory entries.\n");
 881                 return ret;
 882         }
 883
 884         ret = check_inode(de_iter->exfat, de_iter->parent, node);
 885         if (ret) {
 886                 exfat_err("corrupted file directory entries.\n");
 887                 free_exfat_inode(node);
 888                 return ret;
 889         }
 890
 891         node->dentry_file_offset = exfat_de_iter_file_offset(de_iter);
 892         *new_node = node;
 893         return 0;
 894 }
 895
 896 static bool read_volume_label(struct exfat_de_iter *iter)
 897 {
 898         struct exfat *exfat;
 899         struct exfat_dentry *dentry;
 900         __le16 disk_label[VOLUME_LABEL_MAX_LEN];
 901
 902         exfat = iter->exfat;
 903         if (exfat_de_iter_get(iter, 0, &dentry))
 904                 return false;
 905
 906         if (dentry->vol_char_cnt == 0)
 907                 return true;
 908
 909         if (dentry->vol_char_cnt > VOLUME_LABEL_MAX_LEN) {
 910                 exfat_err("too long label. %d\n", dentry->vol_char_cnt);
 911                 return false;
 912         }
 913
 914         memcpy(disk_label, dentry->vol_label, sizeof(disk_label));
 915         if (exfat_utf16_dec(disk_label, dentry->vol_char_cnt*2,
 916                 exfat->volume_label, sizeof(exfat->volume_label)) < 0) {
 917                 exfat_err("failed to decode volume label\n");
 918                 return false;
 919         }
 920
 921         exfat_info("volume label [%s]\n", exfat->volume_label);
 922         return true;
 923 }
 924
 925 static bool read_alloc_bitmap(struct exfat_de_iter *iter)
 926 {
 927         struct exfat_dentry *dentry;
 928         struct exfat *exfat;
 929         ssize_t alloc_bitmap_size;
 930
 931         exfat = iter->exfat;
 932         if (exfat_de_iter_get(iter, 0, &dentry))
 933                 return false;
 934
 935         exfat_debug("start cluster %#x, size %#" PRIx64 "\n",
 936                         le32_to_cpu(dentry->bitmap_start_clu),
 937                         le64_to_cpu(dentry->bitmap_size));
 938
 939         exfat->bit_count = le32_to_cpu(exfat->bs->bsx.clu_count);
 940
 941         if (le64_to_cpu(dentry->bitmap_size) <
 942                         DIV_ROUND_UP(exfat->bit_count, 8)) {
 943                 exfat_err("invalid size of allocation bitmap. 0x%" PRIx64 "\n",
 944                                 le64_to_cpu(dentry->bitmap_size));
 945                 return false;
 946         }
 947         if (exfat_invalid_clus(exfat, le32_to_cpu(dentry->bitmap_start_clu))) {
 948                 exfat_err("invalid start cluster of allocate bitmap. 0x%x\n",
 949                                 le32_to_cpu(dentry->bitmap_start_clu));
 950                 return false;
 951         }
 952
 953         /* TODO: bitmap could be very large. */
 954         alloc_bitmap_size = EXFAT_BITMAP_SIZE(exfat->bit_count);
 955         exfat->alloc_bitmap = (__u32 *)malloc(alloc_bitmap_size);
 956         if (!exfat->alloc_bitmap) {
 957                 exfat_err("failed to allocate bitmap\n");
 958                 return false;
 959         }
 960
 961         if (exfat_read(exfat->blk_dev->dev_fd,
 962                         exfat->alloc_bitmap, alloc_bitmap_size,
 963                         exfat_c2o(exfat,
 964                         le32_to_cpu(dentry->bitmap_start_clu))) !=
 965                         alloc_bitmap_size) {
 966                 exfat_err("failed to read bitmap\n");
 967                 free(exfat->alloc_bitmap);
 968                 exfat->alloc_bitmap = NULL;
 969                 return false;
 970         }
 971
 972         return true;
 973 }
 974
 975 static bool read_upcase_table(struct exfat_de_iter *iter)
 976 {
 977         struct exfat_dentry *dentry;
 978         struct exfat *exfat;
 979         ssize_t size;
 980         __le16 *upcase;
 981         __le32 checksum;
 982
 983         exfat = iter->exfat;
 984
 985         if (exfat_de_iter_get(iter, 0, &dentry))
 986                 return false;
 987
 988         if (exfat_invalid_clus(exfat, le32_to_cpu(dentry->upcase_start_clu))) {
 989                 exfat_err("invalid start cluster of upcase table. 0x%x\n",
 990                         le32_to_cpu(dentry->upcase_start_clu));
 991                 return false;
 992         }
 993
 994         size = (ssize_t)le64_to_cpu(dentry->upcase_size);
 995         if (size > (ssize_t)(EXFAT_MAX_UPCASE_CHARS * sizeof(__le16)) ||
 996                         size == 0 || size % sizeof(__le16)) {
 997                 exfat_err("invalid size of upcase table. 0x%" PRIx64 "\n",
 998                         le64_to_cpu(dentry->upcase_size));
 999                 return false;
1000         }
1001
1002         upcase = (__le16 *)malloc(size);
1003         if (!upcase) {
1004                 exfat_err("failed to allocate upcase table\n");
1005                 return false;
1006         }
1007
1008         if (exfat_read(exfat->blk_dev->dev_fd, upcase, size,
1009                         exfat_c2o(exfat,
1010                         le32_to_cpu(dentry->upcase_start_clu))) != size) {
1011                 exfat_err("failed to read upcase table\n");
1012                 free(upcase);
1013                 return false;
1014         }
1015
1016         checksum = 0;
1017         boot_calc_checksum((unsigned char *)upcase, size, false, &checksum);
1018         if (le32_to_cpu(dentry->upcase_checksum) != checksum) {
1019                 exfat_err("corrupted upcase table %#x (expected: %#x)\n",
1020                         checksum, le32_to_cpu(dentry->upcase_checksum));
1021                 free(upcase);
1022                 return false;
1023         }
1024
1025         free(upcase);
1026         return true;
1027 }
1028
1029 static int read_children(struct exfat *exfat, struct exfat_inode *dir)
1030 {
1031         int ret;
1032         struct exfat_inode *node = NULL;
1033         struct exfat_dentry *dentry;
1034         int dentry_count;
1035         struct list_head sub_dir_list;
1036         struct exfat_de_iter *de_iter;
1037
1038         INIT_LIST_HEAD(&sub_dir_list);
1039
1040         de_iter = &exfat->de_iter;
1041         ret = exfat_de_iter_init(de_iter, exfat, dir);
1042         if (ret == EOF)
1043                 return 0;
1044         else if (ret)
1045                 return ret;
1046
1047         while (1) {
1048                 ret = exfat_de_iter_get(de_iter, 0, &dentry);
1049                 if (ret == EOF) {
1050                         break;
1051                 } else if (ret) {
1052                         exfat_err("failed to get a dentry. %d\n", ret);
1053                         goto err;
1054                 }
1055
1056                 dentry_count = 1;
1057
1058                 switch (dentry->type) {
1059                 case EXFAT_FILE:
1060                         ret = read_file(de_iter, &node, &dentry_count);
1061                         if (ret) {
1062                                 exfat_err("failed to verify file. %d\n", ret);
1063                                 goto err;
1064                         }
1065
1066                         if ((node->attr & ATTR_SUBDIR) && node->size) {
1067                                 node->parent = dir;
1068                                 list_add_tail(&node->sibling, &dir->children);
1069                                 list_add_tail(&node->list, &sub_dir_list);
1070                         } else
1071                                 free_exfat_inode(node);
1072                         break;
1073                 case EXFAT_VOLUME:
1074                         if (!read_volume_label(de_iter)) {
1075                                 exfat_err("failed to verify volume label\n");
1076                                 ret = -EINVAL;
1077                                 goto err;
1078                         }
1079                         break;
1080                 case EXFAT_BITMAP:
1081                         if (!read_alloc_bitmap(de_iter)) {
1082                                 exfat_err(
1083                                         "failed to verify allocation bitmap\n");
1084                                 ret = -EINVAL;
1085                                 goto err;
1086                         }
1087                         break;
1088                 case EXFAT_UPCASE:
1089                         if (!read_upcase_table(de_iter)) {
1090                                 exfat_err(
1091                                         "failed to verify upcase table\n");
1092                                 ret = -EINVAL;
1093                                 goto err;
1094                         }
1095                         break;
1096                 default:
1097                         if (IS_EXFAT_DELETED(dentry->type) ||
1098                                         (dentry->type == EXFAT_UNUSED))
1099                                 break;
1100                         exfat_err("unknown entry type. 0x%x\n", dentry->type);
1101                         ret = -EINVAL;
1102                         goto err;
1103                 }
1104
1105                 exfat_de_iter_advance(de_iter, dentry_count);
1106         }
1107         list_splice(&sub_dir_list, &exfat->dir_list);
1108         return 0;
1109 err:
1110         inode_free_children(dir, false);
1111         INIT_LIST_HEAD(&dir->children);
1112         return ret;
1113 }
1114
1115 /*
1116  * for each directory in @dir_list.
1117  * 1. read all dentries and allocate exfat_nodes for files and directories.
1118  *    and append directory exfat_nodes to the head of @dir_list
1119  * 2. free all of file exfat_nodes.
1120  * 3. if the directory does not have children, free its exfat_node.
1121  */
1122 static bool exfat_filesystem_check(struct exfat *exfat)
1123 {
1124         struct exfat_inode *dir;
1125         bool ret = true;
1126
1127         if (!exfat->root) {
1128                 exfat_err("root is NULL\n");
1129                 return false;
1130         }
1131
1132         list_add(&exfat->root->list, &exfat->dir_list);
1133
1134         while (!list_empty(&exfat->dir_list)) {
1135                 dir = list_entry(exfat->dir_list.next, struct exfat_inode, list);
1136
1137                 if (!(dir->attr & ATTR_SUBDIR)) {
1138                         resolve_path(&path_resolve_ctx, dir);
1139                         ret = false;
1140                         exfat_err("failed to travel directories. "
1141                                         "the node is not directory: %s\n",
1142                                         path_resolve_ctx.local_path);
1143                         goto out;
1144                 }
1145
1146                 if (read_children(exfat, dir)) {
1147                         resolve_path(&path_resolve_ctx, dir);
1148                         ret = false;
1149                         exfat_err("failed to check dentries: %s\n",
1150                                         path_resolve_ctx.local_path);
1151                         goto out;
1152                 }
1153
1154                 list_del(&dir->list);
1155                 inode_free_file_children(dir);
1156                 inode_free_ancestors(dir);
1157         }
1158 out:
1159         exfat_free_dir_list(exfat);
1160         exfat->root = NULL;
1161         return ret;
1162 }
1163
1164 static bool exfat_root_dir_check(struct exfat *exfat)
1165 {
1166         struct exfat_inode *root;
1167         clus_t clus_count;
1168
1169         root = alloc_exfat_inode(ATTR_SUBDIR);
1170         if (!root) {
1171                 exfat_err("failed to allocate memory\n");
1172                 return false;
1173         }
1174
1175         root->first_clus = le32_to_cpu(exfat->bs->bsx.root_cluster);
1176         if (!inode_get_clus_count(exfat, root, &clus_count)) {
1177                 exfat_err("failed to follow the cluster chain of root\n");
1178                 goto err;
1179         }
1180         root->size = clus_count * EXFAT_CLUSTER_SIZE(exfat->bs);
1181
1182         exfat->root = root;
1183         exfat_debug("root directory: start cluster[0x%x] size[0x%" PRIx64 "]\n",
1184                 root->first_clus, root->size);
1185         return true;
1186 err:
1187         free_exfat_inode(root);
1188         exfat->root = NULL;
1189         return false;
1190 }
1191
1192 void exfat_show_info(struct exfat *exfat)
1193 {
1194         exfat_info("Bytes per sector: %d\n",
1195                         1 << exfat->bs->bsx.sect_size_bits);
1196         exfat_info("Sectors per cluster: %d\n",
1197                         1 << exfat->bs->bsx.sect_per_clus_bits);
1198         exfat_info("Cluster heap count: %d(0x%x)\n",
1199                         le32_to_cpu(exfat->bs->bsx.clu_count),
1200                         le32_to_cpu(exfat->bs->bsx.clu_count));
1201         exfat_info("Cluster heap offset: %#x\n",
1202                         le32_to_cpu(exfat->bs->bsx.clu_offset));
1203 }
1204
1205 void exfat_show_stat(void)
1206 {
1207         exfat_debug("Found directories: %ld\n", exfat_stat.dir_count);
1208         exfat_debug("Found files: %ld\n", exfat_stat.file_count);
1209         exfat_debug("Found leak directories: %ld\n",
1210                         exfat_stat.dir_count - exfat_stat.dir_free_count);
1211         exfat_debug("Found leak files: %ld\n",
1212                         exfat_stat.file_count - exfat_stat.file_free_count);
1213 }
1214
1215 int main(int argc, char * const argv[])
1216 {
1217         int c, ret;
1218         struct fsck_user_input ui;
1219         struct exfat_blk_dev bd;
1220         struct exfat *exfat = NULL;
1221         bool version_only = false;
1222
1223         memset(&ui, 0, sizeof(ui));
1224         memset(&bd, 0, sizeof(bd));
1225
1226         print_level = EXFAT_ERROR;
1227
1228         if (!setlocale(LC_CTYPE, ""))
1229                 exfat_err("failed to init locale/codeset\n");
1230
1231         opterr = 0;
1232         while ((c = getopt_long(argc, argv, "rynVvh", opts, NULL)) != EOF) {
1233                 switch (c) {
1234                 case 'n':
1235                         if (ui.options & FSCK_OPTS_REPAIR)
1236                                 usage(argv[0]);
1237                         ui.options |= FSCK_OPTS_REPAIR_NO;
1238                         ui.ei.writeable = false;
1239                         break;
1240                 case 'r':
1241                         if (ui.options & FSCK_OPTS_REPAIR)
1242                                 usage(argv[0]);
1243                         ui.options |= FSCK_OPTS_REPAIR_ASK;
1244                         ui.ei.writeable = true;
1245                         break;
1246                 case 'y':
1247                         if (ui.options & FSCK_OPTS_REPAIR)
1248                                 usage(argv[0]);
1249                         ui.options |= FSCK_OPTS_REPAIR_YES;
1250                         ui.ei.writeable = true;
1251                         break;
1252                 case 'V':
1253                         version_only = true;
1254                         break;
1255                 case 'v':
1256                         if (print_level < EXFAT_DEBUG)
1257                                 print_level++;
1258                         break;
1259                 case '?':
1260                 case 'h':
1261                 default:
1262                         usage(argv[0]);
1263                 }
1264         }
1265
1266         show_version();
1267         if (version_only)
1268                 exit(FSCK_EXIT_SYNTAX_ERROR);
1269
1270         if (optind != argc - 1)
1271                 usage(argv[0]);
1272
1273         snprintf(ui.ei.dev_name, sizeof(ui.ei.dev_name), "%s", argv[optind]);
1274         ret = exfat_get_blk_dev_info(&ui.ei, &bd);
1275         if (ret < 0) {
1276                 exfat_err("failed to open %s. %d\n", ui.ei.dev_name, ret);
1277                 return FSCK_EXIT_OPERATION_ERROR;
1278         }
1279
1280         exfat = alloc_exfat(&bd);
1281         if (!exfat) {
1282                 ret = FSCK_EXIT_OPERATION_ERROR;
1283                 goto err;
1284         }
1285         exfat->options = ui.options;
1286
1287         exfat_debug("verifying boot regions...\n");
1288         if (!exfat_boot_region_check(exfat)) {
1289                 exfat_err("failed to verify boot regions.\n");
1290                 ret = FSCK_EXIT_ERRORS_LEFT;
1291                 goto err;
1292         }
1293
1294         exfat_show_info(exfat);
1295
1296         exfat_debug("verifying root directory...\n");
1297         if (!exfat_root_dir_check(exfat)) {
1298                 exfat_err("failed to verify root directory.\n");
1299                 ret = FSCK_EXIT_ERRORS_LEFT;
1300                 goto out;
1301         }
1302
1303         exfat_debug("verifying directory entries...\n");
1304         if (!exfat_filesystem_check(exfat)) {
1305                 exfat_err("failed to verify directory entries.\n");
1306                 ret = FSCK_EXIT_ERRORS_LEFT;
1307                 goto out;
1308         }
1309
1310         if (ui.ei.writeable)
1311                 fsync(bd.dev_fd);
1312         printf("%s: clean\n", ui.ei.dev_name);
1313         ret = FSCK_EXIT_NO_ERRORS;
1314 out:
1315         exfat_show_stat();
1316 err:
1317         free_exfat(exfat);
1318         close(bd.dev_fd);
1319         return ret;
1320 }