Unix Programming - A question about file operation

Author

A question about file operation

windstorm

2007-06-14, 7:22 pm

int main( void )
{
int fd,size,position;
char buf[20];
char lkl[] = "hello,world!";
fd = creat( "test",0644 );
size = write( fd,lkl,sizeof(lkl) );
close(fd);
fd = open( "test",O_RDWR );
size = read( fd,buf,sizeof(buf) );
printf( "fd is %s,the length is %d\n\n",buf,size );
position = lseek( fd,70000000,SEEK_END);
size = write( fd,lk,sizeof(lkl) );
close(fd);
return 1;

}

This is just test code, I wanna see what the file will be if I make
the file pointer point to the end and move it by API lseek. That is
what you can see in the code. After a lot of tests, I found that the
file's size which can be saw by the command "ls -ls" will change
according to the lseek's second parameter distance.

For example:

If the dist is 4000 or less than 4000, the block which is filled by
file "test" will be 4K, it's reasonable for the minimal size of block
is 4K.

If the dist is 5000-480000, the block which is filled by file "test"
will be 8K, it's reasonable for the position where the second string
lk be written is out of block 1, so maybe we need two block to save
file "test".

But the follow is something I can not understand. If the dist is more
than 480000, such as 700000, the block which is filled by file "test"
will be 8.5K.

I change the dist to 7000000 direct, the block which is filled by file
"test" will be 15K. And if it is changed to 70000000, the block will
be 75K.

In my opnion, there only have two string in the file, so although
length of file will increase as I increase the distance moved by
lseek, the ACTUAL block size filled by "test" file will keep to be 8K.
But actually I am wrong. So who can explain it for me ?

Thanks very much!

David Schwartz

2007-06-14, 7:22 pm

On Jun 14, 7:51 am, windstorm <likunarmstr...@gmail.com> wrote:
> If the dist is 4000 or less than 4000, the block which is filled by
> file "test" will be 4K, it's reasonable for the minimal size of block
> is 4K.
>
> If the dist is 5000-480000, the block which is filled by file "test"
> will be 8K, it's reasonable for the position where the second string
> lk be written is out of block 1, so maybe we need two block to save
> file "test".
>
> But the follow is something I can not understand. If the dist is more
> than 480000, such as 700000, the block which is filled by file "test"
> will be 8.5K.
>
> I change the dist to 7000000 direct, the block which is filled by file
> "test" will be 15K. And if it is changed to 70000000, the block will
> be 75K.
>
> In my opnion, there only have two string in the file, so although
> length of file will increase as I increase the distance moved by
> lseek, the ACTUAL block size filled by "test" file will keep to be 8K.
> But actually I am wrong. So who can explain it for me ?
>
> Thanks very much!

It is due to internal implementation details of the file system. Most
likely, for files above a certain size, the file system uses indirect
blocks rather than direct blocks. So there's an extra allocation for
the block that points to the other blocks.

DS

Chris Torek

2007-06-15, 1:21 am

In article <1181832672.463004.112720@j4g2000prf.googlegroups.com>
windstorm <likunarmstrong@gmail.com> wrote:
>This is just test code ...

A good thing, since it is not very careful :-)

>int main( void )
>{
> int fd,size,position;
> char buf[20];
> char lkl[] = "hello,world!";
> fd = creat( "test",0644 );

(You should test the return value from calls, to make sure the
creat() succeeds in this case, and the others below.)

> size = write( fd,lkl,sizeof(lkl) );
> close(fd);
> fd = open( "test",O_RDWR );
> size = read( fd,buf,sizeof(buf) );
> printf( "fd is %s,the length is %d\n\n",buf,size );
> position = lseek( fd,70000000,SEEK_END);
> size = write( fd,lk,sizeof(lkl) );

The middle argument here needs to be lkl (not lk).

> close(fd);
> return 1;
>}

Returning 1 is usually for some kind of failure -- Unix-like
programs should generally return 0 for success.

>... I found that the
>file's size which can be saw by the command "ls -ls" will change
>according to the lseek's second parameter distance.

The "-s" flag prints the value returned as part of the stat() call
in the st_blocks field of a "struct stat" (or equivalent, e.g.,
stat64).

Depending on the structure of the file system, a file may need more
or fewer blocks than is immediately obvious.

The "UFS" file system format uses what are called "direct" and
"indirect" blocks. The first NDADDR (12) blocks are "direct"
blocks, and then there are NIADDR (3) "indirects" (see also
<ufs/ufs/dinode.h> ).

A file that needs only direct blocks occupies one inode data
structure (which uses part of a disk sector and is not counted
separately), and one file-system block for each block that is not
a "hole". The last part of the file may, but need not, end in a
"fragment" -- anywhere from 1/8th to 7/8ths of a block.

With a block size of 8192 bytes (8k), this handles files from
zero bytes up to 98304 (12 * 8192) bytes for UFS. A larger
basic block size gives you larger "direct-only" files, e.g.,
on an 32K/4K file system, you get up to 393216 bytes in a file
before exceeding the "direct-only" size.

Once a file's size exceeds NDADDR * st_blksize bytes, however, any
additional "non-hole" blocks require "indirect" blocks. The first
indirect block consists of one file-system block containing disk-block
numbers (4 bytes each for UFS, 8 for UFS2, so that you get 8192
such blocks with a 32K block on UFS, or 4096 such with a 32K block
on UFS2).

>For example:
>
>If the dist is 4000 or less than 4000, the block which is filled by
>file "test" will be 4K, it's reasonable for the minimal size of block
>is 4K.
>
>If the dist is 5000-480000, the block which is filled by file "test"
>will be 8K, it's reasonable for the position where the second string
>lk be written is out of block 1, so maybe we need two block to save
>file "test".

This should be 393216 on a standard UFS file system with 32K/4K
block/fragment sizes. The file will need one 32K block and one 4K
fragment, giving a "disk occupancy" of 40K. That is, you have:

inode:
db[0] 0x00001230 (or similar) - one 32768-byte block
db[1] 0 (i.e., a "hole")
db[2] 0
...
db[10] 0
db[11] 0x00001238 (or similar) - one 4096-byte fragment
ib[0] 0
ib[1] 0
ib[2] 0

(Perhaps you are not using UFS.)

>But the follow is something I can not understand. If the dist is more
>than 480000, such as 700000, the block which is filled by file "test"
>will be 8.5K.

A file of approximately 700K on UFS on a 32K/4K file system needs
one indirect block. That one indirect block (assuming UFS1) holds
8192 additional potential disk block numbers, which thus maps
another possible 268435456 bytes (8192 * 32K) of file. If only
the first direct block is occupied, you will have:

inode:
db[0] 0x00001234 (or similar) - one 32768-byte block
db[1] 0 (i.e., a "hole")
db[2] 0
...
db[11] 0
ib[0] 0x00001238 (or similar) - one 32768-byte block
ib[1] 0
ib[2] 0

At this point, we need only calculate which indirect block(s) are
occupied. If the byte at 699999 is occupied (i.e., is not a "hole"),
we need to calculate:

699999 - 393216 = 306783

(take the actual file offset and subtract the number of bytes
already handled by earlier indirect and direct blocks). This value
then gives an index into the indirect block after dividing by the
block size. Use integer division; the remainder is the offset
within the final block:

306783 / 32768 = 9
306783 % 32768 = 11871

Hence:

disk block 0x00001238:
[0] 0
[1] 0
...
[8] 0
[9] 0x00001240 (for example)
[10] 0
...
[8191] 0

The "file byte" at offset 699999 is thus in disk block 0x00001240 at
offset 11871.

The file itself occupies three entire disk blocks of 32K each, or
96K.

The second indirect (ib[1]), if it exists (is nonzero), gives block
numbers of blocks that hold single indirects, which in turn gives
block numbers of blocks that hold file data. If a third indirect
exists (ib[2]), it gives block numbers of double indirects, which
give block numbers of single indirects, which give block numbers
for file data.

Any particular block may be just a "hole", as indicated by a disk
block number of 0. A file should never claim blocks beyond its
size given in its inode, though. In other words, one can expect
"holes" for all blocks beyond the file's size.

Again, you may be using something other than UFS. Other file
system formats have other methods of representing occupied and
unoccupied blocks.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

windstorm

2007-06-15, 1:21 pm

On 6 15 , 9 09 , Chris Torek <nos...@torek.net> wrote:
> In article <1181832672.463004.112...@j4g2000prf.googlegroups.com>
>
> windstorm <likunarmstr...@gmail.com> wrote:
>
> A good thing, since it is not very careful :-)
>
>
> (You should test the return value from calls, to make sure the
> creat() succeeds in this case, and the others below.)
>
>
> The middle argument here needs to be lkl (not lk).
>
>
> Returning 1 is usually for some kind of failure -- Unix-like
> programs should generally return 0 for success.
>
>
> The "-s" flag prints the value returned as part of the stat() call
> in the st_blocks field of a "struct stat" (or equivalent, e.g.,
> stat64).
>
> Depending on the structure of the file system, a file may need more
> or fewer blocks than is immediately obvious.
>
> The "UFS" file system format uses what are called "direct" and
> "indirect" blocks. The first NDADDR (12) blocks are "direct"
> blocks, and then there are NIADDR (3) "indirects" (see also
> <ufs/ufs/dinode.h> ).
>
> A file that needs only direct blocks occupies one inode data
> structure (which uses part of a disk sector and is not counted
> separately), and one file-system block for each block that is not
> a "hole". The last part of the file may, but need not, end in a
> "fragment" -- anywhere from 1/8th to 7/8ths of a block.
>
> With a block size of 8192 bytes (8k), this handles files from
> zero bytes up to 98304 (12 * 8192) bytes forUFS. A larger
> basic block size gives you larger "direct-only" files, e.g.,
> on an 32K/4K file system, you get up to 393216 bytes in a file
> before exceeding the "direct-only" size.
>
> Once a file's size exceeds NDADDR * st_blksize bytes, however, any
> additional "non-hole" blocks require "indirect" blocks. The first
> indirect block consists of one file-system block containing disk-block
> numbers (4 bytes each forUFS, 8 for UFS2, so that you get 8192
> such blocks with a 32K block onUFS, or 4096 such with a 32K block
> on UFS2).
>
>
>
>
> This should be 393216 on a standardUFSfile system with 32K/4K
> block/fragment sizes. The file will need one 32K block and one 4K
> fragment, giving a "disk occupancy" of 40K. That is, you have:
>
> inode:
> db[0] 0x00001230 (or similar) - one 32768-byte block
> db[1] 0 (i.e., a "hole")
> db[2] 0
> ...
> db[10] 0
> db[11] 0x00001238 (or similar) - one 4096-byte fragment
> ib[0] 0
> ib[1] 0
> ib[2] 0
>
> (Perhaps you are not usingUFS.)
>
>
> A file of approximately 700K onUFSon a 32K/4K file system needs
> one indirect block. That one indirect block (assuming UFS1) holds
> 8192 additional potential disk block numbers, which thus maps
> another possible 268435456 bytes (8192 * 32K) of file. If only
> the first direct block is occupied, you will have:
>
> inode:
> db[0] 0x00001234 (or similar) - one 32768-byte block
> db[1] 0 (i.e., a "hole")
> db[2] 0
> ...
> db[11] 0
> ib[0] 0x00001238 (or similar) - one 32768-byte block
> ib[1] 0
> ib[2] 0
>
> At this point, we need only calculate which indirect block(s) are
> occupied. If the byte at 699999 is occupied (i.e., is not a "hole"),
> we need to calculate:
>
> 699999 - 393216 =3D 306783
>
> (take the actual file offset and subtract the number of bytes
> already handled by earlier indirect and direct blocks). This value
> then gives an index into the indirect block after dividing by the
> block size. Use integer division; the remainder is the offset
> within the final block:
>
> 306783 / 32768 =3D 9
> 306783 % 32768 =3D 11871
>
> Hence:
>
> disk block 0x00001238:
> [0] 0
> [1] 0
> ...
> [8] 0
> [9] 0x00001240 (for example)
> [10] 0
> ...
> [8191] 0
>
> The "file byte" at offset 699999 is thus in disk block 0x00001240 at
> offset 11871.
>
> The file itself occupies three entire disk blocks of 32K each, or
> 96K.
>
> The second indirect (ib[1]), if it exists (is nonzero), gives block
> numbers of blocks that hold single indirects, which in turn gives
> block numbers of blocks that hold file data. If a third indirect
> exists (ib[2]), it gives block numbers of double indirects, which
> give block numbers of single indirects, which give block numbers
> for file data.
>
> Any particular block may be just a "hole", as indicated by a disk
> block number of 0. A file should never claim blocks beyond its
> size given in its inode, though. In other words, one can expect
> "holes" for all blocks beyond the file's size.
>
> Again, you may be using something other thanUFS. Other file
> system formats have other methods of representing occupied and
> unoccupied blocks.
> --
> In-Real-Life: Chris Torek, Wind River Systems
> Salt Lake City, UT, USA (40=B039.22'N, 111=B050.29'W) +1 801 277 2603
> email: forget about it http://web.torek.net/torek/index.html
> Reading email is like searching for food in the garbage, thanks to spamme=
rs.

very very very good reply! Thanks a lot!

But I am using ReiserFS and maybe it is not identical to UFS, for I
get different outcome when I use the algorithm you said here. So maybe
ReiserFS have other methods of representing occupied and unoccupied
blocks.

Would you please tell me something to refer which i can get from web?

Thanks again!

Chris Torek

2007-06-18, 7:23 am

>On 6 15 , 9 09 , Chris Torek <nos...@torek.net> wrote:
[a description of how UFS represents blocks]

In article <1181910579.764598.281420@i13g2000prf.googlegroups.com>
windstorm <likunarmstrong@gmail.com> wrote:
>very very very good reply! Thanks a lot!
>
>But I am using ReiserFS and maybe it is not identical to UFS ...

Indeed, it is not. ReiserFS uses a variant of B-trees for pretty
much everything. (The details may depend on which version of
ReiserFS is in use. Wikipedia claims it uses B+ trees; others say
B* trees. Hans Reiser apparently calls them "S+ trees".)

>Would you please tell me something to refer which i can get from web?

I do not have this kind of detail, but there are some links
in the Wikipedia entry. Florian Buchholz's paper appears to
have useful detail.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.