lfs_alloc.c revision 1.97 1 1.97 perseant /* $NetBSD: lfs_alloc.c,v 1.97 2006/09/01 19:41:28 perseant Exp $ */
2 1.2 cgd
3 1.17 perseant /*-
4 1.63 perseant * Copyright (c) 1999, 2000, 2001, 2002, 2003 The NetBSD Foundation, Inc.
5 1.17 perseant * All rights reserved.
6 1.17 perseant *
7 1.17 perseant * This code is derived from software contributed to The NetBSD Foundation
8 1.17 perseant * by Konrad E. Schroder <perseant (at) hhhh.org>.
9 1.17 perseant *
10 1.17 perseant * Redistribution and use in source and binary forms, with or without
11 1.17 perseant * modification, are permitted provided that the following conditions
12 1.17 perseant * are met:
13 1.17 perseant * 1. Redistributions of source code must retain the above copyright
14 1.17 perseant * notice, this list of conditions and the following disclaimer.
15 1.17 perseant * 2. Redistributions in binary form must reproduce the above copyright
16 1.17 perseant * notice, this list of conditions and the following disclaimer in the
17 1.17 perseant * documentation and/or other materials provided with the distribution.
18 1.17 perseant * 3. All advertising materials mentioning features or use of this software
19 1.17 perseant * must display the following acknowledgement:
20 1.64 perseant * This product includes software developed by the NetBSD
21 1.64 perseant * Foundation, Inc. and its contributors.
22 1.17 perseant * 4. Neither the name of The NetBSD Foundation nor the names of its
23 1.17 perseant * contributors may be used to endorse or promote products derived
24 1.17 perseant * from this software without specific prior written permission.
25 1.17 perseant *
26 1.17 perseant * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
27 1.17 perseant * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
28 1.17 perseant * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 1.17 perseant * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
30 1.17 perseant * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
31 1.17 perseant * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
32 1.17 perseant * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
33 1.17 perseant * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
34 1.17 perseant * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
35 1.17 perseant * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36 1.17 perseant * POSSIBILITY OF SUCH DAMAGE.
37 1.17 perseant */
38 1.1 mycroft /*
39 1.1 mycroft * Copyright (c) 1991, 1993
40 1.1 mycroft * The Regents of the University of California. All rights reserved.
41 1.1 mycroft *
42 1.1 mycroft * Redistribution and use in source and binary forms, with or without
43 1.1 mycroft * modification, are permitted provided that the following conditions
44 1.1 mycroft * are met:
45 1.1 mycroft * 1. Redistributions of source code must retain the above copyright
46 1.1 mycroft * notice, this list of conditions and the following disclaimer.
47 1.1 mycroft * 2. Redistributions in binary form must reproduce the above copyright
48 1.1 mycroft * notice, this list of conditions and the following disclaimer in the
49 1.1 mycroft * documentation and/or other materials provided with the distribution.
50 1.71 agc * 3. Neither the name of the University nor the names of its contributors
51 1.1 mycroft * may be used to endorse or promote products derived from this software
52 1.1 mycroft * without specific prior written permission.
53 1.1 mycroft *
54 1.1 mycroft * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
55 1.1 mycroft * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
56 1.1 mycroft * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
57 1.1 mycroft * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
58 1.1 mycroft * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
59 1.1 mycroft * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
60 1.1 mycroft * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
61 1.1 mycroft * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
62 1.1 mycroft * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
63 1.1 mycroft * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
64 1.1 mycroft * SUCH DAMAGE.
65 1.1 mycroft *
66 1.2 cgd * @(#)lfs_alloc.c 8.4 (Berkeley) 1/4/94
67 1.1 mycroft */
68 1.52 lukem
69 1.52 lukem #include <sys/cdefs.h>
70 1.97 perseant __KERNEL_RCSID(0, "$NetBSD: lfs_alloc.c,v 1.97 2006/09/01 19:41:28 perseant Exp $");
71 1.12 scottr
72 1.47 mrg #if defined(_KERNEL_OPT)
73 1.12 scottr #include "opt_quota.h"
74 1.13 scottr #endif
75 1.1 mycroft
76 1.1 mycroft #include <sys/param.h>
77 1.3 christos #include <sys/systm.h>
78 1.1 mycroft #include <sys/kernel.h>
79 1.1 mycroft #include <sys/buf.h>
80 1.56 perseant #include <sys/lock.h>
81 1.1 mycroft #include <sys/vnode.h>
82 1.1 mycroft #include <sys/syslog.h>
83 1.1 mycroft #include <sys/mount.h>
84 1.87 perseant #include <sys/malloc.h>
85 1.15 thorpej #include <sys/pool.h>
86 1.50 chs #include <sys/proc.h>
87 1.81 perseant #include <sys/tree.h>
88 1.94 elad #include <sys/kauth.h>
89 1.1 mycroft
90 1.1 mycroft #include <ufs/ufs/quota.h>
91 1.1 mycroft #include <ufs/ufs/inode.h>
92 1.1 mycroft #include <ufs/ufs/ufsmount.h>
93 1.3 christos #include <ufs/ufs/ufs_extern.h>
94 1.1 mycroft
95 1.1 mycroft #include <ufs/lfs/lfs.h>
96 1.1 mycroft #include <ufs/lfs/lfs_extern.h>
97 1.1 mycroft
98 1.17 perseant extern struct lock ufs_hashlock;
99 1.17 perseant
100 1.87 perseant /* Constants for inode free bitmap */
101 1.88 perseant #define BMSHIFT 5 /* 2 ** 5 = 32 */
102 1.88 perseant #define BMMASK ((1 << BMSHIFT) - 1)
103 1.88 perseant #define SET_BITMAP_FREE(F, I) do { \
104 1.88 perseant DLOG((DLOG_ALLOC, "lfs: ino %d wrd %d bit %d set\n", (int)(I), \
105 1.88 perseant (int)((I) >> BMSHIFT), (int)((I) & BMMASK))); \
106 1.88 perseant (F)->lfs_ino_bitmap[(I) >> BMSHIFT] |= (1 << ((I) & BMMASK)); \
107 1.88 perseant } while (0)
108 1.88 perseant #define CLR_BITMAP_FREE(F, I) do { \
109 1.88 perseant DLOG((DLOG_ALLOC, "lfs: ino %d wrd %d bit %d clr\n", (int)(I), \
110 1.88 perseant (int)((I) >> BMSHIFT), (int)((I) & BMMASK))); \
111 1.88 perseant (F)->lfs_ino_bitmap[(I) >> BMSHIFT] &= ~(1 << ((I) & BMMASK)); \
112 1.88 perseant } while(0)
113 1.88 perseant
114 1.87 perseant #define ISSET_BITMAP_FREE(F, I) \
115 1.88 perseant ((F)->lfs_ino_bitmap[(I) >> BMSHIFT] & (1 << ((I) & BMMASK)))
116 1.87 perseant
117 1.44 perseant /*
118 1.65 perseant * Add a new block to the Ifile, to accommodate future file creations.
119 1.65 perseant * Called with the segment lock held.
120 1.56 perseant */
121 1.96 perseant int
122 1.96 perseant lfs_extend_ifile(struct lfs *fs, kauth_cred_t cred)
123 1.44 perseant {
124 1.44 perseant struct vnode *vp;
125 1.44 perseant struct inode *ip;
126 1.44 perseant IFILE *ifp;
127 1.48 perseant IFILE_V1 *ifp_v1;
128 1.48 perseant struct buf *bp, *cbp;
129 1.44 perseant int error;
130 1.83 christos daddr_t i, blkno, xmax;
131 1.87 perseant ino_t oldlast, maxino;
132 1.48 perseant CLEANERINFO *cip;
133 1.44 perseant
134 1.78 perseant ASSERT_SEGLOCK(fs);
135 1.78 perseant
136 1.44 perseant vp = fs->lfs_ivnode;
137 1.44 perseant ip = VTOI(vp);
138 1.66 fvdl blkno = lblkno(fs, ip->i_size);
139 1.85 yamt if ((error = lfs_balloc(vp, ip->i_size, fs->lfs_bsize, cred, 0,
140 1.44 perseant &bp)) != 0) {
141 1.44 perseant return (error);
142 1.44 perseant }
143 1.66 fvdl ip->i_size += fs->lfs_bsize;
144 1.66 fvdl ip->i_ffs1_size = ip->i_size;
145 1.66 fvdl uvm_vnp_setsize(vp, ip->i_size);
146 1.75 perry
147 1.88 perseant maxino = ((ip->i_size >> fs->lfs_bshift) - fs->lfs_cleansz -
148 1.88 perseant fs->lfs_segtabsz) * fs->lfs_ifpb;
149 1.88 perseant fs->lfs_ino_bitmap = (lfs_bm_t *)
150 1.88 perseant realloc(fs->lfs_ino_bitmap, ((maxino + BMMASK) >> BMSHIFT) *
151 1.88 perseant sizeof(lfs_bm_t), M_SEGMENT, M_WAITOK);
152 1.88 perseant KASSERT(fs->lfs_ino_bitmap != NULL);
153 1.87 perseant
154 1.44 perseant i = (blkno - fs->lfs_segtabsz - fs->lfs_cleansz) *
155 1.44 perseant fs->lfs_ifpb;
156 1.87 perseant
157 1.87 perseant /*
158 1.87 perseant * We insert the new inodes at the head of the free list.
159 1.87 perseant * Under normal circumstances, the free list is empty here,
160 1.87 perseant * so we are also incidentally placing them at the end (which
161 1.87 perseant * we must do if we are to keep them in order).
162 1.87 perseant */
163 1.48 perseant LFS_GET_HEADFREE(fs, cip, cbp, &oldlast);
164 1.48 perseant LFS_PUT_HEADFREE(fs, cip, cbp, i);
165 1.44 perseant #ifdef DIAGNOSTIC
166 1.63 perseant if (fs->lfs_freehd == LFS_UNUSED_INUM)
167 1.44 perseant panic("inode 0 allocated [2]");
168 1.44 perseant #endif /* DIAGNOSTIC */
169 1.83 christos xmax = i + fs->lfs_ifpb;
170 1.48 perseant
171 1.53 chs if (fs->lfs_version == 1) {
172 1.83 christos for (ifp_v1 = (IFILE_V1 *)bp->b_data; i < xmax; ++ifp_v1) {
173 1.89 perseant SET_BITMAP_FREE(fs, i);
174 1.48 perseant ifp_v1->if_version = 1;
175 1.48 perseant ifp_v1->if_daddr = LFS_UNUSED_DADDR;
176 1.48 perseant ifp_v1->if_nextfree = ++i;
177 1.48 perseant }
178 1.48 perseant ifp_v1--;
179 1.48 perseant ifp_v1->if_nextfree = oldlast;
180 1.48 perseant } else {
181 1.83 christos for (ifp = (IFILE *)bp->b_data; i < xmax; ++ifp) {
182 1.89 perseant SET_BITMAP_FREE(fs, i);
183 1.48 perseant ifp->if_version = 1;
184 1.48 perseant ifp->if_daddr = LFS_UNUSED_DADDR;
185 1.48 perseant ifp->if_nextfree = ++i;
186 1.48 perseant }
187 1.48 perseant ifp--;
188 1.48 perseant ifp->if_nextfree = oldlast;
189 1.44 perseant }
190 1.83 christos LFS_PUT_TAILFREE(fs, cip, cbp, xmax - 1);
191 1.48 perseant
192 1.56 perseant (void) LFS_BWRITE_LOG(bp); /* Ifile */
193 1.44 perseant
194 1.44 perseant return 0;
195 1.44 perseant }
196 1.44 perseant
197 1.1 mycroft /* Allocate a new inode. */
198 1.1 mycroft /* ARGSUSED */
199 1.43 perseant /* VOP_BWRITE 2i times */
200 1.1 mycroft int
201 1.94 elad lfs_valloc(struct vnode *pvp, int mode, kauth_cred_t cred, struct vnode **vpp)
202 1.3 christos {
203 1.1 mycroft struct lfs *fs;
204 1.48 perseant struct buf *bp, *cbp;
205 1.1 mycroft struct ifile *ifp;
206 1.1 mycroft ino_t new_ino;
207 1.1 mycroft int error;
208 1.36 perseant int new_gen;
209 1.48 perseant CLEANERINFO *cip;
210 1.1 mycroft
211 1.85 yamt fs = VTOI(pvp)->i_lfs;
212 1.38 perseant if (fs->lfs_ronly)
213 1.38 perseant return EROFS;
214 1.75 perry
215 1.78 perseant ASSERT_NO_SEGLOCK(fs);
216 1.78 perseant
217 1.56 perseant lfs_seglock(fs, SEGM_PROT);
218 1.78 perseant vn_lock(fs->lfs_ivnode, LK_EXCLUSIVE);
219 1.17 perseant
220 1.1 mycroft /* Get the head of the freelist. */
221 1.48 perseant LFS_GET_HEADFREE(fs, cip, cbp, &new_ino);
222 1.87 perseant KASSERT(new_ino != LFS_UNUSED_INUM && new_ino != LFS_IFILE_INUM);
223 1.48 perseant
224 1.87 perseant DLOG((DLOG_ALLOC, "lfs_valloc: allocate inode %lld\n",
225 1.87 perseant (long long)new_ino));
226 1.75 perry
227 1.1 mycroft /*
228 1.1 mycroft * Remove the inode from the free list and write the new start
229 1.1 mycroft * of the free list into the superblock.
230 1.1 mycroft */
231 1.87 perseant CLR_BITMAP_FREE(fs, new_ino);
232 1.1 mycroft LFS_IENTRY(ifp, fs, new_ino, bp);
233 1.1 mycroft if (ifp->if_daddr != LFS_UNUSED_DADDR)
234 1.84 christos panic("lfs_valloc: inuse inode %llu on the free list",
235 1.84 christos (unsigned long long)new_ino);
236 1.48 perseant LFS_PUT_HEADFREE(fs, cip, cbp, ifp->if_nextfree);
237 1.87 perseant DLOG((DLOG_ALLOC, "lfs_valloc: headfree %lld -> %lld\n",
238 1.87 perseant (long long)new_ino, (long long)ifp->if_nextfree));
239 1.48 perseant
240 1.37 perseant new_gen = ifp->if_version; /* version was updated by vfree */
241 1.28 perseant brelse(bp);
242 1.30 perseant
243 1.1 mycroft /* Extend IFILE so that the next lfs_valloc will succeed. */
244 1.63 perseant if (fs->lfs_freehd == LFS_UNUSED_INUM) {
245 1.96 perseant if ((error = lfs_extend_ifile(fs, cred)) != 0) {
246 1.48 perseant LFS_PUT_HEADFREE(fs, cip, cbp, new_ino);
247 1.78 perseant VOP_UNLOCK(fs->lfs_ivnode, 0);
248 1.56 perseant lfs_segunlock(fs);
249 1.44 perseant return error;
250 1.1 mycroft }
251 1.1 mycroft }
252 1.17 perseant #ifdef DIAGNOSTIC
253 1.63 perseant if (fs->lfs_freehd == LFS_UNUSED_INUM)
254 1.17 perseant panic("inode 0 allocated [3]");
255 1.17 perseant #endif /* DIAGNOSTIC */
256 1.48 perseant
257 1.78 perseant /* Set superblock modified bit and increment file count. */
258 1.78 perseant simple_lock(&fs->lfs_interlock);
259 1.78 perseant fs->lfs_fmod = 1;
260 1.78 perseant simple_unlock(&fs->lfs_interlock);
261 1.78 perseant ++fs->lfs_nfiles;
262 1.78 perseant
263 1.78 perseant VOP_UNLOCK(fs->lfs_ivnode, 0);
264 1.56 perseant lfs_segunlock(fs);
265 1.63 perseant
266 1.85 yamt return lfs_ialloc(fs, pvp, new_ino, new_gen, vpp);
267 1.44 perseant }
268 1.44 perseant
269 1.65 perseant /*
270 1.65 perseant * Finish allocating a new inode, given an inode and generation number.
271 1.65 perseant */
272 1.96 perseant int
273 1.44 perseant lfs_ialloc(struct lfs *fs, struct vnode *pvp, ino_t new_ino, int new_gen,
274 1.44 perseant struct vnode **vpp)
275 1.44 perseant {
276 1.44 perseant struct inode *ip;
277 1.44 perseant struct vnode *vp;
278 1.40 fvdl
279 1.78 perseant ASSERT_NO_SEGLOCK(fs);
280 1.78 perseant
281 1.77 perseant vp = *vpp;
282 1.31 perseant lockmgr(&ufs_hashlock, LK_EXCLUSIVE, 0);
283 1.40 fvdl /* Create an inode to associate with the vnode. */
284 1.44 perseant lfs_vcreate(pvp->v_mount, new_ino, vp);
285 1.51 chs
286 1.1 mycroft ip = VTOI(vp);
287 1.73 mycroft LFS_SET_UINO(ip, IN_CHANGE);
288 1.66 fvdl /* on-disk structure has been zeroed out by lfs_vcreate */
289 1.66 fvdl ip->i_din.ffs1_din->di_inumber = new_ino;
290 1.51 chs
291 1.79 perseant /* Note no blocks yet */
292 1.79 perseant ip->i_lfs_hiblk = -1;
293 1.79 perseant
294 1.1 mycroft /* Set a new generation number for this inode. */
295 1.66 fvdl if (new_gen) {
296 1.66 fvdl ip->i_gen = new_gen;
297 1.66 fvdl ip->i_ffs1_gen = new_gen;
298 1.66 fvdl }
299 1.51 chs
300 1.1 mycroft /* Insert into the inode hash table. */
301 1.1 mycroft ufs_ihashins(ip);
302 1.26 perseant lockmgr(&ufs_hashlock, LK_RELEASE, 0);
303 1.44 perseant
304 1.77 perseant ufs_vinit(vp->v_mount, lfs_specop_p, lfs_fifoop_p, vpp);
305 1.77 perseant vp = *vpp;
306 1.44 perseant ip = VTOI(vp);
307 1.57 yamt
308 1.57 yamt memset(ip->i_lfs_fragsize, 0, NDADDR * sizeof(*ip->i_lfs_fragsize));
309 1.51 chs
310 1.51 chs uvm_vnp_setsize(vp, 0);
311 1.72 yamt lfs_mark_vnode(vp);
312 1.54 chs genfs_node_init(vp, &lfs_genfsops);
313 1.38 perseant VREF(ip->i_devvp);
314 1.1 mycroft return (0);
315 1.1 mycroft }
316 1.1 mycroft
317 1.1 mycroft /* Create a new vnode/inode pair and initialize what fields we can. */
318 1.40 fvdl void
319 1.48 perseant lfs_vcreate(struct mount *mp, ino_t ino, struct vnode *vp)
320 1.1 mycroft {
321 1.1 mycroft struct inode *ip;
322 1.66 fvdl struct ufs1_dinode *dp;
323 1.1 mycroft struct ufsmount *ump;
324 1.80 perseant #ifdef QUOTA
325 1.4 pk int i;
326 1.80 perseant #endif
327 1.75 perry
328 1.1 mycroft /* Get a pointer to the private mount structure. */
329 1.1 mycroft ump = VFSTOUFS(mp);
330 1.75 perry
331 1.78 perseant ASSERT_NO_SEGLOCK(ump->um_lfs);
332 1.78 perseant
333 1.1 mycroft /* Initialize the inode. */
334 1.15 thorpej ip = pool_get(&lfs_inode_pool, PR_WAITOK);
335 1.66 fvdl memset(ip, 0, sizeof(*ip));
336 1.66 fvdl dp = pool_get(&lfs_dinode_pool, PR_WAITOK);
337 1.66 fvdl memset(dp, 0, sizeof(*dp));
338 1.63 perseant ip->inode_ext.lfs = pool_get(&lfs_inoext_pool, PR_WAITOK);
339 1.74 perseant memset(ip->inode_ext.lfs, 0, sizeof(*ip->inode_ext.lfs));
340 1.40 fvdl vp->v_data = ip;
341 1.66 fvdl ip->i_din.ffs1_din = dp;
342 1.66 fvdl ip->i_ump = ump;
343 1.40 fvdl ip->i_vnode = vp;
344 1.1 mycroft ip->i_devvp = ump->um_devvp;
345 1.1 mycroft ip->i_dev = ump->um_dev;
346 1.66 fvdl ip->i_number = dp->di_inumber = ino;
347 1.1 mycroft ip->i_lfs = ump->um_lfs;
348 1.66 fvdl ip->i_lfs_effnblks = 0;
349 1.81 perseant SPLAY_INIT(&ip->i_lfs_lbtree);
350 1.82 perseant ip->i_lfs_nbtree = 0;
351 1.91 perseant LIST_INIT(&ip->i_lfs_segdhd);
352 1.1 mycroft #ifdef QUOTA
353 1.1 mycroft for (i = 0; i < MAXQUOTAS; i++)
354 1.1 mycroft ip->i_dquot[i] = NODQUOT;
355 1.1 mycroft #endif
356 1.76 perseant #ifdef DEBUG
357 1.56 perseant if (ino == LFS_IFILE_INUM)
358 1.56 perseant vp->v_vnlock->lk_wmesg = "inlock";
359 1.56 perseant #endif
360 1.1 mycroft }
361 1.1 mycroft
362 1.87 perseant #if 0
363 1.87 perseant /*
364 1.87 perseant * Find the highest-numbered allocated inode.
365 1.87 perseant * This will be used to shrink the Ifile.
366 1.87 perseant */
367 1.87 perseant static inline ino_t
368 1.87 perseant lfs_last_alloc_ino(struct lfs *fs)
369 1.87 perseant {
370 1.87 perseant ino_t ino, maxino;
371 1.87 perseant
372 1.87 perseant maxino = ((fs->lfs_ivnode->v_size >> fs->lfs_bshift) -
373 1.87 perseant fs->lfs_cleansz - fs->lfs_segtabsz) * fs->lfs_ifpb;
374 1.87 perseant for (ino = maxino - 1; ino > LFS_UNUSED_INUM; --ino) {
375 1.87 perseant if (ISSET_BITMAP_FREE(fs, ino) == 0)
376 1.87 perseant break;
377 1.87 perseant }
378 1.87 perseant return ino;
379 1.87 perseant }
380 1.87 perseant #endif
381 1.87 perseant
382 1.87 perseant /*
383 1.87 perseant * Find the previous (next lowest numbered) free inode, if any.
384 1.87 perseant * If there is none, return LFS_UNUSED_INUM.
385 1.87 perseant */
386 1.87 perseant static inline ino_t
387 1.87 perseant lfs_freelist_prev(struct lfs *fs, ino_t ino)
388 1.87 perseant {
389 1.88 perseant ino_t tino, bound, bb, freehdbb;
390 1.88 perseant
391 1.88 perseant if (fs->lfs_freehd == LFS_UNUSED_INUM) /* No free inodes at all */
392 1.88 perseant return LFS_UNUSED_INUM;
393 1.88 perseant
394 1.88 perseant /* Search our own word first */
395 1.88 perseant bound = ino & ~BMMASK;
396 1.89 perseant for (tino = ino - 1; tino >= bound && tino > LFS_UNUSED_INUM; tino--)
397 1.88 perseant if (ISSET_BITMAP_FREE(fs, tino))
398 1.88 perseant return tino;
399 1.88 perseant /* If there are no lower words to search, just return */
400 1.88 perseant if (ino >> BMSHIFT == 0)
401 1.88 perseant return LFS_UNUSED_INUM;
402 1.88 perseant
403 1.88 perseant /*
404 1.88 perseant * Find a word with a free inode in it. We have to be a bit
405 1.88 perseant * careful here since ino_t is unsigned.
406 1.88 perseant */
407 1.88 perseant freehdbb = (fs->lfs_freehd >> BMSHIFT);
408 1.88 perseant for (bb = (ino >> BMSHIFT) - 1; bb >= freehdbb && bb > 0; --bb)
409 1.88 perseant if (fs->lfs_ino_bitmap[bb])
410 1.88 perseant break;
411 1.88 perseant if (fs->lfs_ino_bitmap[bb] == 0)
412 1.88 perseant return LFS_UNUSED_INUM;
413 1.88 perseant
414 1.88 perseant /* Search the word we found */
415 1.89 perseant for (tino = (bb << BMSHIFT) | BMMASK; tino >= (bb << BMSHIFT) &&
416 1.89 perseant tino > LFS_UNUSED_INUM; tino--)
417 1.88 perseant if (ISSET_BITMAP_FREE(fs, tino))
418 1.88 perseant break;
419 1.87 perseant
420 1.87 perseant if (tino <= LFS_IFILE_INUM)
421 1.87 perseant tino = LFS_UNUSED_INUM;
422 1.87 perseant
423 1.87 perseant return tino;
424 1.87 perseant }
425 1.87 perseant
426 1.1 mycroft /* Free an inode. */
427 1.1 mycroft /* ARGUSED */
428 1.43 perseant /* VOP_BWRITE 2i times */
429 1.1 mycroft int
430 1.85 yamt lfs_vfree(struct vnode *vp, ino_t ino, int mode)
431 1.3 christos {
432 1.1 mycroft SEGUSE *sup;
433 1.48 perseant CLEANERINFO *cip;
434 1.48 perseant struct buf *cbp, *bp;
435 1.1 mycroft struct ifile *ifp;
436 1.1 mycroft struct inode *ip;
437 1.1 mycroft struct lfs *fs;
438 1.59 fvdl daddr_t old_iaddr;
439 1.85 yamt ino_t otail;
440 1.56 perseant int s;
441 1.75 perry
442 1.1 mycroft /* Get the inode number and file system. */
443 1.30 perseant ip = VTOI(vp);
444 1.1 mycroft fs = ip->i_lfs;
445 1.1 mycroft ino = ip->i_number;
446 1.34 perseant
447 1.78 perseant ASSERT_NO_SEGLOCK(fs);
448 1.88 perseant DLOG((DLOG_ALLOC, "lfs_vfree: free ino %lld\n", (long long)ino));
449 1.78 perseant
450 1.48 perseant /* Drain of pending writes */
451 1.78 perseant simple_lock(&vp->v_interlock);
452 1.56 perseant s = splbio();
453 1.48 perseant if (fs->lfs_version > 1 && WRITEINPROG(vp))
454 1.78 perseant ltsleep(vp, (PRIBIO+1), "lfs_vfree", 0, &vp->v_interlock);
455 1.56 perseant splx(s);
456 1.78 perseant simple_unlock(&vp->v_interlock);
457 1.48 perseant
458 1.63 perseant lfs_seglock(fs, SEGM_PROT);
459 1.78 perseant vn_lock(fs->lfs_ivnode, LK_EXCLUSIVE);
460 1.75 perry
461 1.72 yamt lfs_unmark_vnode(vp);
462 1.53 chs if (vp->v_flag & VDIROP) {
463 1.78 perseant vp->v_flag &= ~VDIROP;
464 1.78 perseant simple_lock(&fs->lfs_interlock);
465 1.78 perseant simple_lock(&lfs_subsys_lock);
466 1.30 perseant --lfs_dirvcount;
467 1.78 perseant simple_unlock(&lfs_subsys_lock);
468 1.92 perseant --fs->lfs_dirvcount;
469 1.63 perseant TAILQ_REMOVE(&fs->lfs_dchainhd, ip, i_lfs_dchain);
470 1.78 perseant simple_unlock(&fs->lfs_interlock);
471 1.92 perseant wakeup(&fs->lfs_dirvcount);
472 1.30 perseant wakeup(&lfs_dirvcount);
473 1.30 perseant lfs_vunref(vp);
474 1.90 perseant
475 1.90 perseant /*
476 1.90 perseant * If this inode is not going to be written any more, any
477 1.90 perseant * segment accounting left over from its truncation needs
478 1.90 perseant * to occur at the end of the next dirops flush. Attach
479 1.90 perseant * them to the fs-wide list for that purpose.
480 1.90 perseant */
481 1.90 perseant if (LIST_FIRST(&ip->i_lfs_segdhd) != NULL) {
482 1.90 perseant struct segdelta *sd;
483 1.90 perseant
484 1.90 perseant while((sd = LIST_FIRST(&ip->i_lfs_segdhd)) != NULL) {
485 1.90 perseant LIST_REMOVE(sd, list);
486 1.90 perseant LIST_INSERT_HEAD(&fs->lfs_segdhd, sd, list);
487 1.90 perseant }
488 1.90 perseant }
489 1.90 perseant } else {
490 1.90 perseant /*
491 1.90 perseant * If it's not a dirop, we can finalize right away.
492 1.90 perseant */
493 1.90 perseant lfs_finalize_ino_seguse(fs, ip);
494 1.38 perseant }
495 1.30 perseant
496 1.42 perseant LFS_CLR_UINO(ip, IN_ACCESSED|IN_CLEANING|IN_MODIFIED);
497 1.33 perseant ip->i_flag &= ~IN_ALLMOD;
498 1.93 perseant ip->i_lfs_iflags |= LFSI_DELETED;
499 1.93 perseant
500 1.1 mycroft /*
501 1.1 mycroft * Set the ifile's inode entry to unused, increment its version number
502 1.48 perseant * and link it onto the free chain.
503 1.1 mycroft */
504 1.87 perseant SET_BITMAP_FREE(fs, ino);
505 1.1 mycroft LFS_IENTRY(ifp, fs, ino, bp);
506 1.1 mycroft old_iaddr = ifp->if_daddr;
507 1.1 mycroft ifp->if_daddr = LFS_UNUSED_DADDR;
508 1.1 mycroft ++ifp->if_version;
509 1.48 perseant if (fs->lfs_version == 1) {
510 1.48 perseant LFS_GET_HEADFREE(fs, cip, cbp, &(ifp->if_nextfree));
511 1.48 perseant LFS_PUT_HEADFREE(fs, cip, cbp, ino);
512 1.56 perseant (void) LFS_BWRITE_LOG(bp); /* Ifile */
513 1.48 perseant } else {
514 1.87 perseant ino_t tino, onf;
515 1.87 perseant
516 1.48 perseant ifp->if_nextfree = LFS_UNUSED_INUM;
517 1.56 perseant (void) LFS_BWRITE_LOG(bp); /* Ifile */
518 1.87 perseant
519 1.87 perseant tino = lfs_freelist_prev(fs, ino);
520 1.87 perseant if (tino == LFS_UNUSED_INUM) {
521 1.87 perseant /* Nothing free below us, put us on the head */
522 1.87 perseant LFS_IENTRY(ifp, fs, ino, bp);
523 1.87 perseant LFS_GET_HEADFREE(fs, cip, cbp, &(ifp->if_nextfree));
524 1.87 perseant LFS_PUT_HEADFREE(fs, cip, cbp, ino);
525 1.88 perseant DLOG((DLOG_ALLOC, "lfs_vfree: headfree %lld -> %lld\n",
526 1.87 perseant (long long)ifp->if_nextfree, (long long)ino));
527 1.87 perseant LFS_BWRITE_LOG(bp); /* Ifile */
528 1.87 perseant
529 1.87 perseant /* If the list was empty, set tail too */
530 1.87 perseant LFS_GET_TAILFREE(fs, cip, cbp, &otail);
531 1.87 perseant if (otail == LFS_UNUSED_INUM) {
532 1.87 perseant LFS_PUT_TAILFREE(fs, cip, cbp, ino);
533 1.87 perseant DLOG((DLOG_ALLOC, "lfs_vfree: tailfree %lld "
534 1.87 perseant "-> %lld\n", (long long)otail,
535 1.87 perseant (long long)ino));
536 1.87 perseant }
537 1.87 perseant } else {
538 1.87 perseant /*
539 1.87 perseant * Insert this inode into the list after tino.
540 1.87 perseant * We hold the segment lock so we don't have to
541 1.87 perseant * worry about blocks being written out of order.
542 1.87 perseant */
543 1.87 perseant DLOG((DLOG_ALLOC, "lfs_vfree: insert ino %lld "
544 1.87 perseant " after %lld\n", ino, tino));
545 1.87 perseant
546 1.87 perseant LFS_IENTRY(ifp, fs, tino, bp);
547 1.87 perseant onf = ifp->if_nextfree;
548 1.87 perseant ifp->if_nextfree = ino;
549 1.87 perseant LFS_BWRITE_LOG(bp); /* Ifile */
550 1.87 perseant
551 1.87 perseant LFS_IENTRY(ifp, fs, ino, bp);
552 1.87 perseant ifp->if_nextfree = onf;
553 1.87 perseant LFS_BWRITE_LOG(bp); /* Ifile */
554 1.87 perseant
555 1.87 perseant /* If we're last, put us on the tail */
556 1.87 perseant if (onf == LFS_UNUSED_INUM) {
557 1.87 perseant LFS_GET_TAILFREE(fs, cip, cbp, &otail);
558 1.87 perseant LFS_PUT_TAILFREE(fs, cip, cbp, ino);
559 1.87 perseant DLOG((DLOG_ALLOC, "lfs_vfree: tailfree %lld "
560 1.87 perseant "-> %lld\n", (long long)otail,
561 1.87 perseant (long long)ino));
562 1.87 perseant }
563 1.87 perseant }
564 1.48 perseant }
565 1.17 perseant #ifdef DIAGNOSTIC
566 1.53 chs if (ino == LFS_UNUSED_INUM) {
567 1.17 perseant panic("inode 0 freed");
568 1.17 perseant }
569 1.17 perseant #endif /* DIAGNOSTIC */
570 1.1 mycroft if (old_iaddr != LFS_UNUSED_DADDR) {
571 1.48 perseant LFS_SEGENTRY(sup, fs, dtosn(fs, old_iaddr), bp);
572 1.22 perseant #ifdef DIAGNOSTIC
573 1.66 fvdl if (sup->su_nbytes < sizeof (struct ufs1_dinode)) {
574 1.43 perseant printf("lfs_vfree: negative byte count"
575 1.62 yamt " (segment %" PRIu32 " short by %d)\n",
576 1.48 perseant dtosn(fs, old_iaddr),
577 1.66 fvdl (int)sizeof (struct ufs1_dinode) -
578 1.66 fvdl sup->su_nbytes);
579 1.22 perseant panic("lfs_vfree: negative byte count");
580 1.66 fvdl sup->su_nbytes = sizeof (struct ufs1_dinode);
581 1.17 perseant }
582 1.22 perseant #endif
583 1.66 fvdl sup->su_nbytes -= sizeof (struct ufs1_dinode);
584 1.63 perseant LFS_WRITESEGENTRY(sup, fs, dtosn(fs, old_iaddr), bp); /* Ifile */
585 1.1 mycroft }
586 1.75 perry
587 1.1 mycroft /* Set superblock modified bit and decrement file count. */
588 1.78 perseant simple_lock(&fs->lfs_interlock);
589 1.1 mycroft fs->lfs_fmod = 1;
590 1.78 perseant simple_unlock(&fs->lfs_interlock);
591 1.1 mycroft --fs->lfs_nfiles;
592 1.75 perry
593 1.78 perseant VOP_UNLOCK(fs->lfs_ivnode, 0);
594 1.56 perseant lfs_segunlock(fs);
595 1.63 perseant
596 1.1 mycroft return (0);
597 1.1 mycroft }
598 1.87 perseant
599 1.87 perseant /*
600 1.87 perseant * Sort the freelist and set up the free-inode bitmap.
601 1.87 perseant * To be called by lfs_mountfs().
602 1.87 perseant */
603 1.87 perseant void
604 1.87 perseant lfs_order_freelist(struct lfs *fs)
605 1.87 perseant {
606 1.87 perseant CLEANERINFO *cip;
607 1.87 perseant IFILE *ifp = NULL;
608 1.87 perseant struct buf *bp;
609 1.87 perseant ino_t ino, firstino, lastino, maxino;
610 1.97 perseant #ifdef notyet
611 1.97 perseant struct vnode *vp;
612 1.97 perseant #endif
613 1.87 perseant
614 1.95 perseant ASSERT_NO_SEGLOCK(fs);
615 1.95 perseant lfs_seglock(fs, SEGM_PROT);
616 1.95 perseant
617 1.87 perseant maxino = ((fs->lfs_ivnode->v_size >> fs->lfs_bshift) -
618 1.87 perseant fs->lfs_cleansz - fs->lfs_segtabsz) * fs->lfs_ifpb;
619 1.88 perseant fs->lfs_ino_bitmap = (lfs_bm_t *)
620 1.88 perseant malloc(((maxino + BMMASK) >> BMSHIFT) * sizeof(lfs_bm_t),
621 1.88 perseant M_SEGMENT, M_WAITOK | M_ZERO);
622 1.88 perseant KASSERT(fs->lfs_ino_bitmap != NULL);
623 1.87 perseant
624 1.87 perseant firstino = lastino = LFS_UNUSED_INUM;
625 1.87 perseant for (ino = 0; ino < maxino; ino++) {
626 1.87 perseant if (ino % fs->lfs_ifpb == 0)
627 1.87 perseant LFS_IENTRY(ifp, fs, ino, bp);
628 1.87 perseant else
629 1.87 perseant ++ifp;
630 1.87 perseant
631 1.87 perseant /* Don't put zero or ifile on the free list */
632 1.87 perseant if (ino == LFS_UNUSED_INUM || ino == LFS_IFILE_INUM)
633 1.87 perseant continue;
634 1.87 perseant
635 1.97 perseant #ifdef notyet
636 1.97 perseant /* Address orphaned files */
637 1.97 perseant if (ifp->if_nextfree == LFS_ORPHAN_NEXTFREE &&
638 1.97 perseant VFS_VGET(fs->lfs_ivnode->v_mount, ino, &vp) == 0) {
639 1.97 perseant lfs_truncate(vp, 0, 0, NOCRED, curlwp);
640 1.97 perseant vput(vp);
641 1.97 perseant LFS_SEGENTRY(sup, fs, dtosn(fs, ifp->if_daddr), bp);
642 1.97 perseant KASSERT(sup->su_nbytes >= DINODE1_SIZE);
643 1.97 perseant sup->su_nbytes -= DINODE1_SIZE;
644 1.97 perseant LFS_WRITESEGENTRY(sup, fs, dtosn(fs, ifp->if_daddr), bp);
645 1.97 perseant
646 1.97 perseant /* Set up to fall through to next section */
647 1.97 perseant ifp->if_daddr = LFS_UNUSED_DADDR;
648 1.97 perseant LFS_BWRITE_LOG(bp);
649 1.97 perseant LFS_IENTRY(ifp, fs, ino, bp);
650 1.97 perseant }
651 1.97 perseant #endif
652 1.97 perseant
653 1.87 perseant if (ifp->if_daddr == LFS_UNUSED_DADDR) {
654 1.87 perseant if (firstino == LFS_UNUSED_INUM)
655 1.87 perseant firstino = ino;
656 1.87 perseant else {
657 1.87 perseant brelse(bp);
658 1.87 perseant
659 1.87 perseant LFS_IENTRY(ifp, fs, lastino, bp);
660 1.87 perseant ifp->if_nextfree = ino;
661 1.87 perseant LFS_BWRITE_LOG(bp);
662 1.87 perseant
663 1.87 perseant LFS_IENTRY(ifp, fs, ino, bp);
664 1.87 perseant }
665 1.87 perseant lastino = ino;
666 1.87 perseant
667 1.87 perseant SET_BITMAP_FREE(fs, ino);
668 1.87 perseant }
669 1.87 perseant
670 1.87 perseant if ((ino + 1) % fs->lfs_ifpb == 0)
671 1.87 perseant brelse(bp);
672 1.87 perseant }
673 1.87 perseant
674 1.87 perseant LFS_PUT_HEADFREE(fs, cip, bp, firstino);
675 1.87 perseant LFS_PUT_TAILFREE(fs, cip, bp, lastino);
676 1.95 perseant
677 1.95 perseant lfs_segunlock(fs);
678 1.87 perseant }
679 1.97 perseant
680 1.97 perseant void
681 1.97 perseant lfs_orphan(struct lfs *fs, ino_t ino)
682 1.97 perseant {
683 1.97 perseant IFILE *ifp;
684 1.97 perseant struct buf *bp;
685 1.97 perseant
686 1.97 perseant LFS_IENTRY(ifp, fs, ino, bp);
687 1.97 perseant ifp->if_nextfree = LFS_ORPHAN_NEXTFREE;
688 1.97 perseant LFS_BWRITE_LOG(bp);
689 1.97 perseant }
690