WebSVN – HelenOS – Diff – /branches/dynload/uspace/srv/fs/fat/fat_fat.c

 /*
  * Copyright (c) 2008 Jakub Jermar
  * All rights reserved.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
+ *
  * - Redistributions of source code must retain the above copyright
  *   notice, this list of conditions and the following disclaimer.
  * - Redistributions in binary form must reproduce the above copyright
  *   notice, this list of conditions and the following disclaimer in the
  *   documentation and/or other materials provided with the distribution.
  * - The name of the author may not be used to endorse or promote products
  *   derived from this software without specific prior written permission.
+ *
  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 /** @addtogroup fs
  * @{
  */
 /**
  * @file    fat_fat.c
  * @brief   Functions that manipulate the File Allocation Tables.
  */
 #include "fat_fat.h"
 #include "fat_dentry.h"
 #include "fat.h"
 #include "../../vfs/vfs.h"
 #include <libfs.h>
 #include <libblock.h>
 #include <errno.h>
 #include <byteorder.h>
 #include <align.h>
 #include <assert.h>
 #include <futex.h>
 /**
  * The fat_alloc_lock futex protects all copies of the File Allocation Table
  * during allocation of clusters. The lock does not have to be held durring
  * deallocation of clusters.
  */
 static futex_t fat_alloc_lock = FUTEX_INITIALIZER;
-/** Read block from file located on a FAT file system.
+/** Walk the cluster chain.
+ *
- * @param bs        Buffer holding the boot sector of the file system.
+ * @param bs        Buffer holding the boot sector for the file.
- * @param dev_handle    Device handle of the file system.
+ * @param dev_handle    Device handle of the device with the file.
- * @param firstc    First cluster used by the file. Can be zero if the file
+ * @param firstc    First cluster to start the walk with.
+ * @param penult    If non-NULL, output argument hodling the
+ *          the penultimate cluster visited.
+ * @param ult       If non-NULL, output argument holding the
- *          is empty.
+ *          ultimate cluster visited.
- * @param offset    Offset in blocks.
+ * @param max_clusters  Maximum number of clusters to visit.
+ *
- * @return      Block structure holding the requested block.
+ * @return      Number of clusters seen during the walk.
  */
-block_t *
+uint16_t
-_fat_block_get(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t firstc,
+fat_cluster_walk(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t firstc,
-    off_t offset)
+    fat_cluster_t *penult, fat_cluster_t *ult, uint16_t max_clusters)
+{
     block_t *b;
     unsigned bps;
-    unsigned spc;
     unsigned rscnt;     /* block address of the first FAT */
-    unsigned fatcnt;
-    unsigned rde;
-    unsigned rds;       /* root directory size */
-    unsigned sf;
-    unsigned ssa;       /* size of the system area */
-    unsigned clusters;
+    uint16_t clusters = 0;
     fat_cluster_t clst = firstc;
-    unsigned i;
     bps = uint16_t_le2host(bs->bps);
-    spc = bs->spc;
     rscnt = uint16_t_le2host(bs->rscnt);
-    fatcnt = bs->fatcnt;
-    rde = uint16_t_le2host(bs->root_ent_max);
-    sf = uint16_t_le2host(bs->sec_per_fat);
-    rds = (sizeof(fat_dentry_t) * rde) / bps;
-    rds += ((sizeof(fat_dentry_t) * rde) % bps != 0);
-    ssa = rscnt + fatcnt * sf + rds;
-    if (firstc == FAT_CLST_ROOT) {
+    if (firstc == FAT_CLST_RES0) {
-        /* root directory special case */
+        /* No space allocated to the file. */
-        assert(offset < rds);
+        if (ult)
-        b = block_get(dev_handle, rscnt + fatcnt * sf + offset, bps);
+            *ult = firstc;
-        return b;
+        return 0;
+    }
+    /* At this point, the meaning of penult is not well-defined. */
+    if (penult)
-    clusters = offset / spc;
+        *penult = FAT_CLST_RES0;
-    for (i = 0; i < clusters; i++) {
+    while (clst < FAT_CLST_LAST1 && clusters < max_clusters) {
         unsigned fsec;  /* sector offset relative to FAT1 */
         unsigned fidx;  /* FAT1 entry index */
-        assert(clst >= FAT_CLST_FIRST && clst < FAT_CLST_BAD);
+        assert(clst >= FAT_CLST_FIRST);
+        if (penult)
+            *penult = clst; /* remember the penultimate cluster */
         fsec = (clst * sizeof(fat_cluster_t)) / bps;
         fidx = clst % (bps / sizeof(fat_cluster_t));
         /* read FAT1 */
-        b = block_get(dev_handle, rscnt + fsec, bps);
+        b = block_get(dev_handle, rscnt + fsec);
         clst = uint16_t_le2host(((fat_cluster_t *)b->data)[fidx]);
         assert(clst != FAT_CLST_BAD);
-        assert(clst < FAT_CLST_LAST1);
         block_put(b);
+        clusters++;
+    }
-    b = block_get(dev_handle, ssa + (clst - FAT_CLST_FIRST) * spc +
+    if (ult)
-        offset % spc, bps);
+        *ult = clst;
-    return b;
+    return clusters;
+}
-/** Return number of blocks allocated to a file.
+/** Read block from file located on a FAT file system.
+ *
- * @param bs        Buffer holding the boot sector for the file.
+ * @param bs        Buffer holding the boot sector of the file system.
- * @param dev_handle    Device handle of the device with the file.
+ * @param dev_handle    Device handle of the file system.
- * @param firstc    First cluster of the file.
+ * @param firstc    First cluster used by the file. Can be zero if the file
- * @param lastc     If non-NULL, output argument holding the
- *          last cluster.
+ *          is empty.
+ * @param offset    Offset in blocks.
+ *
- * @return      Number of blocks allocated to the file.
+ * @return      Block structure holding the requested block.
  */
-uint16_t
+block_t *
-_fat_blcks_get(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t firstc,
+_fat_block_get(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t firstc,
-    fat_cluster_t *lastc)
+    off_t offset)
+{
     block_t *b;
     unsigned bps;
-    unsigned spc;
     unsigned rscnt;     /* block address of the first FAT */
+    unsigned rde;
+    unsigned rds;       /* root directory size */
+    unsigned sf;
+    unsigned ssa;       /* size of the system area */
-    unsigned clusters = 0;
+    unsigned clusters, max_clusters;
-    fat_cluster_t clst = firstc;
+    fat_cluster_t lastc, clst = firstc;
     bps = uint16_t_le2host(bs->bps);
-    spc = bs->spc;
     rscnt = uint16_t_le2host(bs->rscnt);
+    rde = uint16_t_le2host(bs->root_ent_max);
+    sf = uint16_t_le2host(bs->sec_per_fat);
+    rds = (sizeof(fat_dentry_t) * rde) / bps;
+    rds += ((sizeof(fat_dentry_t) * rde) % bps != 0);
+    ssa = rscnt + bs->fatcnt * sf + rds;
-    if (firstc == FAT_CLST_RES0) {
+    if (firstc == FAT_CLST_ROOT) {
-        /* No space allocated to the file. */
+        /* root directory special case */
-        if (lastc)
+        assert(offset < rds);
-            *lastc = firstc;
+        b = block_get(dev_handle, rscnt + bs->fatcnt * sf + offset);
-        return 0;
+        return b;
+    }
-    while (clst < FAT_CLST_LAST1) {
+    max_clusters = offset / bs->spc;
-        unsigned fsec;  /* sector offset relative to FAT1 */
+    clusters = fat_cluster_walk(bs, dev_handle, firstc, NULL, &lastc,
+        max_clusters);
-        unsigned fidx;  /* FAT1 entry index */
+    assert(clusters == max_clusters);
-        assert(clst >= FAT_CLST_FIRST);
-        if (lastc)
-            *lastc = clst;      /* remember the last cluster */
-        fsec = (clst * sizeof(fat_cluster_t)) / bps;
-        fidx = clst % (bps / sizeof(fat_cluster_t));
-        /* read FAT1 */
-        b = block_get(dev_handle, rscnt + fsec, bps);
+    b = block_get(dev_handle, ssa + (lastc - FAT_CLST_FIRST) * bs->spc +
-        clst = uint16_t_le2host(((fat_cluster_t *)b->data)[fidx]);
-        assert(clst != FAT_CLST_BAD);
-        block_put(b);
+        offset % bs->spc);
-        clusters++;
-    }
-    if (lastc)
-        *lastc = clst;
-    return clusters * spc;
+    return b;
+}
 /** Fill the gap between EOF and a new file position.
+ *
  * @param bs        Buffer holding the boot sector for nodep.
  * @param nodep     FAT node with the gap.
  * @param mcl       First cluster in an independent cluster chain that will
  *          be later appended to the end of the node's own cluster
  *          chain. If pos is still in the last allocated cluster,
  *          this argument is ignored.
  * @param pos       Position in the last node block.
  */
 void fat_fill_gap(fat_bs_t *bs, fat_node_t *nodep, fat_cluster_t mcl, off_t pos)
+{
     uint16_t bps;
     unsigned spc;
     block_t *b;
     off_t o, boundary;
     bps = uint16_t_le2host(bs->bps);
     spc = bs->spc;
     boundary = ROUND_UP(nodep->size, bps * spc);
     /* zero out already allocated space */
     for (o = nodep->size - 1; o < pos && o < boundary;
         o = ALIGN_DOWN(o + bps, bps)) {
         b = fat_block_get(bs, nodep, o / bps);
         memset(b->data + o % bps, 0, bps - o % bps);
         b->dirty = true;        /* need to sync node */
         block_put(b);
+    }
     if (o >= pos)
         return;
     /* zero out the initial part of the new cluster chain */
     for (o = boundary; o < pos; o += bps) {
         b = _fat_block_get(bs, nodep->idx->dev_handle, mcl,
             (o - boundary) / bps);
         memset(b->data, 0, min(bps, pos - o));
         b->dirty = true;        /* need to sync node */
         block_put(b);
+    }
+}
 /** Mark cluster in one instance of FAT.
+ *
  * @param bs        Buffer holding the boot sector for the file system.
  * @param dev_handle    Device handle for the file system.
  * @param fatno     Number of the FAT instance where to make the change.
  * @param clst      Cluster which is to be marked.
  * @param value     Value mark the cluster with.
  */
 void
 fat_mark_cluster(fat_bs_t *bs, dev_handle_t dev_handle, unsigned fatno,
     fat_cluster_t clst, fat_cluster_t value)
+{
     block_t *b;
     uint16_t bps;
     uint16_t rscnt;
     uint16_t sf;
     fat_cluster_t *cp;
     bps = uint16_t_le2host(bs->bps);
     rscnt = uint16_t_le2host(bs->rscnt);
     sf = uint16_t_le2host(bs->sec_per_fat);
     assert(fatno < bs->fatcnt);
     b = block_get(dev_handle, rscnt + sf * fatno +
-        (clst * sizeof(fat_cluster_t)) / bps, bps);
+        (clst * sizeof(fat_cluster_t)) / bps);
     cp = (fat_cluster_t *)b->data + clst % (bps / sizeof(fat_cluster_t));
     *cp = host2uint16_t_le(value);
     b->dirty = true;        /* need to sync block */
     block_put(b);
+}
 /** Replay the allocatoin of clusters in all shadow instances of FAT.
+ *
  * @param bs        Buffer holding the boot sector of the file system.
  * @param dev_handle    Device handle of the file system.
  * @param lifo      Chain of allocated clusters.
  * @param nclsts    Number of clusters in the lifo chain.
  */
 void fat_alloc_shadow_clusters(fat_bs_t *bs, dev_handle_t dev_handle,
     fat_cluster_t *lifo, unsigned nclsts)
+{
     uint8_t fatno;
     unsigned c;
     for (fatno = FAT1 + 1; fatno < bs->fatcnt; fatno++) {
         for (c = 0; c < nclsts; c++) {
             fat_mark_cluster(bs, dev_handle, fatno, lifo[c],
                 c == 0 ? FAT_CLST_LAST1 : lifo[c - 1]);
+        }
+    }
+}
 /** Allocate clusters in FAT1.
+ *
  * This function will attempt to allocate the requested number of clusters in
  * the first FAT instance.  The FAT will be altered so that the allocated
  * clusters form an independent chain (i.e. a chain which does not belong to any
  * file yet).
+ *
  * @param bs        Buffer holding the boot sector of the file system.
  * @param dev_handle    Device handle of the file system.
  * @param nclsts    Number of clusters to allocate.
  * @param mcl       Output parameter where the first cluster in the chain
  *          will be returned.
  * @param lcl       Output parameter where the last cluster in the chain
  *          will be returned.
+ *
  * @return      EOK on success, a negative error code otherwise.
  */
 int
 fat_alloc_clusters(fat_bs_t *bs, dev_handle_t dev_handle, unsigned nclsts,
     fat_cluster_t *mcl, fat_cluster_t *lcl)
+{
     uint16_t bps;
     uint16_t rscnt;
     uint16_t sf;
     block_t *blk;
     fat_cluster_t *lifo;    /* stack for storing free cluster numbers */
     unsigned found = 0; /* top of the free cluster number stack */
     unsigned b, c, cl;
     lifo = (fat_cluster_t *) malloc(nclsts * sizeof(fat_cluster_t));
     if (lifo)
         return ENOMEM;
     bps = uint16_t_le2host(bs->bps);
     rscnt = uint16_t_le2host(bs->rscnt);
     sf = uint16_t_le2host(bs->sec_per_fat);
     /*
      * Search FAT1 for unused clusters.
      */
     futex_down(&fat_alloc_lock);
     for (b = 0, cl = 0; b < sf; blk++) {
-        blk = block_get(dev_handle, rscnt + b, bps);
+        blk = block_get(dev_handle, rscnt + b);
         for (c = 0; c < bps / sizeof(fat_cluster_t); c++, cl++) {
             fat_cluster_t *clst = (fat_cluster_t *)blk->data + c;
             if (uint16_t_le2host(*clst) == FAT_CLST_RES0) {
                 /*
                  * The cluster is free. Put it into our stack
                  * of found clusters and mark it as non-free.
                  */
                 lifo[found] = cl;
                 *clst = (found == 0) ?
                     host2uint16_t_le(FAT_CLST_LAST1) :
                     host2uint16_t_le(lifo[found - 1]);
                 blk->dirty = true;  /* need to sync block */
                 if (++found == nclsts) {
                     /* we are almost done */
                     block_put(blk);
                     /* update the shadow copies of FAT */
                     fat_alloc_shadow_clusters(bs,
                         dev_handle, lifo, nclsts);
                     *mcl = lifo[found - 1];
                     *lcl = lifo[0];
                     free(lifo);
                     futex_up(&fat_alloc_lock);
                     return EOK;
+                }
+            }
+        }
         block_put(blk);
+    }
     futex_up(&fat_alloc_lock);
     /*
      * We could not find enough clusters. Now we need to free the clusters
      * we have allocated so far.
      */
     while (found--) {
         fat_mark_cluster(bs, dev_handle, FAT1, lifo[found],
             FAT_CLST_RES0);
+    }
     free(lifo);
     return ENOSPC;
+}
 /** Append a cluster chain to the last file cluster in all FATs.
+ *
  * @param bs        Buffer holding boot sector of the file system.
  * @param nodep     Node representing the file.
  * @param mcl       First cluster of the cluster chain to append.
  */
 void fat_append_clusters(fat_bs_t *bs, fat_node_t *nodep, fat_cluster_t mcl)
+{
     dev_handle_t dev_handle = nodep->idx->dev_handle;
     fat_cluster_t lcl;
     uint8_t fatno;
-    if (_fat_blcks_get(bs, dev_handle, nodep->firstc, &lcl) == 0) {
+    if (fat_cluster_walk(bs, nodep->idx->dev_handle, nodep->firstc, &lcl,
+        NULL, (uint16_t) -1) == 0) {
+        /* No clusters allocated to the node yet. */
         nodep->firstc = host2uint16_t_le(mcl);
         nodep->dirty = true;        /* need to sync node */
         return;
+    }
     for (fatno = FAT1; fatno < bs->fatcnt; fatno++)
         fat_mark_cluster(bs, nodep->idx->dev_handle, fatno, lcl, mcl);
+}
 /**
  * @}
  */

Subversion Repositories HelenOS

(root)/branches/dynload/uspace/srv/fs/fat/fat_fat.c – Rev 3535 → 3561