/* Copyright (c) 1981 Regents of the University of California */
static char vers
[] = "@(#)ffs_alloc.c 1.19 %G%";
/* alloc.c 4.8 81/03/08 */
extern u_long
hashalloc();
extern daddr_t
alloccg();
extern daddr_t
alloccgblk();
extern daddr_t
fragextend();
extern daddr_t
blkpref();
extern daddr_t
mapsearch();
extern int inside
[], around
[];
extern unsigned char *fragtbl
[];
* Allocate a block in the file system.
* The size of the requested block is given, which must be some
* multiple of fs_fsize and <= fs_bsize.
* A preference may be optionally specified. If a preference is given
* the following hierarchy is used to allocate a block:
* 1) allocate the requested block.
* 2) allocate a rotationally optimal block in the same cylinder.
* 3) allocate a block in the same cylinder group.
* 4) quadradically rehash into other cylinder groups, until an
* available block is located.
* If no block preference is given the following heirarchy is used
* 1) allocate a block in the cylinder group that contains the
* 2) quadradically rehash into other cylinder groups, until an
* available block is located.
register struct inode
*ip
;
if ((unsigned)size
> fs
->fs_bsize
|| fragoff(fs
, size
) != 0)
panic("alloc: bad size");
if (size
== fs
->fs_bsize
&& fs
->fs_cstotal
.cs_nbfree
== 0)
fs
->fs_cstotal
.cs_nbfree
* fs
->fs_frag
+ fs
->fs_cstotal
.cs_nffree
<
fs
->fs_dsize
* fs
->fs_minfree
/ 100)
if (bpref
>= fs
->fs_size
)
cg
= itog(fs
, ip
->i_number
);
bno
= (daddr_t
)hashalloc(ip
, cg
, (long)bpref
, size
, alloccg
);
bp
= getblk(ip
->i_dev
, fsbtodb(fs
, bno
), size
);
fserr(fs
, "file system full");
uprintf("\n%s: write failed, file system is full\n", fs
->fs_fsmnt
);
* Reallocate a fragment to a bigger size
* The number and size of the old block is given, and a preference
* and new size is also specified. The allocator attempts to extend
* the original block. Failing that, the regular block allocator is
* invoked to get an appropriate block.
realloccg(ip
, bprev
, bpref
, osize
, nsize
)
register struct inode
*ip
;
register struct buf
*bp
, *obp
;
if ((unsigned)osize
> fs
->fs_bsize
|| fragoff(fs
, osize
) != 0 ||
(unsigned)nsize
> fs
->fs_bsize
|| fragoff(fs
, nsize
) != 0)
panic("realloccg: bad size");
fs
->fs_cstotal
.cs_nbfree
* fs
->fs_frag
+ fs
->fs_cstotal
.cs_nffree
<
fs
->fs_dsize
* fs
->fs_minfree
/ 100)
panic("realloccg: bad bprev");
bno
= fragextend(ip
, cg
, (long)bprev
, osize
, nsize
);
bp
= bread(ip
->i_dev
, fsbtodb(fs
, bno
), osize
);
if (bp
->b_flags
& B_ERROR
) {
blkclr(bp
->b_un
.b_addr
+ osize
, nsize
- osize
);
if (bpref
>= fs
->fs_size
)
bno
= (daddr_t
)hashalloc(ip
, cg
, (long)bpref
, nsize
, alloccg
);
obp
= bread(ip
->i_dev
, fsbtodb(fs
, bprev
), osize
);
if (obp
->b_flags
& B_ERROR
) {
bp
= getblk(ip
->i_dev
, fsbtodb(fs
, bno
), nsize
);
bp
->b_un
.b_addr
= obp
->b_un
.b_addr
;
fre(ip
, bprev
, (off_t
)osize
);
blkclr(bp
->b_un
.b_addr
+ osize
, nsize
- osize
);
fserr(fs
, "file system full");
uprintf("\n%s: write failed, file system is full\n", fs
->fs_fsmnt
);
* Allocate an inode in the file system.
* A preference may be optionally specified. If a preference is given
* the following hierarchy is used to allocate an inode:
* 1) allocate the requested inode.
* 2) allocate an inode in the same cylinder group.
* 3) quadradically rehash into other cylinder groups, until an
* available inode is located.
* If no inode preference is given the following heirarchy is used
* 1) allocate an inode in cylinder group 0.
* 2) quadradically rehash into other cylinder groups, until an
* available inode is located.
register struct inode
*pip
;
register struct inode
*ip
;
if (fs
->fs_cstotal
.cs_nifree
== 0)
if (ipref
>= fs
->fs_ncg
* fs
->fs_ipg
)
ino
= (ino_t
)hashalloc(pip
, cg
, (long)ipref
, mode
, ialloccg
);
ip
= iget(pip
->i_dev
, pip
->i_fs
, ino
);
panic("ialloc: dup alloc");
fserr(fs
, "out of inodes");
uprintf("\n%s: create failed, no inodes free\n", fs
->fs_fsmnt
);
* Find a cylinder to place a directory.
* The policy implemented by this algorithm is to select from
* among those cylinder groups with above the average number of
* free inodes, the one with the smallest number of directories.
int cg
, minndir
, mincg
, avgifree
;
avgifree
= fs
->fs_cstotal
.cs_nifree
/ fs
->fs_ncg
;
for (cg
= 0; cg
< fs
->fs_ncg
; cg
++)
if (fs
->fs_cs(fs
, cg
).cs_ndir
< minndir
&&
fs
->fs_cs(fs
, cg
).cs_nifree
>= avgifree
) {
minndir
= fs
->fs_cs(fs
, cg
).cs_ndir
;
return (fs
->fs_ipg
* mincg
);
* Select a cylinder to place a large block of data.
* The policy implemented by this algorithm is to maintain a
* rotor that sweeps the cylinder groups. When a block is
* needed, the rotor is advanced until a cylinder group with
* greater than the average number of free blocks is found.
avgbfree
= fs
->fs_cstotal
.cs_nbfree
/ fs
->fs_ncg
;
for (cg
= fs
->fs_cgrotor
+ 1; cg
< fs
->fs_ncg
; cg
++)
if (fs
->fs_cs(fs
, cg
).cs_nbfree
>= avgbfree
) {
return (fs
->fs_fpg
* cg
+ fs
->fs_frag
);
for (cg
= 0; cg
<= fs
->fs_cgrotor
; cg
++)
if (fs
->fs_cs(fs
, cg
).cs_nbfree
>= avgbfree
) {
return (fs
->fs_fpg
* cg
+ fs
->fs_frag
);
* Implement the cylinder overflow algorithm.
* The policy implemented by this algorithm is:
* 1) allocate the block in its requested cylinder group.
* 2) quadradically rehash on the cylinder group number.
* 3) brute force search for a free block.
hashalloc(ip
, cg
, pref
, size
, allocator
)
int size
; /* size for data blocks, mode for inodes */
* 1: preferred cylinder group
result
= (*allocator
)(ip
, cg
, pref
, size
);
for (i
= 1; i
< fs
->fs_ncg
; i
*= 2) {
result
= (*allocator
)(ip
, cg
, 0, size
);
for (i
= 0; i
< fs
->fs_ncg
; i
++) {
result
= (*allocator
)(ip
, cg
, 0, size
);
* Determine whether a fragment can be extended.
* Check to see if the necessary fragments are available, and
* if they are, allocate them.
fragextend(ip
, cg
, bprev
, osize
, nsize
)
frags
= numfrags(fs
, nsize
);
bbase
= fragoff(fs
, bprev
);
if (bbase
> (bprev
+ frags
- 1) % fs
->fs_frag
) {
/* cannot extend across a block boundry */
bp
= bread(ip
->i_dev
, fsbtodb(fs
, cgtod(fs
, cg
)), fs
->fs_bsize
);
if (bp
->b_flags
& B_ERROR
) {
for (i
= numfrags(fs
, osize
); i
< frags
; i
++)
if (isclr(cgp
->cg_free
, bno
+ i
)) {
* the current fragment can be extended
* deduct the count on fragment being extended into
* increase the count on the remaining fragment (if any)
* allocate the extended piece
for (i
= frags
; i
< fs
->fs_frag
- bbase
; i
++)
if (isclr(cgp
->cg_free
, bno
+ i
))
cgp
->cg_frsum
[i
- numfrags(fs
, osize
)]--;
cgp
->cg_frsum
[i
- frags
]++;
for (i
= numfrags(fs
, osize
); i
< frags
; i
++) {
clrbit(cgp
->cg_free
, bno
+ i
);
fs
->fs_cstotal
.cs_nffree
--;
fs
->fs_cs(fs
, cg
).cs_nffree
--;
* Determine whether a block can be allocated.
* Check to see if a block of the apprpriate size is available,
* and if it is, allocate it.
alloccg(ip
, cg
, bpref
, size
)
if (fs
->fs_cs(fs
, cg
).cs_nbfree
== 0 && size
== fs
->fs_bsize
)
bp
= bread(ip
->i_dev
, fsbtodb(fs
, cgtod(fs
, cg
)), fs
->fs_bsize
);
if (bp
->b_flags
& B_ERROR
) {
if (size
== fs
->fs_bsize
) {
bno
= alloccgblk(fs
, cgp
, bpref
);
* check to see if any fragments are already available
* allocsiz is the size which will be allocated, hacking
* it down to a smaller size if necessary
frags
= numfrags(fs
, size
);
for (allocsiz
= frags
; allocsiz
< fs
->fs_frag
; allocsiz
++)
if (cgp
->cg_frsum
[allocsiz
] != 0)
if (allocsiz
== fs
->fs_frag
) {
* no fragments were available, so a block will be
* allocated, and hacked up
if (cgp
->cg_cs
.cs_nbfree
== 0) {
bno
= alloccgblk(fs
, cgp
, bpref
);
for (i
= frags
; i
< fs
->fs_frag
; i
++)
setbit(cgp
->cg_free
, bpref
+ i
);
cgp
->cg_cs
.cs_nffree
+= i
;
fs
->fs_cstotal
.cs_nffree
+= i
;
fs
->fs_cs(fs
, cg
).cs_nffree
+= i
;
bno
= mapsearch(fs
, cgp
, bpref
, allocsiz
);
for (i
= 0; i
< frags
; i
++)
clrbit(cgp
->cg_free
, bno
+ i
);
cgp
->cg_cs
.cs_nffree
-= frags
;
fs
->fs_cstotal
.cs_nffree
-= frags
;
fs
->fs_cs(fs
, cg
).cs_nffree
-= frags
;
cgp
->cg_frsum
[allocsiz
]--;
cgp
->cg_frsum
[allocsiz
- frags
]++;
return (cg
* fs
->fs_fpg
+ bno
);
* Allocate a block in a cylinder group.
* This algorithm implements the following policy:
* 1) allocate the requested block.
* 2) allocate a rotationally optimal block in the same cylinder.
* 3) allocate the next available block on the block rotor for the
* specified cylinder group.
* Note that this routine only allocates fs_bsize blocks; these
* blocks may be fragmented by the routine that allocates them.
alloccgblk(fs
, cgp
, bpref
)
bpref
&= ~(fs
->fs_frag
- 1);
bpref
= dtogd(fs
, bpref
);
* if the requested block is available, use it
if (isblock(fs
, cgp
->cg_free
, bpref
/fs
->fs_frag
)) {
* check for a block available on the same cylinder
cylno
= cbtocylno(fs
, bpref
);
if (cgp
->cg_btot
[cylno
] == 0)
* block layout info is not available, so just have
* to take any block in this cylinder.
bpref
= howmany(fs
->fs_spc
* cylno
, NSPF(fs
));
* find a block that is rotationally optimal
cylbp
= cgp
->cg_b
[cylno
];
if (fs
->fs_rotdelay
== 0) {
pos
= cbtorpos(fs
, bpref
);
* here we convert ms of delay to frags as:
* (frags) = (ms) * (rev/sec) * (sect/rev) /
* ((sect/frag) * (ms/sec))
* then round up to the next rotational position
bpref
+= fs
->fs_rotdelay
* fs
->fs_rps
* fs
->fs_nsect
/
pos
= cbtorpos(fs
, bpref
);
* check the summary information to see if a block is
* available in the requested cylinder starting at the
* optimal rotational position and proceeding around.
for (i
= pos
; i
< NRPOS
; i
++)
for (i
= 0; i
< pos
; i
++)
* found a rotational position, now find the actual
* block. A panic if none is actually there.
pos
= cylno
% fs
->fs_cpc
;
bno
= (cylno
- pos
) * fs
->fs_spc
/ NSPB(fs
);
if (fs
->fs_postbl
[pos
][i
] == -1)
panic("alloccgblk: cyl groups corrupted");
for (i
= fs
->fs_postbl
[pos
][i
]; ; i
+= fs
->fs_rotbl
[i
]) {
if (isblock(fs
, cgp
->cg_free
, bno
+ i
)) {
bno
= (bno
+ i
) * fs
->fs_frag
;
if (fs
->fs_rotbl
[i
] == 0)
panic("alloccgblk: can't find blk in cyl");
* no blocks in the requested cylinder, so take next
* available one in this cylinder group.
bno
= mapsearch(fs
, cgp
, bpref
, fs
->fs_frag
);
clrblock(fs
, cgp
->cg_free
, bno
/fs
->fs_frag
);
fs
->fs_cstotal
.cs_nbfree
--;
fs
->fs_cs(fs
, cgp
->cg_cgx
).cs_nbfree
--;
cylno
= cbtocylno(fs
, bno
);
cgp
->cg_b
[cylno
][cbtorpos(fs
, bno
)]--;
return (cgp
->cg_cgx
* fs
->fs_fpg
+ bno
);
* Determine whether an inode can be allocated.
* Check to see if an inode is available, and if it is,
* allocate it using the following policy:
* 1) allocate the requested inode.
* 2) allocate the next available inode after the requested
* inode in the specified cylinder group.
ialloccg(ip
, cg
, ipref
, mode
)
if (fs
->fs_cs(fs
, cg
).cs_nifree
== 0)
bp
= bread(ip
->i_dev
, fsbtodb(fs
, cgtod(fs
, cg
)), fs
->fs_bsize
);
if (bp
->b_flags
& B_ERROR
) {
if (isclr(cgp
->cg_iused
, ipref
))
for (i
= 0; i
< fs
->fs_ipg
; i
++) {
if (isclr(cgp
->cg_iused
, ipref
)) {
setbit(cgp
->cg_iused
, ipref
);
fs
->fs_cstotal
.cs_nifree
--;
fs
->fs_cs(fs
, cg
).cs_nifree
--;
if ((mode
& IFMT
) == IFDIR
) {
fs
->fs_cstotal
.cs_ndir
++;
fs
->fs_cs(fs
, cg
).cs_ndir
++;
return (cg
* fs
->fs_ipg
+ ipref
);
* Free a block or fragment.
* The specified block or fragment is placed back in the
* free map. If a fragment is deallocated, a possible
* block reassembly is checked.
register struct inode
*ip
;
int cg
, blk
, frags
, bbase
;
if ((unsigned)size
> fs
->fs_bsize
|| fragoff(fs
, size
) != 0)
bp
= bread(ip
->i_dev
, fsbtodb(fs
, cgtod(fs
, cg
)), fs
->fs_bsize
);
if (bp
->b_flags
& B_ERROR
) {
if (size
== fs
->fs_bsize
) {
if (isblock(fs
, cgp
->cg_free
, bno
/fs
->fs_frag
))
panic("free: freeing free block");
setblock(fs
, cgp
->cg_free
, bno
/fs
->fs_frag
);
fs
->fs_cstotal
.cs_nbfree
++;
fs
->fs_cs(fs
, cg
).cs_nbfree
++;
cgp
->cg_b
[i
][cbtorpos(fs
, bno
)]++;
bbase
= bno
- (bno
% fs
->fs_frag
);
* decrement the counts associated with the old frags
blk
= ((cgp
->cg_free
[bbase
/ NBBY
] >> (bbase
% NBBY
)) &
(0xff >> (NBBY
- fs
->fs_frag
)));
fragacct(fs
, blk
, cgp
->cg_frsum
, -1);
* deallocate the fragment
frags
= numfrags(fs
, size
);
for (i
= 0; i
< frags
; i
++) {
if (isset(cgp
->cg_free
, bno
+ i
))
panic("free: freeing free frag");
setbit(cgp
->cg_free
, bno
+ i
);
fs
->fs_cstotal
.cs_nffree
++;
fs
->fs_cs(fs
, cg
).cs_nffree
++;
* add back in counts associated with the new frags
blk
= ((cgp
->cg_free
[bbase
/ NBBY
] >> (bbase
% NBBY
)) &
(0xff >> (NBBY
- fs
->fs_frag
)));
fragacct(fs
, blk
, cgp
->cg_frsum
, 1);
* if a complete block has been reassembled, account for it
if (isblock(fs
, cgp
->cg_free
, bbase
/ fs
->fs_frag
)) {
cgp
->cg_cs
.cs_nffree
-= fs
->fs_frag
;
fs
->fs_cstotal
.cs_nffree
-= fs
->fs_frag
;
fs
->fs_cs(fs
, cg
).cs_nffree
-= fs
->fs_frag
;
fs
->fs_cstotal
.cs_nbfree
++;
fs
->fs_cs(fs
, cg
).cs_nbfree
++;
i
= cbtocylno(fs
, bbase
);
cgp
->cg_b
[i
][cbtorpos(fs
, bbase
)]++;
* The specified inode is placed back in the free map.
if ((unsigned)ino
>= fs
->fs_ipg
*fs
->fs_ncg
)
bp
= bread(ip
->i_dev
, fsbtodb(fs
, cgtod(fs
, cg
)), fs
->fs_bsize
);
if (bp
->b_flags
& B_ERROR
) {
if (isclr(cgp
->cg_iused
, ino
))
panic("ifree: freeing free inode");
clrbit(cgp
->cg_iused
, ino
);
fs
->fs_cstotal
.cs_nifree
++;
fs
->fs_cs(fs
, cg
).cs_nifree
++;
if ((mode
& IFMT
) == IFDIR
) {
fs
->fs_cstotal
.cs_ndir
--;
fs
->fs_cs(fs
, cg
).cs_ndir
--;
* Find a block of the specified size in the specified cylinder group.
* It is a panic if a request is made to find a block if none are
mapsearch(fs
, cgp
, bpref
, allocsiz
)
int blk
, field
, subfield
, pos
;
* find the fragment by searching through the free block
* map for an appropriate bit pattern
start
= dtogd(fs
, bpref
) / NBBY
;
start
= cgp
->cg_frotor
/ NBBY
;
len
= howmany(fs
->fs_fpg
, NBBY
) - start
;
loc
= scanc(len
, &cgp
->cg_free
[start
], fragtbl
[fs
->fs_frag
],
loc
= fs
->fs_dblkno
/ NBBY
;
loc
= scanc(len
, &cgp
->cg_free
[start
], fragtbl
[fs
->fs_frag
],
panic("alloccg: map corrupted");
bno
= (start
+ len
- loc
) * NBBY
;
* found the byte in the map
* sift through the bits to find the selected frag
for (i
= 0; i
< NBBY
; i
+= fs
->fs_frag
) {
blk
= (cgp
->cg_free
[bno
/ NBBY
] >> i
) &
(0xff >> NBBY
- fs
->fs_frag
);
field
= around
[allocsiz
];
subfield
= inside
[allocsiz
];
for (pos
= 0; pos
<= fs
->fs_frag
- allocsiz
; pos
++) {
if ((blk
& field
) == subfield
) {
panic("alloccg: block not in map");
* Update the frsum fields to reflect addition or deletion
fragacct(fs
, fragmap
, fraglist
, cnt
)
register int field
, subfield
;
inblk
= (int)(fragtbl
[fs
->fs_frag
][fragmap
]) << 1;
for (siz
= 1; siz
< fs
->fs_frag
; siz
++) {
if (((1 << siz
) & inblk
) == 0)
for (pos
= siz
; pos
<= fs
->fs_frag
; pos
++) {
if ((fragmap
& field
) == subfield
) {
* Check that a specified block number is in range.
if ((unsigned)bn
>= fs
->fs_size
|| bn
< cgdmin(fs
, dtog(fs
, bn
))) {
* Getfs maps a device number into a pointer to the incore super block.
* The algorithm is a linear search through the mount table. A
* consistency check of the super block magic number is performed.
* panic: no fs -- the device is not mounted.
register struct mount
*mp
;
for (mp
= &mount
[0]; mp
< &mount
[NMOUNT
]; mp
++)
if (mp
->m_bufp
!= NULL
&& mp
->m_dev
== dev
) {
fs
= mp
->m_bufp
->b_un
.b_fs
;
if (fs
->fs_magic
!= FS_MAGIC
)
panic("getfs: bad magic");
* Fserr prints the name of a file system with an error diagnostic.
* The form of the error message is:
printf("%s: %s\n", fs
->fs_fsmnt
, cp
);
* Getfsx returns the index in the file system
* table of the specified device. The swap device
* is also assigned a pseudo-index. The index may
* be used as a compressed indication of the location
* provided the information need remain valid only
* as long as the file system is mounted.
register struct mount
*mp
;
for(mp
= &mount
[0]; mp
< &mount
[NMOUNT
]; mp
++)
* Update is the internal name of 'sync'. It goes through the disk
* queues to initiate sandbagged IO; goes through the inodes to write
* modified nodes; and it goes through the mount table to initiate
* the writing of the modified super blocks.
register struct inode
*ip
;
register struct mount
*mp
;
* Write back modified superblocks.
* Consistency check that the superblock
* of each file system is still in the buffer cache.
for (mp
= &mount
[0]; mp
< &mount
[NMOUNT
]; mp
++)
if (mp
->m_bufp
!= NULL
) {
fs
= mp
->m_bufp
->b_un
.b_fs
;
panic("update: rofs mod");
bp
= getblk(mp
->m_dev
, SBLOCK
, SBSIZE
);
panic("update: bad b_fs");
blks
= howmany(fs
->fs_cssize
, fs
->fs_bsize
);
for (i
= 0; i
< blks
; i
++) {
fsbtodb(fs
, fs
->fs_csaddr
+ (i
* fs
->fs_frag
)),
* Write back each (modified) inode.
for (ip
= inode
; ip
< inodeNINODE
; ip
++)
if((ip
->i_flag
&ILOCK
)==0 && ip
->i_count
) {
iupdat(ip
, &tim
, &tim
, 0);
* Force stale buffer cache information to be flushed,
* check if a block is available
mask
= 0x0f << ((h
& 0x1) << 2);
return ((cp
[h
>> 1] & mask
) == mask
);
mask
= 0x03 << ((h
& 0x3) << 1);
return ((cp
[h
>> 2] & mask
) == mask
);
mask
= 0x01 << (h
& 0x7);
return ((cp
[h
>> 3] & mask
) == mask
);
panic("isblock bad fs_frag");
* take a block out of the map
cp
[h
>> 1] &= ~(0x0f << ((h
& 0x1) << 2));
cp
[h
>> 2] &= ~(0x03 << ((h
& 0x3) << 1));
cp
[h
>> 3] &= ~(0x01 << (h
& 0x7));
panic("clrblock bad fs_frag");
* put a block into the map
cp
[h
>> 1] |= (0x0f << ((h
& 0x1) << 2));
cp
[h
>> 2] |= (0x03 << ((h
& 0x3) << 1));
cp
[h
>> 3] |= (0x01 << (h
& 0x7));
panic("setblock bad fs_frag");