1/* $NetBSD: ext2fs_alloc.c,v 1.51 2016/08/20 19:53:43 jdolecek Exp $ */
2
3/*
4 * Copyright (c) 1982, 1986, 1989, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 *
31 * @(#)ffs_alloc.c 8.11 (Berkeley) 10/27/94
32 * Modified for ext2fs by Manuel Bouyer.
33 */
34
35/*
36 * Copyright (c) 1997 Manuel Bouyer.
37 *
38 * Redistribution and use in source and binary forms, with or without
39 * modification, are permitted provided that the following conditions
40 * are met:
41 * 1. Redistributions of source code must retain the above copyright
42 * notice, this list of conditions and the following disclaimer.
43 * 2. Redistributions in binary form must reproduce the above copyright
44 * notice, this list of conditions and the following disclaimer in the
45 * documentation and/or other materials provided with the distribution.
46 *
47 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
48 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
49 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
50 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
51 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
52 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
53 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
54 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
55 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
56 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
57 *
58 * @(#)ffs_alloc.c 8.11 (Berkeley) 10/27/94
59 * Modified for ext2fs by Manuel Bouyer.
60 */
61
62#include <sys/cdefs.h>
63__KERNEL_RCSID(0, "$NetBSD: ext2fs_alloc.c,v 1.51 2016/08/20 19:53:43 jdolecek Exp $");
64
65#include <sys/param.h>
66#include <sys/systm.h>
67#include <sys/buf.h>
68#include <sys/proc.h>
69#include <sys/vnode.h>
70#include <sys/mount.h>
71#include <sys/kernel.h>
72#include <sys/syslog.h>
73#include <sys/kauth.h>
74
75#include <lib/libkern/crc16.h>
76
77#include <ufs/ufs/inode.h>
78#include <ufs/ufs/ufs_extern.h>
79#include <ufs/ufs/ufsmount.h>
80
81#include <ufs/ext2fs/ext2fs.h>
82#include <ufs/ext2fs/ext2fs_extern.h>
83
84u_long ext2gennumber;
85
86static daddr_t ext2fs_alloccg(struct inode *, int, daddr_t, int);
87static u_long ext2fs_dirpref(struct m_ext2fs *);
88static void ext2fs_fserr(struct m_ext2fs *, u_int, const char *);
89static u_long ext2fs_hashalloc(struct inode *, int, long, int,
90 daddr_t (*)(struct inode *, int, daddr_t, int));
91static daddr_t ext2fs_nodealloccg(struct inode *, int, daddr_t, int);
92static daddr_t ext2fs_mapsearch(struct m_ext2fs *, char *, daddr_t);
93static __inline void ext2fs_cg_update(struct m_ext2fs *, int, struct ext2_gd *, int, int, int, daddr_t);
94static uint16_t ext2fs_cg_get_csum(struct m_ext2fs *, int, struct ext2_gd *);
95static void ext2fs_init_bb(struct m_ext2fs *, int, struct ext2_gd *, char *);
96
97/*
98 * Allocate a block in the file system.
99 *
100 * A preference may be optionally specified. If a preference is given
101 * the following hierarchy is used to allocate a block:
102 * 1) allocate the requested block.
103 * 2) allocate a rotationally optimal block in the same cylinder.
104 * 3) allocate a block in the same cylinder group.
105 * 4) quadradically rehash into other cylinder groups, until an
106 * available block is located.
107 * If no block preference is given the following hierarchy is used
108 * to allocate a block:
109 * 1) allocate a block in the cylinder group that contains the
110 * inode for the file.
111 * 2) quadradically rehash into other cylinder groups, until an
112 * available block is located.
113 */
114int
115ext2fs_alloc(struct inode *ip, daddr_t lbn, daddr_t bpref,
116 kauth_cred_t cred, daddr_t *bnp)
117{
118 struct m_ext2fs *fs;
119 daddr_t bno;
120 int cg;
121
122 *bnp = 0;
123 fs = ip->i_e2fs;
124#ifdef DIAGNOSTIC
125 if (cred == NOCRED)
126 panic("ext2fs_alloc: missing credential");
127#endif /* DIAGNOSTIC */
128 if (fs->e2fs.e2fs_fbcount == 0)
129 goto nospace;
130 if (kauth_authorize_system(cred, KAUTH_SYSTEM_FS_RESERVEDSPACE, 0, NULL,
131 NULL, NULL) != 0 &&
132 freespace(fs) <= 0)
133 goto nospace;
134 if (bpref >= fs->e2fs.e2fs_bcount)
135 bpref = 0;
136 if (bpref == 0)
137 cg = ino_to_cg(fs, ip->i_number);
138 else
139 cg = dtog(fs, bpref);
140 bno = (daddr_t)ext2fs_hashalloc(ip, cg, bpref, fs->e2fs_bsize,
141 ext2fs_alloccg);
142 if (bno > 0) {
143 ext2fs_setnblock(ip, ext2fs_nblock(ip) + btodb(fs->e2fs_bsize));
144 ip->i_flag |= IN_CHANGE | IN_UPDATE;
145 *bnp = bno;
146 return 0;
147 }
148nospace:
149 ext2fs_fserr(fs, kauth_cred_geteuid(cred), "file system full");
150 uprintf("\n%s: write failed, file system is full\n", fs->e2fs_fsmnt);
151 return ENOSPC;
152}
153
154/*
155 * Allocate an inode in the file system.
156 *
157 * If allocating a directory, use ext2fs_dirpref to select the inode.
158 * If allocating in a directory, the following hierarchy is followed:
159 * 1) allocate the preferred inode.
160 * 2) allocate an inode in the same cylinder group.
161 * 3) quadradically rehash into other cylinder groups, until an
162 * available inode is located.
163 * If no inode preference is given the following hierarchy is used
164 * to allocate an inode:
165 * 1) allocate an inode in cylinder group 0.
166 * 2) quadradically rehash into other cylinder groups, until an
167 * available inode is located.
168 */
169int
170ext2fs_valloc(struct vnode *pvp, int mode, kauth_cred_t cred,
171 struct vnode **vpp)
172{
173 struct inode *pip;
174 struct m_ext2fs *fs;
175 struct inode *ip;
176 ino_t ino, ipref;
177 int cg, error;
178
179 *vpp = NULL;
180 pip = VTOI(pvp);
181 fs = pip->i_e2fs;
182 if (fs->e2fs.e2fs_ficount == 0)
183 goto noinodes;
184
185 if ((mode & IFMT) == IFDIR)
186 cg = ext2fs_dirpref(fs);
187 else
188 cg = ino_to_cg(fs, pip->i_number);
189 ipref = cg * fs->e2fs.e2fs_ipg + 1;
190 ino = (ino_t)ext2fs_hashalloc(pip, cg, (long)ipref, mode, ext2fs_nodealloccg);
191 if (ino == 0)
192 goto noinodes;
193 error = VFS_VGET(pvp->v_mount, ino, vpp);
194 if (error) {
195 ext2fs_vfree(pvp, ino, mode);
196 return error;
197 }
198 ip = VTOI(*vpp);
199
200 KASSERT(!E2FS_HAS_GD_CSUM(fs) || (fs->e2fs_gd[ino_to_cg(fs, ino)].ext2bgd_flags & h2fs16(E2FS_BG_INODE_ZEROED)) != 0);
201
202 /* check for already used inode; makes sense only for ZEROED itable */
203 if (__predict_false(ip->i_e2fs_mode && ip->i_e2fs_nlink != 0)) {
204 printf("mode = 0%o, nlinks %d, inum = %llu, fs = %s\n",
205 ip->i_e2fs_mode, ip->i_e2fs_nlink,
206 (unsigned long long)ip->i_number, fs->e2fs_fsmnt);
207 panic("ext2fs_valloc: dup alloc");
208 }
209
210 memset(ip->i_din.e2fs_din, 0, EXT2_DINODE_SIZE(fs));
211
212 /*
213 * Set up a new generation number for this inode.
214 */
215 if (++ext2gennumber < time_second)
216 ext2gennumber = time_second;
217 ip->i_e2fs_gen = ext2gennumber;
218 return 0;
219noinodes:
220 ext2fs_fserr(fs, kauth_cred_geteuid(cred), "out of inodes");
221 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->e2fs_fsmnt);
222 return ENOSPC;
223}
224
225/*
226 * Find a cylinder to place a directory.
227 *
228 * The policy implemented by this algorithm is to select from
229 * among those cylinder groups with above the average number of
230 * free inodes, the one with the smallest number of directories.
231 */
232static u_long
233ext2fs_dirpref(struct m_ext2fs *fs)
234{
235 int cg, maxspace, mincg, avgifree;
236
237 avgifree = fs->e2fs.e2fs_ficount / fs->e2fs_ncg;
238 maxspace = 0;
239 mincg = -1;
240 for (cg = 0; cg < fs->e2fs_ncg; cg++)
241 if (fs2h16(fs->e2fs_gd[cg].ext2bgd_nifree) >= avgifree) {
242 if (mincg == -1 || fs2h16(fs->e2fs_gd[cg].ext2bgd_nbfree) > maxspace) {
243 mincg = cg;
244 maxspace = fs2h16(fs->e2fs_gd[cg].ext2bgd_nbfree);
245 }
246 }
247 return mincg;
248}
249
250/*
251 * Select the desired position for the next block in a file. The file is
252 * logically divided into sections. The first section is composed of the
253 * direct blocks. Each additional section contains fs_maxbpg blocks.
254 *
255 * If no blocks have been allocated in the first section, the policy is to
256 * request a block in the same cylinder group as the inode that describes
257 * the file. Otherwise, the policy is to try to allocate the blocks
258 * contigously. The two fields of the ext2 inode extension (see
259 * ufs/ufs/inode.h) help this.
260 */
261daddr_t
262ext2fs_blkpref(struct inode *ip, daddr_t lbn, int indx,
263 int32_t *bap /* XXX ondisk32 */)
264{
265 struct m_ext2fs *fs;
266 int cg, i;
267
268 fs = ip->i_e2fs;
269 /*
270 * if we are doing contigous lbn allocation, try to alloc blocks
271 * contigously on disk
272 */
273
274 if ( ip->i_e2fs_last_blk && lbn == ip->i_e2fs_last_lblk + 1) {
275 return ip->i_e2fs_last_blk + 1;
276 }
277
278 /*
279 * bap, if provided, gives us a list of blocks to which we want to
280 * stay close
281 */
282
283 if (bap) {
284 for (i = indx; i >= 0 ; i--) {
285 if (bap[i]) {
286 return fs2h32(bap[i]) + 1;
287 }
288 }
289 }
290
291 /* fall back to the first block of the cylinder containing the inode */
292
293 cg = ino_to_cg(fs, ip->i_number);
294 return fs->e2fs.e2fs_bpg * cg + fs->e2fs.e2fs_first_dblock + 1;
295}
296
297/*
298 * Implement the cylinder overflow algorithm.
299 *
300 * The policy implemented by this algorithm is:
301 * 1) allocate the block in its requested cylinder group.
302 * 2) quadradically rehash on the cylinder group number.
303 * 3) brute force search for a free block.
304 */
305static u_long
306ext2fs_hashalloc(struct inode *ip, int cg, long pref, int size,
307 daddr_t (*allocator)(struct inode *, int, daddr_t, int))
308{
309 struct m_ext2fs *fs;
310 long result;
311 int i, icg = cg;
312
313 fs = ip->i_e2fs;
314 /*
315 * 1: preferred cylinder group
316 */
317 result = (*allocator)(ip, cg, pref, size);
318 if (result)
319 return result;
320 /*
321 * 2: quadratic rehash
322 */
323 for (i = 1; i < fs->e2fs_ncg; i *= 2) {
324 cg += i;
325 if (cg >= fs->e2fs_ncg)
326 cg -= fs->e2fs_ncg;
327 result = (*allocator)(ip, cg, 0, size);
328 if (result)
329 return result;
330 }
331 /*
332 * 3: brute force search
333 * Note that we start at i == 2, since 0 was checked initially,
334 * and 1 is always checked in the quadratic rehash.
335 */
336 cg = (icg + 2) % fs->e2fs_ncg;
337 for (i = 2; i < fs->e2fs_ncg; i++) {
338 result = (*allocator)(ip, cg, 0, size);
339 if (result)
340 return result;
341 cg++;
342 if (cg == fs->e2fs_ncg)
343 cg = 0;
344 }
345 return 0;
346}
347
348/*
349 * Determine whether a block can be allocated.
350 *
351 * Check to see if a block of the appropriate size is available,
352 * and if it is, allocate it.
353 */
354
355static daddr_t
356ext2fs_alloccg(struct inode *ip, int cg, daddr_t bpref, int size)
357{
358 struct m_ext2fs *fs;
359 char *bbp;
360 struct buf *bp;
361 /* XXX ondisk32 */
362 int error, bno, start, end, loc;
363
364 fs = ip->i_e2fs;
365 if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0)
366 return 0;
367 error = bread(ip->i_devvp, EXT2_FSBTODB(fs,
368 fs2h32(fs->e2fs_gd[cg].ext2bgd_b_bitmap)),
369 (int)fs->e2fs_bsize, B_MODIFY, &bp);
370 if (error) {
371 return 0;
372 }
373 bbp = (char *)bp->b_data;
374
375 if (dtog(fs, bpref) != cg)
376 bpref = 0;
377
378 /* initialize block bitmap now if uninit */
379 if (__predict_false(E2FS_HAS_GD_CSUM(fs) &&
380 (fs->e2fs_gd[cg].ext2bgd_flags & h2fs16(E2FS_BG_BLOCK_UNINIT)))) {
381 ext2fs_init_bb(fs, cg, &fs->e2fs_gd[cg], bbp);
382 fs->e2fs_gd[cg].ext2bgd_flags &= h2fs16(~E2FS_BG_BLOCK_UNINIT);
383 }
384
385 if (bpref != 0) {
386 bpref = dtogd(fs, bpref);
387 /*
388 * if the requested block is available, use it
389 */
390 if (isclr(bbp, bpref)) {
391 bno = bpref;
392 goto gotit;
393 }
394 }
395 /*
396 * no blocks in the requested cylinder, so take next
397 * available one in this cylinder group.
398 * first try to get 8 contigous blocks, then fall back to a single
399 * block.
400 */
401 if (bpref)
402 start = dtogd(fs, bpref) / NBBY;
403 else
404 start = 0;
405 end = howmany(fs->e2fs.e2fs_fpg, NBBY) - start;
406 for (loc = start; loc < end; loc++) {
407 if (bbp[loc] == 0) {
408 bno = loc * NBBY;
409 goto gotit;
410 }
411 }
412 for (loc = 0; loc < start; loc++) {
413 if (bbp[loc] == 0) {
414 bno = loc * NBBY;
415 goto gotit;
416 }
417 }
418
419 bno = ext2fs_mapsearch(fs, bbp, bpref);
420#if 0
421 /*
422 * XXX jdolecek mapsearch actually never fails, it panics instead.
423 * If re-enabling, make sure to brele() before returning.
424 */
425 if (bno < 0)
426 return 0;
427#endif
428gotit:
429#ifdef DIAGNOSTIC
430 if (isset(bbp, (daddr_t)bno)) {
431 printf("ext2fs_alloccgblk: cg=%d bno=%d fs=%s\n",
432 cg, bno, fs->e2fs_fsmnt);
433 panic("ext2fs_alloccg: dup alloc");
434 }
435#endif
436 setbit(bbp, (daddr_t)bno);
437 fs->e2fs.e2fs_fbcount--;
438 ext2fs_cg_update(fs, cg, &fs->e2fs_gd[cg], -1, 0, 0, 0);
439 fs->e2fs_fmod = 1;
440 bdwrite(bp);
441 return cg * fs->e2fs.e2fs_fpg + fs->e2fs.e2fs_first_dblock + bno;
442}
443
444/*
445 * Determine whether an inode can be allocated.
446 *
447 * Check to see if an inode is available, and if it is,
448 * allocate it using the following policy:
449 * 1) allocate the requested inode.
450 * 2) allocate the next available inode after the requested
451 * inode in the specified cylinder group.
452 */
453static daddr_t
454ext2fs_nodealloccg(struct inode *ip, int cg, daddr_t ipref, int mode)
455{
456 struct m_ext2fs *fs;
457 char *ibp;
458 struct buf *bp;
459 int error, start, len, loc, map, i;
460
461 ipref--; /* to avoid a lot of (ipref -1) */
462 if (ipref == -1)
463 ipref = 0;
464 fs = ip->i_e2fs;
465 if (fs->e2fs_gd[cg].ext2bgd_nifree == 0)
466 return 0;
467 error = bread(ip->i_devvp, EXT2_FSBTODB(fs,
468 fs2h32(fs->e2fs_gd[cg].ext2bgd_i_bitmap)),
469 (int)fs->e2fs_bsize, B_MODIFY, &bp);
470 if (error) {
471 return 0;
472 }
473 ibp = (char *)bp->b_data;
474
475 KASSERT(!E2FS_HAS_GD_CSUM(fs) || (fs->e2fs_gd[cg].ext2bgd_flags & h2fs16(E2FS_BG_INODE_ZEROED)) != 0);
476
477 /* initialize inode bitmap now if uninit */
478 if (__predict_false(E2FS_HAS_GD_CSUM(fs) &&
479 (fs->e2fs_gd[cg].ext2bgd_flags & h2fs16(E2FS_BG_INODE_UNINIT)))) {
480 KASSERT(fs2h16(fs->e2fs_gd[cg].ext2bgd_nifree) == fs->e2fs.e2fs_ipg);
481 memset(ibp, 0, fs->e2fs_bsize);
482 fs->e2fs_gd[cg].ext2bgd_flags &= h2fs16(~E2FS_BG_INODE_UNINIT);
483 }
484
485 if (ipref) {
486 ipref %= fs->e2fs.e2fs_ipg;
487 if (isclr(ibp, ipref))
488 goto gotit;
489 }
490 start = ipref / NBBY;
491 len = howmany(fs->e2fs.e2fs_ipg - ipref, NBBY);
492 loc = skpc(0xff, len, &ibp[start]);
493 if (loc == 0) {
494 len = start + 1;
495 start = 0;
496 loc = skpc(0xff, len, &ibp[0]);
497 if (loc == 0) {
498 printf("cg = %d, ipref = %lld, fs = %s\n",
499 cg, (long long)ipref, fs->e2fs_fsmnt);
500 panic("ext2fs_nodealloccg: map corrupted");
501 /* NOTREACHED */
502 }
503 }
504 i = start + len - loc;
505 map = ibp[i] ^ 0xff;
506 if (map == 0) {
507 printf("fs = %s\n", fs->e2fs_fsmnt);
508 panic("ext2fs_nodealloccg: inode not in map");
509 }
510 ipref = i * NBBY + ffs(map) - 1;
511gotit:
512 setbit(ibp, ipref);
513 fs->e2fs.e2fs_ficount--;
514 ext2fs_cg_update(fs, cg, &fs->e2fs_gd[cg],
515 0, -1, ((mode & IFMT) == IFDIR) ? 1 : 0, ipref);
516 fs->e2fs_fmod = 1;
517 bdwrite(bp);
518 return cg * fs->e2fs.e2fs_ipg + ipref + 1;
519}
520
521/*
522 * Free a block.
523 *
524 * The specified block is placed back in the
525 * free map.
526 */
527void
528ext2fs_blkfree(struct inode *ip, daddr_t bno)
529{
530 struct m_ext2fs *fs;
531 char *bbp;
532 struct buf *bp;
533 int error, cg;
534
535 fs = ip->i_e2fs;
536 cg = dtog(fs, bno);
537
538 KASSERT(!E2FS_HAS_GD_CSUM(fs) || (fs->e2fs_gd[cg].ext2bgd_flags & h2fs16(E2FS_BG_BLOCK_UNINIT)) == 0);
539
540 if ((u_int)bno >= fs->e2fs.e2fs_bcount) {
541 printf("bad block %lld, ino %llu\n", (long long)bno,
542 (unsigned long long)ip->i_number);
543 ext2fs_fserr(fs, ip->i_uid, "bad block");
544 return;
545 }
546 error = bread(ip->i_devvp,
547 EXT2_FSBTODB(fs, fs2h32(fs->e2fs_gd[cg].ext2bgd_b_bitmap)),
548 (int)fs->e2fs_bsize, B_MODIFY, &bp);
549 if (error) {
550 return;
551 }
552 bbp = (char *)bp->b_data;
553 bno = dtogd(fs, bno);
554 if (isclr(bbp, bno)) {
555 printf("dev = 0x%llx, block = %lld, fs = %s\n",
556 (unsigned long long)ip->i_dev, (long long)bno,
557 fs->e2fs_fsmnt);
558 panic("blkfree: freeing free block");
559 }
560 clrbit(bbp, bno);
561 fs->e2fs.e2fs_fbcount++;
562 ext2fs_cg_update(fs, cg, &fs->e2fs_gd[cg], 1, 0, 0, 0);
563 fs->e2fs_fmod = 1;
564 bdwrite(bp);
565}
566
567/*
568 * Free an inode.
569 *
570 * The specified inode is placed back in the free map.
571 */
572int
573ext2fs_vfree(struct vnode *pvp, ino_t ino, int mode)
574{
575 struct m_ext2fs *fs;
576 char *ibp;
577 struct inode *pip;
578 struct buf *bp;
579 int error, cg;
580
581 pip = VTOI(pvp);
582 fs = pip->i_e2fs;
583
584 if ((u_int)ino > fs->e2fs.e2fs_icount || (u_int)ino < EXT2_FIRSTINO)
585 panic("ifree: range: dev = 0x%llx, ino = %llu, fs = %s",
586 (unsigned long long)pip->i_dev, (unsigned long long)ino,
587 fs->e2fs_fsmnt);
588
589 cg = ino_to_cg(fs, ino);
590
591 KASSERT(!E2FS_HAS_GD_CSUM(fs) || (fs->e2fs_gd[cg].ext2bgd_flags & h2fs16(E2FS_BG_INODE_UNINIT)) == 0);
592
593 error = bread(pip->i_devvp,
594 EXT2_FSBTODB(fs, fs2h32(fs->e2fs_gd[cg].ext2bgd_i_bitmap)),
595 (int)fs->e2fs_bsize, B_MODIFY, &bp);
596 if (error) {
597 return 0;
598 }
599 ibp = (char *)bp->b_data;
600 ino = (ino - 1) % fs->e2fs.e2fs_ipg;
601 if (isclr(ibp, ino)) {
602 printf("dev = 0x%llx, ino = %llu, fs = %s\n",
603 (unsigned long long)pip->i_dev,
604 (unsigned long long)ino, fs->e2fs_fsmnt);
605 if (fs->e2fs_ronly == 0)
606 panic("ifree: freeing free inode");
607 }
608 clrbit(ibp, ino);
609 fs->e2fs.e2fs_ficount++;
610 ext2fs_cg_update(fs, cg, &fs->e2fs_gd[cg],
611 0, 1, ((mode & IFMT) == IFDIR) ? -1 : 0, 0);
612 fs->e2fs_fmod = 1;
613 bdwrite(bp);
614 return 0;
615}
616
617/*
618 * Find a block in the specified cylinder group.
619 *
620 * It is a panic if a request is made to find a block if none are
621 * available.
622 */
623
624static daddr_t
625ext2fs_mapsearch(struct m_ext2fs *fs, char *bbp, daddr_t bpref)
626{
627 int start, len, loc, i, map;
628
629 /*
630 * find the fragment by searching through the free block
631 * map for an appropriate bit pattern
632 */
633 if (bpref)
634 start = dtogd(fs, bpref) / NBBY;
635 else
636 start = 0;
637 len = howmany(fs->e2fs.e2fs_fpg, NBBY) - start;
638 loc = skpc(0xff, len, &bbp[start]);
639 if (loc == 0) {
640 len = start + 1;
641 start = 0;
642 loc = skpc(0xff, len, &bbp[start]);
643 if (loc == 0) {
644 printf("start = %d, len = %d, fs = %s\n",
645 start, len, fs->e2fs_fsmnt);
646 panic("ext2fs_alloccg: map corrupted");
647 /* NOTREACHED */
648 }
649 }
650 i = start + len - loc;
651 map = bbp[i] ^ 0xff;
652 if (map == 0) {
653 printf("fs = %s\n", fs->e2fs_fsmnt);
654 panic("ext2fs_mapsearch: block not in map");
655 }
656 return i * NBBY + ffs(map) - 1;
657}
658
659/*
660 * Fserr prints the name of a file system with an error diagnostic.
661 *
662 * The form of the error message is:
663 * fs: error message
664 */
665static void
666ext2fs_fserr(struct m_ext2fs *fs, u_int uid, const char *cp)
667{
668
669 log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->e2fs_fsmnt, cp);
670}
671
672static __inline void
673ext2fs_cg_update(struct m_ext2fs *fs, int cg, struct ext2_gd *gd, int nbfree, int nifree, int ndirs, daddr_t ioff)
674{
675 /* XXX disk32 */
676 if (nifree) {
677 gd->ext2bgd_nifree = h2fs16(fs2h16(gd->ext2bgd_nifree) + nifree);
678 /*
679 * If we allocated inode on bigger offset than what was
680 * ever used before, bump the itable_unused count. This
681 * member only ever grows, and is used only for initialization
682 * !INODE_ZEROED groups with used inodes. Of course, by the
683 * time we get here the itables are already zeroed, but
684 * e2fstools fsck.ext4 still checks this.
685 */
686 if (E2FS_HAS_GD_CSUM(fs) && nifree < 0 && (ioff+1) >= (fs->e2fs.e2fs_ipg - fs2h16(gd->ext2bgd_itable_unused_lo))) {
687 gd->ext2bgd_itable_unused_lo = h2fs16(fs->e2fs.e2fs_ipg - (ioff + 1));
688 }
689
690 KASSERT(!E2FS_HAS_GD_CSUM(fs) || gd->ext2bgd_itable_unused_lo <= gd->ext2bgd_nifree);
691 }
692
693
694 if (nbfree)
695 gd->ext2bgd_nbfree = h2fs16(fs2h16(gd->ext2bgd_nbfree) + nbfree);
696
697 if (ndirs)
698 gd->ext2bgd_ndirs = h2fs16(fs2h16(gd->ext2bgd_ndirs) + ndirs);
699
700 if (E2FS_HAS_GD_CSUM(fs))
701 gd->ext2bgd_checksum = ext2fs_cg_get_csum(fs, cg, gd);
702}
703
704/*
705 * Compute group description csum. Structure data must be LE (not host).
706 * Returned as LE (disk encoding).
707 */
708static uint16_t
709ext2fs_cg_get_csum(struct m_ext2fs *fs, int cg, struct ext2_gd *gd)
710{
711 uint16_t crc;
712 uint32_t cg_bswapped = h2fs32((uint32_t)cg);
713 size_t off;
714
715 if (!EXT2F_HAS_ROCOMPAT_FEATURE(fs, EXT2F_ROCOMPAT_GDT_CSUM))
716 return 0;
717
718 off = offsetof(struct ext2_gd, ext2bgd_checksum);
719
720 crc = crc16(~0, (uint8_t *)fs->e2fs.e2fs_uuid, sizeof(fs->e2fs.e2fs_uuid));
721 crc = crc16(crc, (uint8_t *)&cg_bswapped, sizeof(cg_bswapped));
722 crc = crc16(crc, (uint8_t *)gd, off);
723 /* XXX ondisk32 */
724
725 return h2fs16(crc);
726}
727
728static void
729ext2fs_init_bb(struct m_ext2fs *fs, int cg, struct ext2_gd *gd, char *bbp)
730{
731 int i;
732
733 memset(bbp, 0, fs->e2fs_bsize);
734
735 /*
736 * No block was ever allocated on this cg before, so the only used
737 * blocks are metadata blocks on start of the group. We could optimize
738 * this to set by bytes, but since this is done once per the group
739 * in lifetime of filesystem, it really is not worth it.
740 */
741 for(i=0; i < fs->e2fs.e2fs_bpg - fs2h16(gd->ext2bgd_nbfree); i++)
742 setbit(bbp, i);
743}
744
745/*
746 * Verify csum and initialize itable if not done already
747 */
748int
749ext2fs_cg_verify_and_initialize(struct vnode *devvp, struct m_ext2fs *fs, int ronly)
750{
751 /* XXX disk32 */
752 struct ext2_gd *gd;
753 ino_t ioff;
754 size_t boff;
755 struct buf *bp;
756 int cg, i, error;
757
758 if (!E2FS_HAS_GD_CSUM(fs))
759 return 0;
760
761 for(cg=0; cg < fs->e2fs_ncg; cg++) {
762 gd = &fs->e2fs_gd[cg];
763
764 /* Verify checksum */
765 if (gd->ext2bgd_checksum != ext2fs_cg_get_csum(fs, cg, gd)) {
766 printf("ext2fs_cg_verify_and_initialize: group %d invalid csum\n", cg);
767 return EINVAL;
768 }
769
770 /* if mounting read-write, zero itable if not already done */
771 if (ronly || (gd->ext2bgd_flags & h2fs16(E2FS_BG_INODE_ZEROED)) != 0)
772 continue;
773
774 /*
775 * We are skipping already used inodes, zero rest of itable
776 * blocks. First block to zero could be only partial wipe, all
777 * others are wiped completely. This might take a while,
778 * there could be many inode table blocks. We use
779 * delayed writes, so this shouldn't block for very
780 * long.
781 */
782 ioff = fs->e2fs.e2fs_ipg - fs2h16(gd->ext2bgd_itable_unused_lo);
783 boff = (ioff % fs->e2fs_ipb) * EXT2_DINODE_SIZE(fs);
784
785 for(i = ioff / fs->e2fs_ipb; i < fs->e2fs_itpg; i++) {
786 if (boff) {
787 /* partial wipe, must read old data */
788 error = bread(devvp,
789 EXT2_FSBTODB(fs, fs2h32(gd->ext2bgd_i_tables) + i),
790 (int)fs->e2fs_bsize, B_MODIFY, &bp);
791 if (error) {
792 printf("ext2fs_cg_verify_and_initialize: can't read itable block");
793 return error;
794 }
795 memset((char *)bp->b_data + boff, 0, fs->e2fs_bsize - boff);
796 boff = 0;
797 } else {
798 /*
799 * Complete wipe, don't need to read data. This
800 * assumes nothing else is changing the data.
801 */
802 bp = getblk(devvp,
803 EXT2_FSBTODB(fs, fs2h32(gd->ext2bgd_i_tables) + i),
804 (int)fs->e2fs_bsize, 0, 0);
805 clrbuf(bp);
806 }
807
808 bdwrite(bp);
809 }
810
811 gd->ext2bgd_flags |= h2fs16(E2FS_BG_INODE_ZEROED);
812 gd->ext2bgd_checksum = ext2fs_cg_get_csum(fs, cg, gd);
813 fs->e2fs_fmod = 1;
814 }
815
816 return 0;
817}
818