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