Subversion Repositories HelenOS

Rev

Rev 4537 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
4419 trochtova 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
35
 * @brief   Functions that manipulate the File Allocation Tables.
36
 */
37
 
38
#include "fat_fat.h"
39
#include "fat_dentry.h"
40
#include "fat.h"
41
#include "../../vfs/vfs.h"
42
#include <libfs.h>
43
#include <libblock.h>
44
#include <errno.h>
45
#include <byteorder.h>
46
#include <align.h>
47
#include <assert.h>
4668 trochtova 48
#include <fibril_sync.h>
4537 trochtova 49
#include <mem.h>
4419 trochtova 50
 
51
/**
4668 trochtova 52
 * The fat_alloc_lock mutex protects all copies of the File Allocation Table
4419 trochtova 53
 * during allocation of clusters. The lock does not have to be held durring
54
 * deallocation of clusters.
55
 */  
4668 trochtova 56
static FIBRIL_MUTEX_INITIALIZE(fat_alloc_lock);
4419 trochtova 57
 
58
/** Walk the cluster chain.
59
 *
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.
63
 * @param lastc     If non-NULL, output argument hodling the last cluster number visited.
64
 * @param max_clusters  Maximum number of clusters to visit.   
65
 *
66
 * @return      Number of clusters seen during the walk.
67
 */
68
uint16_t
69
fat_cluster_walk(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t firstc,
70
    fat_cluster_t *lastc, uint16_t max_clusters)
71
{
72
    block_t *b;
73
    unsigned bps;
74
    unsigned rscnt;     /* block address of the first FAT */
75
    uint16_t clusters = 0;
76
    fat_cluster_t clst = firstc;
77
 
78
    bps = uint16_t_le2host(bs->bps);
79
    rscnt = uint16_t_le2host(bs->rscnt);
80
 
81
    if (firstc == FAT_CLST_RES0) {
82
        /* No space allocated to the file. */
83
        if (lastc)
84
            *lastc = firstc;
85
        return 0;
86
    }
87
 
88
    while (clst < FAT_CLST_LAST1 && clusters < max_clusters) {
89
        bn_t fsec;  /* sector offset relative to FAT1 */
90
        unsigned fidx;  /* FAT1 entry index */
91
 
92
        assert(clst >= FAT_CLST_FIRST);
93
        if (lastc)
94
            *lastc = clst;  /* remember the last cluster number */
95
        fsec = (clst * sizeof(fat_cluster_t)) / bps;
96
        fidx = clst % (bps / sizeof(fat_cluster_t));
97
        /* read FAT1 */
98
        b = block_get(dev_handle, rscnt + fsec, BLOCK_FLAGS_NONE);
99
        clst = uint16_t_le2host(((fat_cluster_t *)b->data)[fidx]);
100
        assert(clst != FAT_CLST_BAD);
101
        block_put(b);
102
        clusters++;
103
    }
104
 
105
    if (lastc && clst < FAT_CLST_LAST1)
106
        *lastc = clst;
107
 
108
    return clusters;
109
}
110
 
111
/** Read block from file located on a FAT file system.
112
 *
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.
117
 * @param bn        Block number.
118
 * @param flags     Flags passed to libblock.
119
 *
120
 * @return      Block structure holding the requested block.
121
 */
122
block_t *
123
_fat_block_get(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t firstc,
124
    bn_t bn, int flags)
125
{
126
    block_t *b;
127
    unsigned bps;
128
    unsigned rscnt;     /* block address of the first FAT */
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;
134
    fat_cluster_t lastc;
135
 
136
    bps = uint16_t_le2host(bs->bps);
137
    rscnt = uint16_t_le2host(bs->rscnt);
138
    rde = uint16_t_le2host(bs->root_ent_max);
139
    sf = uint16_t_le2host(bs->sec_per_fat);
140
 
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 */
147
        assert(bn < rds);
148
        b = block_get(dev_handle, rscnt + bs->fatcnt * sf + bn, flags);
149
        return b;
150
    }
151
 
152
    max_clusters = bn / bs->spc;
153
    clusters = fat_cluster_walk(bs, dev_handle, firstc, &lastc,
154
        max_clusters);
155
    assert(clusters == max_clusters);
156
 
157
    b = block_get(dev_handle, ssa + (lastc - FAT_CLST_FIRST) * bs->spc +
158
        bn % bs->spc, flags);
159
 
160
    return b;
161
}
162
 
163
/** Fill the gap between EOF and a new file position.
164
 *
165
 * @param bs        Buffer holding the boot sector for nodep.
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
 */
173
void fat_fill_gap(fat_bs_t *bs, fat_node_t *nodep, fat_cluster_t mcl, off_t pos)
174
{
175
    uint16_t bps;
176
    unsigned spc;
177
    block_t *b;
178
    off_t o, boundary;
179
 
180
    bps = uint16_t_le2host(bs->bps);
181
    spc = bs->spc;
182
 
183
    boundary = ROUND_UP(nodep->size, bps * spc);
184
 
185
    /* zero out already allocated space */
186
    for (o = nodep->size; o < pos && o < boundary;
187
        o = ALIGN_DOWN(o + bps, bps)) {
188
            int flags = (o % bps == 0) ?
189
            BLOCK_FLAGS_NOREAD : BLOCK_FLAGS_NONE;
190
        b = fat_block_get(bs, nodep, o / bps, flags);
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) {
201
        b = _fat_block_get(bs, nodep->idx->dev_handle, mcl,
202
            (o - boundary) / bps, BLOCK_FLAGS_NOREAD);
203
        memset(b->data, 0, min(bps, pos - o));
204
        b->dirty = true;        /* need to sync node */
205
        block_put(b);
206
    }
207
}
208
 
209
/** Get cluster from the first FAT.
210
 *
211
 * @param bs        Buffer holding the boot sector for the file system.
212
 * @param dev_handle    Device handle for the file system.
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
 
228
    b = block_get(dev_handle, rscnt + (clst * sizeof(fat_cluster_t)) / bps,
229
        BLOCK_FLAGS_NONE);
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.
241
 * @param fatno     Number of the FAT instance where to make the change.
242
 * @param clst      Cluster which is to be set.
243
 * @param value     Value to set the cluster with.
244
 */
245
void
246
fat_set_cluster(fat_bs_t *bs, dev_handle_t dev_handle, unsigned fatno,
247
    fat_cluster_t clst, fat_cluster_t value)
248
{
249
    block_t *b;
250
    uint16_t bps;
251
    uint16_t rscnt;
252
    uint16_t sf;
253
    fat_cluster_t *cp;
254
 
255
    bps = uint16_t_le2host(bs->bps);
256
    rscnt = uint16_t_le2host(bs->rscnt);
257
    sf = uint16_t_le2host(bs->sec_per_fat);
258
 
259
    assert(fatno < bs->fatcnt);
260
    b = block_get(dev_handle, rscnt + sf * fatno +
261
        (clst * sizeof(fat_cluster_t)) / bps, BLOCK_FLAGS_NONE);
262
    cp = (fat_cluster_t *)b->data + clst % (bps / sizeof(fat_cluster_t));
263
    *cp = host2uint16_t_le(value);
264
    b->dirty = true;        /* need to sync block */
265
    block_put(b);
266
}
267
 
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
 */
275
void fat_alloc_shadow_clusters(fat_bs_t *bs, dev_handle_t dev_handle,
276
    fat_cluster_t *lifo, unsigned nclsts)
277
{
278
    uint8_t fatno;
279
    unsigned c;
280
 
281
    for (fatno = FAT1 + 1; fatno < bs->fatcnt; fatno++) {
282
        for (c = 0; c < nclsts; c++) {
283
            fat_set_cluster(bs, dev_handle, fatno, lifo[c],
284
                c == 0 ? FAT_CLST_LAST1 : lifo[c - 1]);
285
        }
286
    }
287
}
288
 
289
/** Allocate clusters in all copies of FAT.
290
 *
291
 * This function will attempt to allocate the requested number of clusters in
292
 * all instances of the FAT.  The FAT will be altered so that the allocated
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
 */
306
int
307
fat_alloc_clusters(fat_bs_t *bs, dev_handle_t dev_handle, unsigned nclsts,
308
    fat_cluster_t *mcl, fat_cluster_t *lcl)
309
{
310
    uint16_t bps;
311
    uint16_t rscnt;
312
    uint16_t sf;
313
    block_t *blk;
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));
319
    if (!lifo)
320
        return ENOMEM;
321
 
322
    bps = uint16_t_le2host(bs->bps);
323
    rscnt = uint16_t_le2host(bs->rscnt);
324
    sf = uint16_t_le2host(bs->sec_per_fat);
325
 
326
    /*
327
     * Search FAT1 for unused clusters.
328
     */
4668 trochtova 329
    fibril_mutex_lock(&fat_alloc_lock);
4419 trochtova 330
    for (b = 0, cl = 0; b < sf; b++) {
331
        blk = block_get(dev_handle, rscnt + b, BLOCK_FLAGS_NONE);
332
        for (c = 0; c < bps / sizeof(fat_cluster_t); c++, cl++) {
333
            fat_cluster_t *clst = (fat_cluster_t *)blk->data + c;
334
            if (uint16_t_le2host(*clst) == FAT_CLST_RES0) {
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;
340
                *clst = (found == 0) ?
341
                    host2uint16_t_le(FAT_CLST_LAST1) :
342
                    host2uint16_t_le(lifo[found - 1]);
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 */
348
                    fat_alloc_shadow_clusters(bs,
349
                        dev_handle, lifo, nclsts);
350
                    *mcl = lifo[found - 1];
351
                    *lcl = lifo[0];
352
                    free(lifo);
4668 trochtova 353
                    fibril_mutex_unlock(&fat_alloc_lock);
4419 trochtova 354
                    return EOK;
355
                }
356
            }
357
        }
358
        block_put(blk);
359
    }
4668 trochtova 360
    fibril_mutex_unlock(&fat_alloc_lock);
4419 trochtova 361
 
362
    /*
363
     * We could not find enough clusters. Now we need to free the clusters
364
     * we have allocated so far.
365
     */
366
    while (found--) {
367
        fat_set_cluster(bs, dev_handle, FAT1, lifo[found],
368
            FAT_CLST_RES0);
369
    }
370
 
371
    free(lifo);
372
    return ENOSPC;
373
}
374
 
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) {
389
        assert(firstc >= FAT_CLST_FIRST && firstc < FAT_CLST_BAD);
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
 
398
/** Append a cluster chain to the last file cluster in all FATs.
399
 *
400
 * @param bs        Buffer holding the boot sector of the file system.
401
 * @param nodep     Node representing the file.
402
 * @param mcl       First cluster of the cluster chain to append.
403
 */
404
void fat_append_clusters(fat_bs_t *bs, fat_node_t *nodep, fat_cluster_t mcl)
405
{
406
    dev_handle_t dev_handle = nodep->idx->dev_handle;
407
    fat_cluster_t lcl;
408
    uint8_t fatno;
409
 
410
    if (fat_cluster_walk(bs, dev_handle, nodep->firstc, &lcl,
411
        (uint16_t) -1) == 0) {
412
        /* No clusters allocated to the node yet. */
413
        nodep->firstc = mcl;
414
        nodep->dirty = true;        /* need to sync node */
415
        return;
416
    }
417
 
418
    for (fatno = FAT1; fatno < bs->fatcnt; fatno++)
419
        fat_set_cluster(bs, nodep->idx->dev_handle, fatno, lcl, mcl);
420
}
421
 
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
428
 *          be chopped off.
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
 
453
/**
454
 * @}
455
 */