1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
|
/*-
* modified for Lites 1.1
*
* Aug 1995, Godmar Back (gback@cs.utah.edu)
* University of Utah, Department of Computer Science
*/
/*-
* Copyright (c) 1982, 1986, 1989, 1993
* The Regents of the University of California. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. 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.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``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 REGENTS OR CONTRIBUTORS 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.
*
* @(#)ffs_alloc.c 8.8 (Berkeley) 2/21/94
* $FreeBSD$
*/
#include <sys/param.h>
#include <sys/systm.h>
#include <sys/conf.h>
#include <sys/vnode.h>
#include <sys/stat.h>
#include <sys/mount.h>
#include <sys/syslog.h>
#include <gnu/fs/ext2fs/inode.h>
#include <gnu/fs/ext2fs/ext2_mount.h>
#include <gnu/fs/ext2fs/ext2_fs.h>
#include <gnu/fs/ext2fs/ext2_fs_sb.h>
#include <gnu/fs/ext2fs/fs.h>
#include <gnu/fs/ext2fs/ext2_extern.h>
static void ext2_fserr(struct ext2_sb_info *, u_int, char *);
/*
* Linux calls this functions at the following locations:
* (1) the inode is freed
* (2) a preallocation miss occurs
* (3) truncate is called
* (4) release_file is called and f_mode & 2
*
* I call it in ext2_inactive, ext2_truncate, ext2_vfree and in (2)
* the call in vfree might be redundant
*/
void
ext2_discard_prealloc(ip)
struct inode * ip;
{
#ifdef EXT2_PREALLOCATE
if (ip->i_prealloc_count) {
int i = ip->i_prealloc_count;
ip->i_prealloc_count = 0;
ext2_free_blocks (ITOV(ip)->v_mount,
ip->i_prealloc_block,
i);
}
#endif
}
/*
* Allocate a block in the file system.
*
* this takes the framework from ffs_alloc. To implement the
* actual allocation, it calls ext2_new_block, the ported version
* of the same Linux routine.
*
* we note that this is always called in connection with ext2_blkpref
*
* preallocation is done as Linux does it
*/
int
ext2_alloc(ip, lbn, bpref, size, cred, bnp)
struct inode *ip;
int32_t lbn, bpref;
int size;
struct ucred *cred;
int32_t *bnp;
{
struct ext2_sb_info *fs;
int32_t bno;
*bnp = 0;
fs = ip->i_e2fs;
#ifdef DIAGNOSTIC
if ((u_int)size > fs->s_blocksize || blkoff(fs, size) != 0) {
vn_printf(ip->i_devvp, "bsize = %lu, size = %d, fs = %s\n",
fs->s_blocksize, size, fs->fs_fsmnt);
panic("ext2_alloc: bad size");
}
if (cred == NOCRED)
panic("ext2_alloc: missing credential");
#endif /* DIAGNOSTIC */
if (size == fs->s_blocksize && fs->s_es->s_free_blocks_count == 0)
goto nospace;
if (cred->cr_uid != 0 &&
fs->s_es->s_free_blocks_count < fs->s_es->s_r_blocks_count)
goto nospace;
if (bpref >= fs->s_es->s_blocks_count)
bpref = 0;
/* call the Linux code */
#ifdef EXT2_PREALLOCATE
/* To have a preallocation hit, we must
* - have at least one block preallocated
* - and our preferred block must have that block number or one below
*/
if (ip->i_prealloc_count &&
(bpref == ip->i_prealloc_block ||
bpref + 1 == ip->i_prealloc_block))
{
bno = ip->i_prealloc_block++;
ip->i_prealloc_count--;
/* ext2_debug ("preallocation hit (%lu/%lu).\n",
++alloc_hits, ++alloc_attempts); */
/* Linux gets, clears, and releases the buffer at this
point - we don't have to that; we leave it to the caller
*/
} else {
ext2_discard_prealloc (ip);
/* ext2_debug ("preallocation miss (%lu/%lu).\n",
alloc_hits, ++alloc_attempts); */
if (S_ISREG(ip->i_mode))
bno = ext2_new_block
(ITOV(ip)->v_mount, bpref,
&ip->i_prealloc_count,
&ip->i_prealloc_block);
else
bno = (int32_t)ext2_new_block(ITOV(ip)->v_mount,
bpref, 0, 0);
}
#else
bno = (int32_t)ext2_new_block(ITOV(ip)->v_mount, bpref, 0, 0);
#endif
if (bno > 0) {
/* set next_alloc fields as done in block_getblk */
ip->i_next_alloc_block = lbn;
ip->i_next_alloc_goal = bno;
ip->i_blocks += btodb(size);
ip->i_flag |= IN_CHANGE | IN_UPDATE;
*bnp = bno;
return (0);
}
nospace:
ext2_fserr(fs, cred->cr_uid, "file system full");
uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt);
return (ENOSPC);
}
/*
* Reallocate a sequence of blocks into a contiguous sequence of blocks.
*
* The vnode and an array of buffer pointers for a range of sequential
* logical blocks to be made contiguous is given. The allocator attempts
* to find a range of sequential blocks starting as close as possible to
* an fs_rotdelay offset from the end of the allocation for the logical
* block immediately preceding the current range. If successful, the
* physical block numbers in the buffer pointers and in the inode are
* changed to reflect the new allocation. If unsuccessful, the allocation
* is left unchanged. The success in doing the reallocation is returned.
* Note that the error return is not reflected back to the user. Rather
* the previous block allocation will be used.
*/
#ifdef FANCY_REALLOC
#include <sys/sysctl.h>
static int doasyncfree = 1;
#ifdef OPT_DEBUG
SYSCTL_INT(_debug, 14, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, "");
#endif /* OPT_DEBUG */
#endif
int
ext2_reallocblks(ap)
struct vop_reallocblks_args /* {
struct vnode *a_vp;
struct cluster_save *a_buflist;
} */ *ap;
{
#ifndef FANCY_REALLOC
/* printf("ext2_reallocblks not implemented\n"); */
return ENOSPC;
#else
struct ext2_sb_info *fs;
struct inode *ip;
struct vnode *vp;
struct buf *sbp, *ebp;
int32_t *bap, *sbap, *ebap;
struct cluster_save *buflist;
int32_t start_lbn, end_lbn, soff, eoff, newblk, blkno;
struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp;
int i, len, start_lvl, end_lvl, pref, ssize;
vp = ap->a_vp;
ip = VTOI(vp);
fs = ip->i_e2fs;
#ifdef UNKLAR
if (fs->fs_contigsumsize <= 0)
return (ENOSPC);
#endif
buflist = ap->a_buflist;
len = buflist->bs_nchildren;
start_lbn = buflist->bs_children[0]->b_lblkno;
end_lbn = start_lbn + len - 1;
#ifdef DIAGNOSTIC
for (i = 1; i < len; i++)
if (buflist->bs_children[i]->b_lblkno != start_lbn + i)
panic("ext2_reallocblks: non-cluster");
#endif
/*
* If the latest allocation is in a new cylinder group, assume that
* the filesystem has decided to move and do not force it back to
* the previous cylinder group.
*/
if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) !=
dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno)))
return (ENOSPC);
if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) ||
ufs_getlbns(vp, end_lbn, end_ap, &end_lvl))
return (ENOSPC);
/*
* Get the starting offset and block map for the first block.
*/
if (start_lvl == 0) {
sbap = &ip->i_db[0];
soff = start_lbn;
} else {
idp = &start_ap[start_lvl - 1];
if (bread(vp, idp->in_lbn, (int)fs->s_blocksize, NOCRED, &sbp)) {
brelse(sbp);
return (ENOSPC);
}
sbap = (int32_t *)sbp->b_data;
soff = idp->in_off;
}
/*
* Find the preferred location for the cluster.
*/
pref = ext2_blkpref(ip, start_lbn, soff, sbap);
/*
* If the block range spans two block maps, get the second map.
*/
if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) {
ssize = len;
} else {
#ifdef DIAGNOSTIC
if (start_ap[start_lvl-1].in_lbn == idp->in_lbn)
panic("ext2_reallocblk: start == end");
#endif
ssize = len - (idp->in_off + 1);
if (bread(vp, idp->in_lbn, (int)fs->s_blocksize, NOCRED, &ebp))
goto fail;
ebap = (int32_t *)ebp->b_data;
}
/*
* Search the block map looking for an allocation of the desired size.
*/
if ((newblk = (int32_t)ext2_hashalloc(ip, dtog(fs, pref), (long)pref,
len, (u_long (*)())ext2_clusteralloc)) == 0)
goto fail;
/*
* We have found a new contiguous block.
*
* First we have to replace the old block pointers with the new
* block pointers in the inode and indirect blocks associated
* with the file.
*/
blkno = newblk;
for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->s_frags_per_block) {
if (i == ssize)
bap = ebap;
#ifdef DIAGNOSTIC
if (buflist->bs_children[i]->b_blkno != fsbtodb(fs, *bap))
panic("ext2_reallocblks: alloc mismatch");
#endif
*bap++ = blkno;
}
/*
* Next we must write out the modified inode and indirect blocks.
* For strict correctness, the writes should be synchronous since
* the old block values may have been written to disk. In practise
* they are almost never written, but if we are concerned about
* strict correctness, the `doasyncfree' flag should be set to zero.
*
* The test on `doasyncfree' should be changed to test a flag
* that shows whether the associated buffers and inodes have
* been written. The flag should be set when the cluster is
* started and cleared whenever the buffer or inode is flushed.
* We can then check below to see if it is set, and do the
* synchronous write only when it has been cleared.
*/
if (sbap != &ip->i_db[0]) {
if (doasyncfree)
bdwrite(sbp);
else
bwrite(sbp);
} else {
ip->i_flag |= IN_CHANGE | IN_UPDATE;
if (!doasyncfree)
ext2_update(vp, 1);
}
if (ssize < len)
if (doasyncfree)
bdwrite(ebp);
else
bwrite(ebp);
/*
* Last, free the old blocks and assign the new blocks to the buffers.
*/
for (blkno = newblk, i = 0; i < len; i++, blkno += fs->s_frags_per_block) {
ext2_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno),
fs->s_blocksize);
buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno);
}
return (0);
fail:
if (ssize < len)
brelse(ebp);
if (sbap != &ip->i_db[0])
brelse(sbp);
return (ENOSPC);
#endif /* FANCY_REALLOC */
}
/*
* Allocate an inode in the file system.
*
* we leave the actual allocation strategy to the (modified)
* ext2_new_inode(), to make sure we get the policies right
*/
int
ext2_valloc(pvp, mode, cred, vpp)
struct vnode *pvp;
int mode;
struct ucred *cred;
struct vnode **vpp;
{
struct inode *pip;
struct ext2_sb_info *fs;
struct inode *ip;
ino_t ino;
int i, error;
*vpp = NULL;
pip = VTOI(pvp);
fs = pip->i_e2fs;
if (fs->s_es->s_free_inodes_count == 0)
goto noinodes;
/* call the Linux routine - it returns the inode number only */
ino = ext2_new_inode(pip, mode);
if (ino == 0)
goto noinodes;
error = VFS_VGET(pvp->v_mount, ino, LK_EXCLUSIVE, vpp);
if (error) {
ext2_vfree(pvp, ino, mode);
return (error);
}
ip = VTOI(*vpp);
/*
the question is whether using VGET was such good idea at all -
Linux doesn't read the old inode in when it's allocating a
new one. I will set at least i_size & i_blocks the zero.
*/
ip->i_mode = 0;
ip->i_size = 0;
ip->i_blocks = 0;
ip->i_flags = 0;
/* now we want to make sure that the block pointers are zeroed out */
for (i = 0; i < NDADDR; i++)
ip->i_db[i] = 0;
for (i = 0; i < NIADDR; i++)
ip->i_ib[i] = 0;
/*
* Set up a new generation number for this inode.
* XXX check if this makes sense in ext2
*/
if (ip->i_gen == 0 || ++ip->i_gen == 0)
ip->i_gen = random() / 2 + 1;
/*
printf("ext2_valloc: allocated inode %d\n", ino);
*/
return (0);
noinodes:
ext2_fserr(fs, cred->cr_uid, "out of inodes");
uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt);
return (ENOSPC);
}
/*
* Select the desired position for the next block in a file.
*
* we try to mimic what Remy does in inode_getblk/block_getblk
*
* we note: blocknr == 0 means that we're about to allocate either
* a direct block or a pointer block at the first level of indirection
* (In other words, stuff that will go in i_db[] or i_ib[])
*
* blocknr != 0 means that we're allocating a block that is none
* of the above. Then, blocknr tells us the number of the block
* that will hold the pointer
*/
int32_t
ext2_blkpref(ip, lbn, indx, bap, blocknr)
struct inode *ip;
int32_t lbn;
int indx;
int32_t *bap;
int32_t blocknr;
{
int tmp;
/* if the next block is actually what we thought it is,
then set the goal to what we thought it should be
*/
if(ip->i_next_alloc_block == lbn)
return ip->i_next_alloc_goal;
/* now check whether we were provided with an array that basically
tells us previous blocks to which we want to stay closeby
*/
if(bap)
for (tmp = indx - 1; tmp >= 0; tmp--)
if (bap[tmp])
return bap[tmp];
/* else let's fall back to the blocknr, or, if there is none,
follow the rule that a block should be allocated near its inode
*/
return blocknr ? blocknr :
(int32_t)(ip->i_block_group *
EXT2_BLOCKS_PER_GROUP(ip->i_e2fs)) +
ip->i_e2fs->s_es->s_first_data_block;
}
/*
* Free a block or fragment.
*
* pass on to the Linux code
*/
void
ext2_blkfree(ip, bno, size)
struct inode *ip;
int32_t bno;
long size;
{
struct ext2_sb_info *fs;
fs = ip->i_e2fs;
/*
* call Linux code with mount *, block number, count
*/
ext2_free_blocks(ITOV(ip)->v_mount, bno, size / fs->s_frag_size);
}
/*
* Free an inode.
*
* the maintenance of the actual bitmaps is again up to the linux code
*/
int
ext2_vfree(pvp, ino, mode)
struct vnode *pvp;
ino_t ino;
int mode;
{
struct ext2_sb_info *fs;
struct inode *pip;
mode_t save_i_mode;
pip = VTOI(pvp);
fs = pip->i_e2fs;
if ((u_int)ino > fs->s_inodes_per_group * fs->s_groups_count)
panic("ext2_vfree: range: devvp = %p, ino = %d, fs = %s",
pip->i_devvp, ino, fs->fs_fsmnt);
/* ext2_debug("ext2_vfree (%d, %d) called\n", pip->i_number, mode);
*/
ext2_discard_prealloc(pip);
/* we need to make sure that ext2_free_inode can adjust the
used_dir_counts in the group summary information - I'd
really like to know what the rationale behind this
'set i_mode to zero to denote an unused inode' is
*/
save_i_mode = pip->i_mode;
pip->i_mode = mode;
ext2_free_inode(pip);
pip->i_mode = save_i_mode;
return (0);
}
/*
* Fserr prints the name of a file system with an error diagnostic.
*
* The form of the error message is:
* fs: error message
*/
static void
ext2_fserr(fs, uid, cp)
struct ext2_sb_info *fs;
u_int uid;
char *cp;
{
log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->fs_fsmnt, cp);
}
|