Relicensed the code from GPLv3+ to GPLv2+.

[android-x86/external-exfat.git] / libexfat / cluster.c

diff --git a/libexfat/cluster.c b/libexfat/cluster.c
index 0f2d76a..d020d36 100644 (file)
--- a/libexfat/cluster.c
+++ b/libexfat/cluster.c
@@ -2,11 +2,12 @@
        cluster.c (03.09.09)
        exFAT file system implementation library.
 
        cluster.c (03.09.09)
        exFAT file system implementation library.
 

-       Copyright (C) 2009, 2010  Andrew Nayenko
+       Free exFAT implementation.
+       Copyright (C) 2010-2013  Andrew Nayenko

 
 

-       This program is free software: you can redistribute it and/or modify
+       This program is free software; you can redistribute it and/or modify

        it under the terms of the GNU General Public License as published by
        it under the terms of the GNU General Public License as published by

-       the Free Software Foundation, either version 3 of the License, or
+       the Free Software Foundation, either version 2 of the License, or

        (at your option) any later version.
 
        This program is distributed in the hope that it will be useful,
        (at your option) any later version.
 
        This program is distributed in the hope that it will be useful,


@@ -14,35 +15,32 @@
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        GNU General Public License for more details.
 
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        GNU General Public License for more details.
 

-       You should have received a copy of the GNU General Public License
-       along with this program.  If not, see <http://www.gnu.org/licenses/>.
+       You should have received a copy of the GNU General Public License along
+       with this program; if not, write to the Free Software Foundation, Inc.,
+       51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

 */
 
 #include "exfat.h"
 #include <errno.h>
 #include <string.h>
 
 */
 
 #include "exfat.h"
 #include <errno.h>
 #include <string.h>
 

-#define BMAP_GET(bitmap, index) ((bitmap)[(index) / 8] & (1u << ((index) % 8)))
-#define BMAP_SET(bitmap, index) (bitmap)[(index) / 8] |= (1u << ((index) % 8))
-#define BMAP_CLR(bitmap, index) (bitmap)[(index) / 8] &= ~(1u << ((index) % 8))
-

 /*
 /*

- * Block to absolute offset.
+ * Sector to absolute offset.

  */
  */

-static off_t b2o(const struct exfat* ef, off_t block)
+static off_t s2o(const struct exfat* ef, off_t sector)

 {
 {

-       return block << ef->sb->block_bits;
+       return sector << ef->sb->sector_bits;

 }
 
 /*
 }
 
 /*

- * Cluster to block.
+ * Cluster to sector.

  */
  */

-static off_t c2b(const struct exfat* ef, cluster_t cluster)
+static off_t c2s(const struct exfat* ef, cluster_t cluster)

 {
        if (cluster < EXFAT_FIRST_DATA_CLUSTER)
                exfat_bug("invalid cluster number %u", cluster);
 {
        if (cluster < EXFAT_FIRST_DATA_CLUSTER)
                exfat_bug("invalid cluster number %u", cluster);

-       return le32_to_cpu(ef->sb->cluster_block_start) +
-               ((off_t) (cluster - EXFAT_FIRST_DATA_CLUSTER) << ef->sb->bpc_bits);
+       return le32_to_cpu(ef->sb->cluster_sector_start) +
+               ((off_t) (cluster - EXFAT_FIRST_DATA_CLUSTER) << ef->sb->spc_bits);

 }
 
 /*
 }
 
 /*


@@ -50,7 +48,16 @@ static off_t c2b(const struct exfat* ef, cluster_t cluster)
  */
 off_t exfat_c2o(const struct exfat* ef, cluster_t cluster)
 {
  */
 off_t exfat_c2o(const struct exfat* ef, cluster_t cluster)
 {

-       return b2o(ef, c2b(ef, cluster));
+       return s2o(ef, c2s(ef, cluster));
+}
+
+/*
+ * Sector to cluster.
+ */
+static cluster_t s2c(const struct exfat* ef, off_t sector)
+{
+       return ((sector - le32_to_cpu(ef->sb->cluster_sector_start)) >>
+                       ef->sb->spc_bits) + EXFAT_FIRST_DATA_CLUSTER;

 }
 
 /*
 }
 
 /*


@@ -73,9 +80,9 @@ cluster_t exfat_next_cluster(const struct exfat* ef,
 
        if (IS_CONTIGUOUS(*node))
                return cluster + 1;
 
        if (IS_CONTIGUOUS(*node))
                return cluster + 1;

-       fat_offset = b2o(ef, le32_to_cpu(ef->sb->fat_block_start))
+       fat_offset = s2o(ef, le32_to_cpu(ef->sb->fat_sector_start))

                + cluster * sizeof(cluster_t);
                + cluster * sizeof(cluster_t);

-       exfat_read_raw(&next, sizeof(next), fat_offset, ef->fd);
+       exfat_pread(ef->dev, &next, sizeof(next), fat_offset);

        return le32_to_cpu(next);
 }
 
        return le32_to_cpu(next);
 }
 


@@ -94,58 +101,42 @@ cluster_t exfat_advance_cluster(const struct exfat* ef,
        {
                node->fptr_cluster = exfat_next_cluster(ef, node, node->fptr_cluster);
                if (CLUSTER_INVALID(node->fptr_cluster))
        {
                node->fptr_cluster = exfat_next_cluster(ef, node, node->fptr_cluster);
                if (CLUSTER_INVALID(node->fptr_cluster))

-                       break;
+                       break; /* the caller should handle this and print appropriate 
+                                 error message */

        }
        node->fptr_index = count;
        return node->fptr_cluster;
 }
 
        }
        node->fptr_index = count;
        return node->fptr_cluster;
 }
 

-static cluster_t find_bit_and_set(uint8_t* bitmap, cluster_t start,
-               cluster_t end)
+static cluster_t find_bit_and_set(uint8_t* bitmap, size_t start, size_t end)

 {
 {

-       const cluster_t mid_start = (start + 7) / 8 * 8;
-       const cluster_t mid_end = end / 8 * 8;
-       cluster_t c;
-       cluster_t byte;
-
-       for (c = start; c < mid_start; c++)
-               if (BMAP_GET(bitmap, c) == 0)
-               {
-                       BMAP_SET(bitmap, c);
-                       return c + EXFAT_FIRST_DATA_CLUSTER;
-               }
-
-       for (byte = mid_start / 8; byte < mid_end / 8; byte++)
-               if (bitmap[byte] != 0xff)
-               {
-                       cluster_t bit;
-
-                       for (bit = 0; bit < 8; bit++)
-                               if (!(bitmap[byte] & (1u << bit)))
-                               {
-                                       bitmap[byte] |= (1u << bit);
-                                       return byte * 8 + bit + EXFAT_FIRST_DATA_CLUSTER;
-                               }
-               }
-
-       for (c = mid_end; c < end; c++)
-               if (BMAP_GET(bitmap, c) == 0)
-               {
-                       BMAP_SET(bitmap, c);
-                       return c + EXFAT_FIRST_DATA_CLUSTER;
-               }
+       const size_t start_index = start / 8;
+       const size_t end_index = DIV_ROUND_UP(end, 8);
+       size_t i;
+       size_t c;

 
 

+       for (i = start_index; i < end_index; i++)
+       {
+               if (bitmap[i] == 0xff)
+                       continue;
+               for (c = MAX(i * 8, start); c < MIN((i + 1) * 8, end); c++)
+                       if (BMAP_GET(bitmap, c) == 0)
+                       {
+                               BMAP_SET(bitmap, c);
+                               return c + EXFAT_FIRST_DATA_CLUSTER;
+                       }
+       }

        return EXFAT_CLUSTER_END;
 }
 
 void exfat_flush_cmap(struct exfat* ef)
 {
        return EXFAT_CLUSTER_END;
 }
 
 void exfat_flush_cmap(struct exfat* ef)
 {

-       exfat_write_raw(ef->cmap.chunk, (ef->cmap.chunk_size + 7) / 8,
-                       exfat_c2o(ef, ef->cmap.start_cluster), ef->fd);
-       ef->cmap.dirty = 0;
+       exfat_pwrite(ef->dev, ef->cmap.chunk, (ef->cmap.chunk_size + 7) / 8,
+                       exfat_c2o(ef, ef->cmap.start_cluster));
+       ef->cmap.dirty = false;

 }
 
 }
 

-static void set_next_cluster(const struct exfat* ef, int contiguous,
+static void set_next_cluster(const struct exfat* ef, bool contiguous,

                cluster_t current, cluster_t next)
 {
        off_t fat_offset;
                cluster_t current, cluster_t next)
 {
        off_t fat_offset;


@@ -153,10 +144,10 @@ static void set_next_cluster(const struct exfat* ef, int contiguous,
 
        if (contiguous)
                return;
 
        if (contiguous)
                return;

-       fat_offset = b2o(ef, le32_to_cpu(ef->sb->fat_block_start))
+       fat_offset = s2o(ef, le32_to_cpu(ef->sb->fat_sector_start))

                + current * sizeof(cluster_t);
        next_le32 = cpu_to_le32(next);
                + current * sizeof(cluster_t);
        next_le32 = cpu_to_le32(next);

-       exfat_write_raw(&next_le32, sizeof(next_le32), fat_offset, ef->fd);
+       exfat_pwrite(ef->dev, &next_le32, sizeof(next_le32), fat_offset);

 }
 
 static cluster_t allocate_cluster(struct exfat* ef, cluster_t hint)
 }
 
 static cluster_t allocate_cluster(struct exfat* ef, cluster_t hint)


@@ -176,22 +167,20 @@ static cluster_t allocate_cluster(struct exfat* ef, cluster_t hint)
                return EXFAT_CLUSTER_END;
        }
 
                return EXFAT_CLUSTER_END;
        }
 

-       ef->cmap.dirty = 1;
-       /* FIXME update percentage of used space */
+       ef->cmap.dirty = true;

        return cluster;
 }
 
 static void free_cluster(struct exfat* ef, cluster_t cluster)
 {
        if (CLUSTER_INVALID(cluster))
        return cluster;
 }
 
 static void free_cluster(struct exfat* ef, cluster_t cluster)
 {
        if (CLUSTER_INVALID(cluster))

-               exfat_bug("attempting to free invalid cluster");
-       if (cluster < EXFAT_FIRST_DATA_CLUSTER ||
-               cluster - EXFAT_FIRST_DATA_CLUSTER >= ef->cmap.size)
-               exfat_bug("bad cluster 0x%x (0x%x)", cluster, ef->cmap.size);
+               exfat_bug("freeing invalid cluster 0x%x", cluster);
+       if (cluster - EXFAT_FIRST_DATA_CLUSTER >= ef->cmap.size)
+               exfat_bug("freeing non-existing cluster 0x%x (0x%x)", cluster,
+                               ef->cmap.size);

 
        BMAP_CLR(ef->cmap.chunk, cluster - EXFAT_FIRST_DATA_CLUSTER);
 
        BMAP_CLR(ef->cmap.chunk, cluster - EXFAT_FIRST_DATA_CLUSTER);

-       ef->cmap.dirty = 1;
-       /* FIXME update percentage of used space */
+       ef->cmap.dirty = true;

 }
 
 static void make_noncontiguous(const struct exfat* ef, cluster_t first,
 }
 
 static void make_noncontiguous(const struct exfat* ef, cluster_t first,


@@ -200,7 +189,7 @@ static void make_noncontiguous(const struct exfat* ef, cluster_t first,
        cluster_t c;
 
        for (c = first; c < last; c++)
        cluster_t c;
 
        for (c = first; c < last; c++)

-               set_next_cluster(ef, 0, c, c + 1);
+               set_next_cluster(ef, false, c, c + 1);

 }
 
 static int shrink_file(struct exfat* ef, struct exfat_node* node,
 }
 
 static int shrink_file(struct exfat* ef, struct exfat_node* node,


@@ -222,7 +211,7 @@ static int grow_file(struct exfat* ef, struct exfat_node* node,
                previous = exfat_advance_cluster(ef, node, current - 1);
                if (CLUSTER_INVALID(previous))
                {
                previous = exfat_advance_cluster(ef, node, current - 1);
                if (CLUSTER_INVALID(previous))
                {

-                       exfat_error("invalid cluster in file");
+                       exfat_error("invalid cluster 0x%x while growing", previous);

                        return -EIO;
                }
        }
                        return -EIO;
                }
        }


@@ -287,7 +276,7 @@ static int shrink_file(struct exfat* ef, struct exfat_node* node,
                                current - difference - 1);
                if (CLUSTER_INVALID(last))
                {
                                current - difference - 1);
                if (CLUSTER_INVALID(last))
                {

-                       exfat_error("invalid cluster in file");
+                       exfat_error("invalid cluster 0x%x while shrinking", last);

                        return -EIO;
                }
                previous = exfat_next_cluster(ef, node, last);
                        return -EIO;
                }
                previous = exfat_next_cluster(ef, node, last);


@@ -306,7 +295,8 @@ static int shrink_file(struct exfat* ef, struct exfat_node* node,
        {
                if (CLUSTER_INVALID(previous))
                {
        {
                if (CLUSTER_INVALID(previous))
                {

-                       exfat_error("invalid cluster in file");
+                       exfat_error("invalid cluster 0x%x while freeing after shrink",
+                                       previous);

                        return -EIO;
                }
                next = exfat_next_cluster(ef, node, previous);
                        return -EIO;
                }
                next = exfat_next_cluster(ef, node, previous);


@@ -320,42 +310,44 @@ static int shrink_file(struct exfat* ef, struct exfat_node* node,
 
 static void erase_raw(struct exfat* ef, size_t size, off_t offset)
 {
 
 static void erase_raw(struct exfat* ef, size_t size, off_t offset)
 {

-       exfat_write_raw(ef->zero_block, size, offset, ef->fd);
+       exfat_pwrite(ef->dev, ef->zero_cluster, size, offset);

 }
 
 static int erase_range(struct exfat* ef, struct exfat_node* node,
                uint64_t begin, uint64_t end)
 {
 }
 
 static int erase_range(struct exfat* ef, struct exfat_node* node,
                uint64_t begin, uint64_t end)
 {

-       uint64_t block_boundary;
+       uint64_t cluster_boundary;

        cluster_t cluster;
 
        if (begin >= end)
                return 0;
 
        cluster_t cluster;
 
        if (begin >= end)
                return 0;
 

-       block_boundary = (node->size | (BLOCK_SIZE(*ef->sb) - 1)) + 1;
+       cluster_boundary = (begin | (CLUSTER_SIZE(*ef->sb) - 1)) + 1;

        cluster = exfat_advance_cluster(ef, node,
        cluster = exfat_advance_cluster(ef, node,

-                       node->size / CLUSTER_SIZE(*ef->sb));
+                       begin / CLUSTER_SIZE(*ef->sb));

        if (CLUSTER_INVALID(cluster))
        {
        if (CLUSTER_INVALID(cluster))
        {

-               exfat_error("invalid cluster in file");
+               exfat_error("invalid cluster 0x%x while erasing", cluster);

                return -EIO;
        }
                return -EIO;
        }

-       /* erase from the beginning to the closest block boundary */
-       erase_raw(ef, MIN(block_boundary, end) - node->size,
-                       exfat_c2o(ef, cluster) + node->size % CLUSTER_SIZE(*ef->sb));
-       /* erase whole blocks */
-       while (block_boundary < end)
+       /* erase from the beginning to the closest cluster boundary */
+       erase_raw(ef, MIN(cluster_boundary, end) - begin,
+                       exfat_c2o(ef, cluster) + begin % CLUSTER_SIZE(*ef->sb));
+       /* erase whole clusters */
+       while (cluster_boundary < end)

        {
        {

-               if (block_boundary % CLUSTER_SIZE(*ef->sb) == 0)
-                       cluster = exfat_next_cluster(ef, node, cluster);
-               erase_raw(ef, BLOCK_SIZE(*ef->sb),
-                       exfat_c2o(ef, cluster) + block_boundary % CLUSTER_SIZE(*ef->sb));
-               block_boundary += BLOCK_SIZE(*ef->sb);
+               cluster = exfat_next_cluster(ef, node, cluster);
+               /* the cluster cannot be invalid because we have just allocated it */
+               if (CLUSTER_INVALID(cluster))
+                       exfat_bug("invalid cluster 0x%x after allocation", cluster);
+               erase_raw(ef, CLUSTER_SIZE(*ef->sb), exfat_c2o(ef, cluster));
+               cluster_boundary += CLUSTER_SIZE(*ef->sb);

        }
        return 0;
 }
 
        }
        return 0;
 }
 

-int exfat_truncate(struct exfat* ef, struct exfat_node* node, uint64_t size)
+int exfat_truncate(struct exfat* ef, struct exfat_node* node, uint64_t size,
+               bool erase)

 {
        uint32_t c1 = bytes2clusters(ef, node->size);
        uint32_t c2 = bytes2clusters(ef, size);
 {
        uint32_t c1 = bytes2clusters(ef, node->size);
        uint32_t c2 = bytes2clusters(ef, size);


@@ -375,9 +367,12 @@ int exfat_truncate(struct exfat* ef, struct exfat_node* node, uint64_t size)
        if (rc != 0)
                return rc;
 
        if (rc != 0)
                return rc;
 

-       rc = erase_range(ef, node, node->size, size);
-       if (rc != 0)
-               return rc;
+       if (erase)
+       {
+               rc = erase_range(ef, node, node->size, size);
+               if (rc != 0)
+                       return rc;
+       }

 
        exfat_update_mtime(node);
        node->size = size;
 
        exfat_update_mtime(node);
        node->size = size;


@@ -385,7 +380,7 @@ int exfat_truncate(struct exfat* ef, struct exfat_node* node, uint64_t size)
        return 0;
 }
 
        return 0;
 }
 

-uint32_t exfat_count_free_clusters(struct exfat* ef)
+uint32_t exfat_count_free_clusters(const struct exfat* ef)

 {
        uint32_t free_clusters = 0;
        uint32_t i;
 {
        uint32_t free_clusters = 0;
        uint32_t i;


@@ -395,3 +390,45 @@ uint32_t exfat_count_free_clusters(struct exfat* ef)
                        free_clusters++;
        return free_clusters;
 }
                        free_clusters++;
        return free_clusters;
 }

+
+static int find_used_clusters(const struct exfat* ef,
+               cluster_t* a, cluster_t* b)
+{
+       const cluster_t end = le32_to_cpu(ef->sb->cluster_count);
+
+       /* find first used cluster */
+       for (*a = *b + 1; *a < end; (*a)++)
+               if (BMAP_GET(ef->cmap.chunk, *a - EXFAT_FIRST_DATA_CLUSTER))
+                       break;
+       if (*a >= end)
+               return 1;
+
+       /* find last contiguous used cluster */
+       for (*b = *a; *b < end; (*b)++)
+               if (BMAP_GET(ef->cmap.chunk, *b - EXFAT_FIRST_DATA_CLUSTER) == 0)
+               {
+                       (*b)--;
+                       break;
+               }
+
+       return 0;
+}
+
+int exfat_find_used_sectors(const struct exfat* ef, off_t* a, off_t* b)
+{
+       cluster_t ca, cb;
+
+       if (*a == 0 && *b == 0)
+               ca = cb = EXFAT_FIRST_DATA_CLUSTER - 1;
+       else
+       {
+               ca = s2c(ef, *a);
+               cb = s2c(ef, *b);
+       }
+       if (find_used_clusters(ef, &ca, &cb) != 0)
+               return 1;
+       if (*a != 0 || *b != 0)
+               *a = c2s(ef, ca);
+       *b = c2s(ef, cb) + (CLUSTER_SIZE(*ef->sb) - 1) / SECTOR_SIZE(*ef->sb);
+       return 0;
+}