libexfat/cluster.c

   1 /*
   2  *  cluster.c
   3  *  exFAT file system implementation library.
   4  *
   5  *  Created by Andrew Nayenko on 03.09.09.
   6  *  This software is distributed under the GNU General Public License
   7  *  version 3 or any later.
   8  */
   9
  10 #include "exfat.h"
  11 #include <errno.h>
  12 #include <string.h>
  13
  14 #define BMAP_GET(bitmap, index) ((bitmap)[(index) / 8] & (1u << ((index) % 8)))
  15 #define BMAP_SET(bitmap, index) (bitmap)[(index) / 8] |= (1u << ((index) % 8))
  16 #define BMAP_CLR(bitmap, index) (bitmap)[(index) / 8] &= ~(1u << ((index) % 8))
  17
  18 /*
  19  * Cluster to block.
  20  */
  21 static uint32_t c2b(const struct exfat* ef, cluster_t cluster)
  22 {
  23         if (cluster < EXFAT_FIRST_DATA_CLUSTER)
  24                 exfat_bug("invalid cluster number %u", cluster);
  25         return le32_to_cpu(ef->sb->cluster_block_start) +
  26                 ((cluster - EXFAT_FIRST_DATA_CLUSTER) << ef->sb->bpc_bits);
  27 }
  28
  29 /*
  30  * Cluster to absolute offset.
  31  */
  32 off_t exfat_c2o(const struct exfat* ef, cluster_t cluster)
  33 {
  34         return (off_t) c2b(ef, cluster) << ef->sb->block_bits;
  35 }
  36
  37 /*
  38  * Block to absolute offset.
  39  */
  40 static off_t b2o(const struct exfat* ef, uint32_t block)
  41 {
  42         return (off_t) block << ef->sb->block_bits;
  43 }
  44
  45 /*
  46  * Size in bytes to size in clusters (rounded upwards).
  47  */
  48 static uint32_t bytes2clusters(const struct exfat* ef, uint64_t bytes)
  49 {
  50         uint64_t cluster_size = CLUSTER_SIZE(*ef->sb);
  51         return (bytes + cluster_size - 1) / cluster_size;
  52 }
  53
  54 cluster_t exfat_next_cluster(const struct exfat* ef,
  55                 const struct exfat_node* node, cluster_t cluster)
  56 {
  57         cluster_t next;
  58         off_t fat_offset;
  59
  60         if (cluster < EXFAT_FIRST_DATA_CLUSTER)
  61                 exfat_bug("bad cluster 0x%x", cluster);
  62
  63         if (IS_CONTIGUOUS(*node))
  64                 return cluster + 1;
  65         fat_offset = b2o(ef, le32_to_cpu(ef->sb->fat_block_start))
  66                 + cluster * sizeof(cluster_t);
  67         exfat_read_raw(&next, sizeof(next), fat_offset, ef->fd);
  68         return next;
  69 }
  70
  71 cluster_t exfat_advance_cluster(const struct exfat* ef,
  72                 const struct exfat_node* node, cluster_t cluster, uint32_t count)
  73 {
  74         uint32_t i;
  75
  76         for (i = 0; i < count; i++)
  77         {
  78                 cluster = exfat_next_cluster(ef, node, cluster);
  79                 if (CLUSTER_INVALID(cluster))
  80                         break;
  81         }
  82         return cluster;
  83 }
  84
  85 static cluster_t find_bit_and_set(uint8_t* bitmap, cluster_t start,
  86                 cluster_t end)
  87 {
  88         const cluster_t mid_start = (start + 7) / 8 * 8;
  89         const cluster_t mid_end = end / 8 * 8;
  90         cluster_t c;
  91         cluster_t byte;
  92
  93         for (c = start; c < mid_start; c++)
  94                 if (BMAP_GET(bitmap, c) == 0)
  95                 {
  96                         BMAP_SET(bitmap, c);
  97                         return c + EXFAT_FIRST_DATA_CLUSTER;
  98                 }
  99
 100         for (byte = mid_start / 8; byte < mid_end / 8; byte++)
 101                 if (bitmap[byte] != 0xff)
 102                 {
 103                         cluster_t bit;
 104
 105                         for (bit = 0; bit < 8; bit++)
 106                                 if (!(bitmap[byte] & (1u << bit)))
 107                                 {
 108                                         bitmap[byte] |= (1u << bit);
 109                                         return byte * 8 + bit + EXFAT_FIRST_DATA_CLUSTER;
 110                                 }
 111                 }
 112
 113         for (c = mid_end; c < end; c++)
 114                 if (BMAP_GET(bitmap, c) == 0)
 115                 {
 116                         BMAP_SET(bitmap, c);
 117                         return c + EXFAT_FIRST_DATA_CLUSTER;
 118                 }
 119
 120         return EXFAT_CLUSTER_END;
 121 }
 122
 123 static void flush_cmap(struct exfat* ef)
 124 {
 125         exfat_write_raw(ef->cmap.chunk, (ef->cmap.chunk_size + 7) / 8,
 126                         exfat_c2o(ef, ef->cmap.start_cluster), ef->fd);
 127 }
 128
 129 static void set_next_cluster(const struct exfat* ef, int contiguous,
 130                 cluster_t current, cluster_t next)
 131 {
 132         off_t fat_offset;
 133
 134         if (contiguous)
 135                 return;
 136         fat_offset = b2o(ef, le32_to_cpu(ef->sb->fat_block_start))
 137                 + current * sizeof(cluster_t);
 138         exfat_write_raw(&next, sizeof(next), fat_offset, ef->fd);
 139 }
 140
 141 static void erase_cluster(struct exfat* ef, cluster_t cluster)
 142 {
 143         const int block_size = BLOCK_SIZE(*ef->sb);
 144         const int blocks_in_cluster = CLUSTER_SIZE(*ef->sb) / block_size;
 145         int i;
 146
 147         for (i = 0; i < blocks_in_cluster; i++)
 148                 exfat_write_raw(ef->zero_block, block_size,
 149                                 exfat_c2o(ef, cluster) + i * block_size, ef->fd);
 150 }
 151
 152 static cluster_t allocate_cluster(struct exfat* ef)
 153 {
 154         cluster_t cluster = find_bit_and_set(ef->cmap.chunk, 0,
 155                         ef->cmap.chunk_size);
 156
 157         if (cluster == EXFAT_CLUSTER_END)
 158         {
 159                 exfat_error("no free space left");
 160                 return EXFAT_CLUSTER_END;
 161         }
 162
 163         erase_cluster(ef, cluster);
 164         /* FIXME no need to flush immediately */
 165         flush_cmap(ef);
 166         /* FIXME update percentage of used space */
 167         return cluster;
 168 }
 169
 170 static void free_cluster(struct exfat* ef, cluster_t cluster)
 171 {
 172         if (CLUSTER_INVALID(cluster))
 173                 exfat_bug("attempting to free invalid cluster");
 174
 175         if (cluster < EXFAT_FIRST_DATA_CLUSTER)
 176                 exfat_bug("bad cluster 0x%x", cluster);
 177         BMAP_CLR(ef->cmap.chunk, cluster - EXFAT_FIRST_DATA_CLUSTER);
 178         /* FIXME no need to flush immediately */
 179         flush_cmap(ef);
 180 }
 181
 182 static void make_noncontiguous(const struct exfat* ef, cluster_t first,
 183                 cluster_t last)
 184 {
 185         cluster_t c;
 186
 187         for (c = first; c < last; c++)
 188                 set_next_cluster(ef, 0, c, c + 1);
 189 }
 190
 191 static int grow_file(struct exfat* ef, struct exfat_node* node,
 192                 uint32_t difference)
 193 {
 194         cluster_t previous;
 195         cluster_t next;
 196
 197         if (difference == 0)
 198                 exfat_bug("zero clusters count passed");
 199
 200         if (node->start_cluster != EXFAT_CLUSTER_FREE)
 201         {
 202                 /* get the last cluster of the file */
 203                 previous = exfat_advance_cluster(ef, node, node->start_cluster,
 204                                 bytes2clusters(ef, node->size) - 1);
 205                 if (CLUSTER_INVALID(previous))
 206                 {
 207                         exfat_error("invalid cluster in file");
 208                         return -EIO;
 209                 }
 210         }
 211         else
 212         {
 213                 /* file does not have clusters (i.e. is empty), allocate
 214                    the first one for it */
 215                 previous = allocate_cluster(ef);
 216                 if (CLUSTER_INVALID(previous))
 217                         return -ENOSPC;
 218                 node->start_cluster = previous;
 219                 difference--;
 220                 /* file consists of only one cluster, so it's contiguous */
 221                 node->flags |= EXFAT_ATTRIB_CONTIGUOUS;
 222         }
 223
 224         while (difference--)
 225         {
 226                 next = allocate_cluster(ef);
 227                 if (CLUSTER_INVALID(next))
 228                         return -ENOSPC;
 229                 if (next != previous - 1 && IS_CONTIGUOUS(*node))
 230                 {
 231                         /* it's a pity, but we are not able to keep the file contiguous
 232                            anymore */
 233                         make_noncontiguous(ef, node->start_cluster, previous);
 234                         node->flags &= ~EXFAT_ATTRIB_CONTIGUOUS;
 235                 }
 236                 set_next_cluster(ef, IS_CONTIGUOUS(*node), previous, next);
 237                 previous = next;
 238         }
 239
 240         set_next_cluster(ef, IS_CONTIGUOUS(*node), previous, EXFAT_CLUSTER_END);
 241         return 0;
 242 }
 243
 244 static int shrink_file(struct exfat* ef, struct exfat_node* node,
 245                 uint32_t difference)
 246 {
 247         uint32_t current = bytes2clusters(ef, node->size);
 248         cluster_t previous;
 249         cluster_t next;
 250
 251         if (difference == 0)
 252                 exfat_bug("zero difference passed");
 253         if (node->start_cluster == EXFAT_CLUSTER_FREE)
 254                 exfat_bug("unable to shrink empty file (%u clusters)", current);
 255         if (current < difference)
 256                 exfat_bug("file underflow (%u < %u)", current, difference);
 257
 258         /* crop the file */
 259         if (current > difference)
 260         {
 261                 cluster_t last = exfat_advance_cluster(ef, node, node->start_cluster,
 262                                 current - difference - 1);
 263                 if (CLUSTER_INVALID(last))
 264                 {
 265                         exfat_error("invalid cluster in file");
 266                         return -EIO;
 267                 }
 268                 previous = exfat_next_cluster(ef, node, last);
 269                 set_next_cluster(ef, IS_CONTIGUOUS(*node), last, EXFAT_CLUSTER_END);
 270         }
 271         else
 272         {
 273                 previous = node->start_cluster;
 274                 node->start_cluster = EXFAT_CLUSTER_FREE;
 275         }
 276
 277         /* free remaining clusters */
 278         while (difference--)
 279         {
 280                 if (CLUSTER_INVALID(previous))
 281                 {
 282                         exfat_error("invalid cluster in file");
 283                         return -EIO;
 284                 }
 285                 next = exfat_next_cluster(ef, node, previous);
 286                 set_next_cluster(ef, IS_CONTIGUOUS(*node), previous,
 287                                 EXFAT_CLUSTER_FREE);
 288                 free_cluster(ef, previous);
 289                 previous = next;
 290         }
 291         return 0;
 292 }
 293
 294 int exfat_truncate(struct exfat* ef, struct exfat_node* node, uint64_t size)
 295 {
 296         uint32_t c1 = bytes2clusters(ef, node->size);
 297         uint32_t c2 = bytes2clusters(ef, size);
 298         int rc = 0;
 299
 300         if (c1 < c2)
 301                 rc = grow_file(ef, node, c2 - c1);
 302         else if (c1 > c2)
 303                 rc = shrink_file(ef, node, c1 - c2);
 304
 305         if (rc != 0)
 306                 return rc;
 307
 308         if (node->size != size)
 309         {
 310                 node->size = size;
 311                 /* FIXME no need to flush immediately */
 312                 exfat_flush_node(ef, node);
 313         }
 314         return 0;
 315 }