Subversion Repositories HelenOS

Rev

Rev 4552 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
3504 jermar 1
/*
2
 * Copyright (c) 2008 Jakub Jermar
3
 * All rights reserved.
4
 *
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
7
 * are met:
8
 *
9
 * - Redistributions of source code must retain the above copyright
10
 *   notice, this list of conditions and the following disclaimer.
11
 * - Redistributions in binary form must reproduce the above copyright
12
 *   notice, this list of conditions and the following disclaimer in the
13
 *   documentation and/or other materials provided with the distribution.
14
 * - The name of the author may not be used to endorse or promote products
15
 *   derived from this software without specific prior written permission.
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
 */
28
 
29
/** @addtogroup fs
30
 * @{
31
 */
32
 
33
/**
34
 * @file    fat_fat.c
3517 jermar 35
 * @brief   Functions that manipulate the File Allocation Tables.
3504 jermar 36
 */
37
 
3506 jermar 38
#include "fat_fat.h"
39
#include "fat_dentry.h"
40
#include "fat.h"
41
#include "../../vfs/vfs.h"
42
#include <libfs.h>
3521 jermar 43
#include <libblock.h>
3506 jermar 44
#include <errno.h>
45
#include <byteorder.h>
46
#include <align.h>
47
#include <assert.h>
4552 jermar 48
#include <fibril_sync.h>
4465 decky 49
#include <mem.h>
3504 jermar 50
 
3517 jermar 51
/**
4552 jermar 52
 * The fat_alloc_lock mutex protects all copies of the File Allocation Table
3517 jermar 53
 * during allocation of clusters. The lock does not have to be held durring
54
 * deallocation of clusters.
55
 */  
4552 jermar 56
static FIBRIL_MUTEX_INITIALIZE(fat_alloc_lock);
3517 jermar 57
 
3550 jermar 58
/** Walk the cluster chain.
3518 jermar 59
 *
3550 jermar 60
 * @param bs        Buffer holding the boot sector for the file.
61
 * @param dev_handle    Device handle of the device with the file.
62
 * @param firstc    First cluster to start the walk with.
3571 jermar 63
 * @param lastc     If non-NULL, output argument hodling the last cluster number visited.
3550 jermar 64
 * @param max_clusters  Maximum number of clusters to visit.   
3518 jermar 65
 *
3550 jermar 66
 * @return      Number of clusters seen during the walk.
3518 jermar 67
 */
3550 jermar 68
uint16_t
69
fat_cluster_walk(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t firstc,
3571 jermar 70
    fat_cluster_t *lastc, uint16_t max_clusters)
3506 jermar 71
{
72
    block_t *b;
73
    unsigned bps;
74
    unsigned rscnt;     /* block address of the first FAT */
3550 jermar 75
    uint16_t clusters = 0;
3506 jermar 76
    fat_cluster_t clst = firstc;
77
 
3516 jermar 78
    bps = uint16_t_le2host(bs->bps);
79
    rscnt = uint16_t_le2host(bs->rscnt);
3506 jermar 80
 
3550 jermar 81
    if (firstc == FAT_CLST_RES0) {
82
        /* No space allocated to the file. */
3571 jermar 83
        if (lastc)
84
            *lastc = firstc;
3550 jermar 85
        return 0;
3506 jermar 86
    }
87
 
3550 jermar 88
    while (clst < FAT_CLST_LAST1 && clusters < max_clusters) {
3571 jermar 89
        bn_t fsec;  /* sector offset relative to FAT1 */
3506 jermar 90
        unsigned fidx;  /* FAT1 entry index */
91
 
3550 jermar 92
        assert(clst >= FAT_CLST_FIRST);
3571 jermar 93
        if (lastc)
94
            *lastc = clst;  /* remember the last cluster number */
3506 jermar 95
        fsec = (clst * sizeof(fat_cluster_t)) / bps;
96
        fidx = clst % (bps / sizeof(fat_cluster_t));
97
        /* read FAT1 */
3595 jermar 98
        b = block_get(dev_handle, rscnt + fsec, BLOCK_FLAGS_NONE);
3506 jermar 99
        clst = uint16_t_le2host(((fat_cluster_t *)b->data)[fidx]);
100
        assert(clst != FAT_CLST_BAD);
101
        block_put(b);
3550 jermar 102
        clusters++;
3506 jermar 103
    }
104
 
3571 jermar 105
    if (lastc && clst < FAT_CLST_LAST1)
106
        *lastc = clst;
3506 jermar 107
 
3550 jermar 108
    return clusters;
3506 jermar 109
}
110
 
3550 jermar 111
/** Read block from file located on a FAT file system.
3506 jermar 112
 *
3550 jermar 113
 * @param bs        Buffer holding the boot sector of the file system.
114
 * @param dev_handle    Device handle of the file system.
115
 * @param firstc    First cluster used by the file. Can be zero if the file
116
 *          is empty.
3571 jermar 117
 * @param bn        Block number.
3595 jermar 118
 * @param flags     Flags passed to libblock.
3506 jermar 119
 *
3550 jermar 120
 * @return      Block structure holding the requested block.
3506 jermar 121
 */
3550 jermar 122
block_t *
123
_fat_block_get(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t firstc,
3595 jermar 124
    bn_t bn, int flags)
3506 jermar 125
{
126
    block_t *b;
127
    unsigned bps;
128
    unsigned rscnt;     /* block address of the first FAT */
3550 jermar 129
    unsigned rde;
130
    unsigned rds;       /* root directory size */
131
    unsigned sf;
132
    unsigned ssa;       /* size of the system area */
133
    unsigned clusters, max_clusters;
3572 jermar 134
    fat_cluster_t lastc;
3506 jermar 135
 
3516 jermar 136
    bps = uint16_t_le2host(bs->bps);
137
    rscnt = uint16_t_le2host(bs->rscnt);
3550 jermar 138
    rde = uint16_t_le2host(bs->root_ent_max);
139
    sf = uint16_t_le2host(bs->sec_per_fat);
3506 jermar 140
 
3550 jermar 141
    rds = (sizeof(fat_dentry_t) * rde) / bps;
142
    rds += ((sizeof(fat_dentry_t) * rde) % bps != 0);
143
    ssa = rscnt + bs->fatcnt * sf + rds;
144
 
145
    if (firstc == FAT_CLST_ROOT) {
146
        /* root directory special case */
3571 jermar 147
        assert(bn < rds);
3595 jermar 148
        b = block_get(dev_handle, rscnt + bs->fatcnt * sf + bn, flags);
3550 jermar 149
        return b;
3506 jermar 150
    }
151
 
3571 jermar 152
    max_clusters = bn / bs->spc;
153
    clusters = fat_cluster_walk(bs, dev_handle, firstc, &lastc,
3550 jermar 154
        max_clusters);
155
    assert(clusters == max_clusters);
3506 jermar 156
 
3550 jermar 157
    b = block_get(dev_handle, ssa + (lastc - FAT_CLST_FIRST) * bs->spc +
3595 jermar 158
        bn % bs->spc, flags);
3506 jermar 159
 
3550 jermar 160
    return b;
3506 jermar 161
}
162
 
163
/** Fill the gap between EOF and a new file position.
164
 *
3516 jermar 165
 * @param bs        Buffer holding the boot sector for nodep.
3506 jermar 166
 * @param nodep     FAT node with the gap.
167
 * @param mcl       First cluster in an independent cluster chain that will
168
 *          be later appended to the end of the node's own cluster
169
 *          chain. If pos is still in the last allocated cluster,
170
 *          this argument is ignored.
171
 * @param pos       Position in the last node block.
172
 */
3516 jermar 173
void fat_fill_gap(fat_bs_t *bs, fat_node_t *nodep, fat_cluster_t mcl, off_t pos)
3506 jermar 174
{
175
    uint16_t bps;
176
    unsigned spc;
3516 jermar 177
    block_t *b;
3506 jermar 178
    off_t o, boundary;
179
 
3516 jermar 180
    bps = uint16_t_le2host(bs->bps);
181
    spc = bs->spc;
3506 jermar 182
 
183
    boundary = ROUND_UP(nodep->size, bps * spc);
184
 
185
    /* zero out already allocated space */
3652 jermar 186
    for (o = nodep->size; o < pos && o < boundary;
3506 jermar 187
        o = ALIGN_DOWN(o + bps, bps)) {
3595 jermar 188
            int flags = (o % bps == 0) ?
189
            BLOCK_FLAGS_NOREAD : BLOCK_FLAGS_NONE;
190
        b = fat_block_get(bs, nodep, o / bps, flags);
3506 jermar 191
        memset(b->data + o % bps, 0, bps - o % bps);
192
        b->dirty = true;        /* need to sync node */
193
        block_put(b);
194
    }
195
 
196
    if (o >= pos)
197
        return;
198
 
199
    /* zero out the initial part of the new cluster chain */
200
    for (o = boundary; o < pos; o += bps) {
3516 jermar 201
        b = _fat_block_get(bs, nodep->idx->dev_handle, mcl,
3595 jermar 202
            (o - boundary) / bps, BLOCK_FLAGS_NOREAD);
3506 jermar 203
        memset(b->data, 0, min(bps, pos - o));
204
        b->dirty = true;        /* need to sync node */
205
        block_put(b);
206
    }
207
}
208
 
3572 jermar 209
/** Get cluster from the first FAT.
3518 jermar 210
 *
211
 * @param bs        Buffer holding the boot sector for the file system.
212
 * @param dev_handle    Device handle for the file system.
3572 jermar 213
 * @param clst      Cluster which to get.
214
 *
215
 * @return      Value found in the cluster.
216
 */
217
fat_cluster_t
218
fat_get_cluster(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t clst)
219
{
220
    block_t *b;
221
    uint16_t bps;
222
    uint16_t rscnt;
223
    fat_cluster_t *cp, value;
224
 
225
    bps = uint16_t_le2host(bs->bps);
226
    rscnt = uint16_t_le2host(bs->rscnt);
227
 
3595 jermar 228
    b = block_get(dev_handle, rscnt + (clst * sizeof(fat_cluster_t)) / bps,
229
        BLOCK_FLAGS_NONE);
3572 jermar 230
    cp = (fat_cluster_t *)b->data + clst % (bps / sizeof(fat_cluster_t));
231
    value = uint16_t_le2host(*cp);
232
    block_put(b);
233
 
234
    return value;
235
}
236
 
237
/** Set cluster in one instance of FAT.
238
 *
239
 * @param bs        Buffer holding the boot sector for the file system.
240
 * @param dev_handle    Device handle for the file system.
3518 jermar 241
 * @param fatno     Number of the FAT instance where to make the change.
3572 jermar 242
 * @param clst      Cluster which is to be set.
243
 * @param value     Value to set the cluster with.
3518 jermar 244
 */
3506 jermar 245
void
3572 jermar 246
fat_set_cluster(fat_bs_t *bs, dev_handle_t dev_handle, unsigned fatno,
3516 jermar 247
    fat_cluster_t clst, fat_cluster_t value)
3506 jermar 248
{
3516 jermar 249
    block_t *b;
3510 jermar 250
    uint16_t bps;
251
    uint16_t rscnt;
252
    uint16_t sf;
253
    fat_cluster_t *cp;
254
 
3516 jermar 255
    bps = uint16_t_le2host(bs->bps);
256
    rscnt = uint16_t_le2host(bs->rscnt);
257
    sf = uint16_t_le2host(bs->sec_per_fat);
3510 jermar 258
 
3516 jermar 259
    assert(fatno < bs->fatcnt);
260
    b = block_get(dev_handle, rscnt + sf * fatno +
3595 jermar 261
        (clst * sizeof(fat_cluster_t)) / bps, BLOCK_FLAGS_NONE);
3516 jermar 262
    cp = (fat_cluster_t *)b->data + clst % (bps / sizeof(fat_cluster_t));
3510 jermar 263
    *cp = host2uint16_t_le(value);
3516 jermar 264
    b->dirty = true;        /* need to sync block */
265
    block_put(b);
3506 jermar 266
}
267
 
3518 jermar 268
/** Replay the allocatoin of clusters in all shadow instances of FAT.
269
 *
270
 * @param bs        Buffer holding the boot sector of the file system.
271
 * @param dev_handle    Device handle of the file system.
272
 * @param lifo      Chain of allocated clusters.
273
 * @param nclsts    Number of clusters in the lifo chain.
274
 */
3516 jermar 275
void fat_alloc_shadow_clusters(fat_bs_t *bs, dev_handle_t dev_handle,
276
    fat_cluster_t *lifo, unsigned nclsts)
3506 jermar 277
{
3507 jermar 278
    uint8_t fatno;
279
    unsigned c;
280
 
3516 jermar 281
    for (fatno = FAT1 + 1; fatno < bs->fatcnt; fatno++) {
3507 jermar 282
        for (c = 0; c < nclsts; c++) {
3572 jermar 283
            fat_set_cluster(bs, dev_handle, fatno, lifo[c],
3507 jermar 284
                c == 0 ? FAT_CLST_LAST1 : lifo[c - 1]);
285
        }
286
    }
3506 jermar 287
}
288
 
3632 jermar 289
/** Allocate clusters in all copies of FAT.
3518 jermar 290
 *
291
 * This function will attempt to allocate the requested number of clusters in
3632 jermar 292
 * all instances of the FAT.  The FAT will be altered so that the allocated
3518 jermar 293
 * clusters form an independent chain (i.e. a chain which does not belong to any
294
 * file yet).
295
 *
296
 * @param bs        Buffer holding the boot sector of the file system.
297
 * @param dev_handle    Device handle of the file system.
298
 * @param nclsts    Number of clusters to allocate.
299
 * @param mcl       Output parameter where the first cluster in the chain
300
 *          will be returned.
301
 * @param lcl       Output parameter where the last cluster in the chain
302
 *          will be returned.
303
 *
304
 * @return      EOK on success, a negative error code otherwise.
305
 */
3506 jermar 306
int
3516 jermar 307
fat_alloc_clusters(fat_bs_t *bs, dev_handle_t dev_handle, unsigned nclsts,
308
    fat_cluster_t *mcl, fat_cluster_t *lcl)
3506 jermar 309
{
310
    uint16_t bps;
311
    uint16_t rscnt;
312
    uint16_t sf;
3516 jermar 313
    block_t *blk;
3506 jermar 314
    fat_cluster_t *lifo;    /* stack for storing free cluster numbers */
315
    unsigned found = 0; /* top of the free cluster number stack */
316
    unsigned b, c, cl;
317
 
318
    lifo = (fat_cluster_t *) malloc(nclsts * sizeof(fat_cluster_t));
3632 jermar 319
    if (!lifo)
3506 jermar 320
        return ENOMEM;
321
 
3516 jermar 322
    bps = uint16_t_le2host(bs->bps);
323
    rscnt = uint16_t_le2host(bs->rscnt);
324
    sf = uint16_t_le2host(bs->sec_per_fat);
3506 jermar 325
 
326
    /*
327
     * Search FAT1 for unused clusters.
328
     */
4552 jermar 329
    fibril_mutex_lock(&fat_alloc_lock);
3632 jermar 330
    for (b = 0, cl = 0; b < sf; b++) {
331
        blk = block_get(dev_handle, rscnt + b, BLOCK_FLAGS_NONE);
3506 jermar 332
        for (c = 0; c < bps / sizeof(fat_cluster_t); c++, cl++) {
333
            fat_cluster_t *clst = (fat_cluster_t *)blk->data + c;
3512 jermar 334
            if (uint16_t_le2host(*clst) == FAT_CLST_RES0) {
3506 jermar 335
                /*
336
                 * The cluster is free. Put it into our stack
337
                 * of found clusters and mark it as non-free.
338
                 */
339
                lifo[found] = cl;
3512 jermar 340
                *clst = (found == 0) ?
341
                    host2uint16_t_le(FAT_CLST_LAST1) :
342
                    host2uint16_t_le(lifo[found - 1]);
3506 jermar 343
                blk->dirty = true;  /* need to sync block */
344
                if (++found == nclsts) {
345
                    /* we are almost done */
346
                    block_put(blk);
347
                    /* update the shadow copies of FAT */
3516 jermar 348
                    fat_alloc_shadow_clusters(bs,
349
                        dev_handle, lifo, nclsts);
3506 jermar 350
                    *mcl = lifo[found - 1];
351
                    *lcl = lifo[0];
352
                    free(lifo);
4552 jermar 353
                    fibril_mutex_unlock(&fat_alloc_lock);
3506 jermar 354
                    return EOK;
355
                }
356
            }
357
        }
358
        block_put(blk);
359
    }
4552 jermar 360
    fibril_mutex_unlock(&fat_alloc_lock);
3506 jermar 361
 
362
    /*
363
     * We could not find enough clusters. Now we need to free the clusters
364
     * we have allocated so far.
365
     */
3516 jermar 366
    while (found--) {
3572 jermar 367
        fat_set_cluster(bs, dev_handle, FAT1, lifo[found],
3516 jermar 368
            FAT_CLST_RES0);
369
    }
3506 jermar 370
 
371
    free(lifo);
372
    return ENOSPC;
373
}
374
 
3572 jermar 375
/** Free clusters forming a cluster chain in all copies of FAT.
376
 *
377
 * @param bs        Buffer hodling the boot sector of the file system.
378
 * @param dev_handle    Device handle of the file system.
379
 * @param firstc    First cluster in the chain which is to be freed.
380
 */
381
void
382
fat_free_clusters(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t firstc)
383
{
384
    unsigned fatno;
385
    fat_cluster_t nextc;
386
 
387
    /* Mark all clusters in the chain as free in all copies of FAT. */
388
    while (firstc < FAT_CLST_LAST1) {
3637 jermar 389
        assert(firstc >= FAT_CLST_FIRST && firstc < FAT_CLST_BAD);
3572 jermar 390
        nextc = fat_get_cluster(bs, dev_handle, firstc);
391
        for (fatno = FAT1; fatno < bs->fatcnt; fatno++)
392
            fat_set_cluster(bs, dev_handle, fatno, firstc,
393
                FAT_CLST_RES0);
394
        firstc = nextc;
395
    }
396
}
397
 
3518 jermar 398
/** Append a cluster chain to the last file cluster in all FATs.
399
 *
3572 jermar 400
 * @param bs        Buffer holding the boot sector of the file system.
3518 jermar 401
 * @param nodep     Node representing the file.
402
 * @param mcl       First cluster of the cluster chain to append.
403
 */
3516 jermar 404
void fat_append_clusters(fat_bs_t *bs, fat_node_t *nodep, fat_cluster_t mcl)
3506 jermar 405
{
3516 jermar 406
    dev_handle_t dev_handle = nodep->idx->dev_handle;
3513 jermar 407
    fat_cluster_t lcl;
3516 jermar 408
    uint8_t fatno;
3513 jermar 409
 
3572 jermar 410
    if (fat_cluster_walk(bs, dev_handle, nodep->firstc, &lcl,
3571 jermar 411
        (uint16_t) -1) == 0) {
3550 jermar 412
        /* No clusters allocated to the node yet. */
3656 jermar 413
        nodep->firstc = mcl;
3513 jermar 414
        nodep->dirty = true;        /* need to sync node */
415
        return;
416
    }
417
 
3516 jermar 418
    for (fatno = FAT1; fatno < bs->fatcnt; fatno++)
3572 jermar 419
        fat_set_cluster(bs, nodep->idx->dev_handle, fatno, lcl, mcl);
3506 jermar 420
}
421
 
3572 jermar 422
/** Chop off node clusters in all copies of FAT.
423
 *
424
 * @param bs        Buffer holding the boot sector of the file system.
425
 * @param nodep     FAT node where the chopping will take place.
426
 * @param lastc     Last cluster which will remain in the node. If this
427
 *          argument is FAT_CLST_RES0, then all clusters will
3573 jermar 428
 *          be chopped off.
3572 jermar 429
 */
430
void fat_chop_clusters(fat_bs_t *bs, fat_node_t *nodep, fat_cluster_t lastc)
431
{
432
    dev_handle_t dev_handle = nodep->idx->dev_handle;
433
    if (lastc == FAT_CLST_RES0) {
434
        /* The node will have zero size and no clusters allocated. */
435
        fat_free_clusters(bs, dev_handle, nodep->firstc);
436
        nodep->firstc = FAT_CLST_RES0;
437
        nodep->dirty = true;        /* need to sync node */
438
    } else {
439
        fat_cluster_t nextc;
440
        unsigned fatno;
441
 
442
        nextc = fat_get_cluster(bs, dev_handle, lastc);
443
 
444
        /* Terminate the cluster chain in all copies of FAT. */
445
        for (fatno = FAT1; fatno < bs->fatcnt; fatno++)
446
            fat_set_cluster(bs, dev_handle, fatno, lastc, FAT_CLST_LAST1);
447
 
448
        /* Free all following clusters. */
449
        fat_free_clusters(bs, dev_handle, nextc);
450
    }
451
}
452
 
3504 jermar 453
/**
454
 * @}
455
 */