ffs_alloc.c (74747) | ffs_alloc.c (75377) |
---|---|
1/* 2 * Copyright (c) 1982, 1986, 1989, 1993 3 * The Regents of the University of California. 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 * 1. Redistributions of source code must retain the above copyright --- 17 unchanged lines hidden (view full) --- 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 * 33 * @(#)ffs_alloc.c 8.18 (Berkeley) 5/26/95 | 1/* 2 * Copyright (c) 1982, 1986, 1989, 1993 3 * The Regents of the University of California. 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 * 1. Redistributions of source code must retain the above copyright --- 17 unchanged lines hidden (view full) --- 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 * 33 * @(#)ffs_alloc.c 8.18 (Berkeley) 5/26/95 |
34 * $FreeBSD: head/sys/ufs/ffs/ffs_alloc.c 74747 2001-03-24 15:25:04Z asmodai $ | 34 * $FreeBSD: head/sys/ufs/ffs/ffs_alloc.c 75377 2001-04-10 08:38:59Z mckusick $ |
35 */ 36 37#include "opt_quota.h" 38 39#include <sys/param.h> 40#include <sys/systm.h> 41#include <sys/bio.h> 42#include <sys/buf.h> --- 23 unchanged lines hidden (view full) --- 66 ffs_alloccgblk __P((struct inode *, struct buf *, ufs_daddr_t)); 67#ifdef DIAGNOSTIC 68static int ffs_checkblk __P((struct inode *, ufs_daddr_t, long)); 69#endif 70static void ffs_clusteracct __P((struct fs *, struct cg *, ufs_daddr_t, 71 int)); 72static ufs_daddr_t ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t, 73 int)); | 35 */ 36 37#include "opt_quota.h" 38 39#include <sys/param.h> 40#include <sys/systm.h> 41#include <sys/bio.h> 42#include <sys/buf.h> --- 23 unchanged lines hidden (view full) --- 66 ffs_alloccgblk __P((struct inode *, struct buf *, ufs_daddr_t)); 67#ifdef DIAGNOSTIC 68static int ffs_checkblk __P((struct inode *, ufs_daddr_t, long)); 69#endif 70static void ffs_clusteracct __P((struct fs *, struct cg *, ufs_daddr_t, 71 int)); 72static ufs_daddr_t ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t, 73 int)); |
74static ino_t ffs_dirpref __P((struct fs *)); | 74static ino_t ffs_dirpref __P((struct inode *)); |
75static ufs_daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 76static void ffs_fserr __P((struct fs *, u_int, char *)); 77static u_long ffs_hashalloc 78 __P((struct inode *, int, long, int, allocfcn_t *)); 79static ino_t ffs_nodealloccg __P((struct inode *, int, ufs_daddr_t, int)); 80static ufs_daddr_t ffs_mapsearch __P((struct fs *, struct cg *, ufs_daddr_t, 81 int)); 82 --- 505 unchanged lines hidden (view full) --- 588 589 *vpp = NULL; 590 pip = VTOI(pvp); 591 fs = pip->i_fs; 592 if (fs->fs_cstotal.cs_nifree == 0) 593 goto noinodes; 594 595 if ((mode & IFMT) == IFDIR) | 75static ufs_daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 76static void ffs_fserr __P((struct fs *, u_int, char *)); 77static u_long ffs_hashalloc 78 __P((struct inode *, int, long, int, allocfcn_t *)); 79static ino_t ffs_nodealloccg __P((struct inode *, int, ufs_daddr_t, int)); 80static ufs_daddr_t ffs_mapsearch __P((struct fs *, struct cg *, ufs_daddr_t, 81 int)); 82 --- 505 unchanged lines hidden (view full) --- 588 589 *vpp = NULL; 590 pip = VTOI(pvp); 591 fs = pip->i_fs; 592 if (fs->fs_cstotal.cs_nifree == 0) 593 goto noinodes; 594 595 if ((mode & IFMT) == IFDIR) |
596 ipref = ffs_dirpref(fs); | 596 ipref = ffs_dirpref(pip); |
597 else 598 ipref = pip->i_number; 599 if (ipref >= fs->fs_ncg * fs->fs_ipg) 600 ipref = 0; 601 cg = ino_to_cg(fs, ipref); | 597 else 598 ipref = pip->i_number; 599 if (ipref >= fs->fs_ncg * fs->fs_ipg) 600 ipref = 0; 601 cg = ino_to_cg(fs, ipref); |
602 /* 603 * Track number of dirs created one after another 604 * in a same cg without intervening by files. 605 */ 606 if ((mode & IFMT) == IFDIR) { 607 if (fs->fs_contigdirs[cg] < 255) 608 fs->fs_contigdirs[cg]++; 609 } else { 610 if (fs->fs_contigdirs[cg] > 0) 611 fs->fs_contigdirs[cg]--; 612 } |
|
602 ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, 603 (allocfcn_t *)ffs_nodealloccg); 604 if (ino == 0) 605 goto noinodes; 606 error = VFS_VGET(pvp->v_mount, ino, vpp); 607 if (error) { 608 UFS_VFREE(pvp, ino, mode); 609 return (error); --- 18 unchanged lines hidden (view full) --- 628 return (0); 629noinodes: 630 ffs_fserr(fs, cred->cr_uid, "out of inodes"); 631 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 632 return (ENOSPC); 633} 634 635/* | 613 ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, 614 (allocfcn_t *)ffs_nodealloccg); 615 if (ino == 0) 616 goto noinodes; 617 error = VFS_VGET(pvp->v_mount, ino, vpp); 618 if (error) { 619 UFS_VFREE(pvp, ino, mode); 620 return (error); --- 18 unchanged lines hidden (view full) --- 639 return (0); 640noinodes: 641 ffs_fserr(fs, cred->cr_uid, "out of inodes"); 642 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 643 return (ENOSPC); 644} 645 646/* |
636 * Find a cylinder to place a directory. | 647 * Find a cylinder group to place a directory. |
637 * | 648 * |
638 * The policy implemented by this algorithm is to select from 639 * among those cylinder groups with above the average number of 640 * free inodes, the one with the smallest number of directories. | 649 * The policy implemented by this algorithm is to allocate a 650 * directory inode in the same cylinder group as its parent 651 * directory, but also to reserve space for its files inodes 652 * and data. Restrict the number of directories which may be 653 * allocated one after another in the same cylinder group 654 * without intervening allocation of files. 655 * 656 * If we allocate a first level directory then force allocation 657 * in another cylinder group. |
641 */ 642static ino_t | 658 */ 659static ino_t |
643ffs_dirpref(fs) 644 register struct fs *fs; | 660ffs_dirpref(pip) 661 struct inode *pip; |
645{ | 662{ |
646 int cg, minndir, mincg, avgifree; | 663 register struct fs *fs; 664 int cg, prefcg, dirsize, cgsize; 665 int avgifree, avgbfree, avgndir, curdirsize; 666 int minifree, minbfree, maxndir; 667 int mincg, minndir; 668 int maxcontigdirs; |
647 | 669 |
670 fs = pip->i_fs; 671 |
|
648 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; | 672 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; |
649 minndir = fs->fs_ipg; 650 mincg = 0; 651 for (cg = 0; cg < fs->fs_ncg; cg++) 652 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 653 fs->fs_cs(fs, cg).cs_nifree >= avgifree) { 654 mincg = cg; 655 minndir = fs->fs_cs(fs, cg).cs_ndir; | 673 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 674 avgndir = fs->fs_cstotal.cs_ndir / fs->fs_ncg; 675 676 /* 677 * Force allocation in another cg if creating a first level dir. 678 */ 679 if (ITOV(pip)->v_flag & VROOT) { 680 prefcg = arc4random() % fs->fs_ncg; 681 mincg = prefcg; 682 minndir = fs->fs_ipg; 683 for (cg = prefcg; cg < fs->fs_ncg; cg++) 684 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 685 fs->fs_cs(fs, cg).cs_nifree >= avgifree && 686 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 687 mincg = cg; 688 minndir = fs->fs_cs(fs, cg).cs_ndir; 689 } 690 for (cg = 0; cg < prefcg; cg++) 691 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 692 fs->fs_cs(fs, cg).cs_nifree >= avgifree && 693 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 694 mincg = cg; 695 minndir = fs->fs_cs(fs, cg).cs_ndir; 696 } 697 return ((ino_t)(fs->fs_ipg * mincg)); 698 } 699 700 /* 701 * Count various limits which used for 702 * optimal allocation of a directory inode. 703 */ 704 maxndir = min(avgndir + fs->fs_ipg / 16, fs->fs_ipg); 705 minifree = avgifree - fs->fs_ipg / 4; 706 if (minifree < 0) 707 minifree = 0; 708 minbfree = avgbfree - fs->fs_fpg / fs->fs_frag / 4; 709 if (minbfree < 0) 710 minbfree = 0; 711 cgsize = fs->fs_fsize * fs->fs_fpg; 712 dirsize = fs->fs_avgfilesize * fs->fs_avgfpdir; 713 curdirsize = avgndir ? (cgsize - avgbfree * fs->fs_bsize) / avgndir : 0; 714 if (dirsize < curdirsize) 715 dirsize = curdirsize; 716 maxcontigdirs = min(cgsize / dirsize, 255); 717 if (fs->fs_avgfpdir > 0) 718 maxcontigdirs = min(maxcontigdirs, 719 fs->fs_ipg / fs->fs_avgfpdir); 720 if (maxcontigdirs == 0) 721 maxcontigdirs = 1; 722 723 /* 724 * Limit number of dirs in one cg and reserve space for 725 * regular files, but only if we have no deficit in 726 * inodes or space. 727 */ 728 prefcg = ino_to_cg(fs, pip->i_number); 729 for (cg = prefcg; cg < fs->fs_ncg; cg++) 730 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 731 fs->fs_cs(fs, cg).cs_nifree >= minifree && 732 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 733 if (fs->fs_contigdirs[cg] < maxcontigdirs) 734 return ((ino_t)(fs->fs_ipg * cg)); |
656 } | 735 } |
657 return ((ino_t)(fs->fs_ipg * mincg)); | 736 for (cg = 0; cg < prefcg; cg++) 737 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 738 fs->fs_cs(fs, cg).cs_nifree >= minifree && 739 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 740 if (fs->fs_contigdirs[cg] < maxcontigdirs) 741 return ((ino_t)(fs->fs_ipg * cg)); 742 } 743 /* 744 * This is a backstop when we have deficit in space. 745 */ 746 for (cg = prefcg; cg < fs->fs_ncg; cg++) 747 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 748 return ((ino_t)(fs->fs_ipg * cg)); 749 for (cg = 0; cg < prefcg; cg++) 750 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 751 break; 752 return ((ino_t)(fs->fs_ipg * cg)); |
658} 659 660/* 661 * Select the desired position for the next block in a file. The file is 662 * logically divided into sections. The first section is composed of the 663 * direct blocks. Each additional section contains fs_maxbpg blocks. 664 * 665 * If no blocks have been allocated in the first section, the policy is to --- 1270 unchanged lines hidden --- | 753} 754 755/* 756 * Select the desired position for the next block in a file. The file is 757 * logically divided into sections. The first section is composed of the 758 * direct blocks. Each additional section contains fs_maxbpg blocks. 759 * 760 * If no blocks have been allocated in the first section, the policy is to --- 1270 unchanged lines hidden --- |