4.t

早期freebsd实现

.\" Copyright (c) 1985 The Regents of the University of California.
.\" All rights reserved.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\" 3. All advertising materials mentioning features or use of this software
.\"    must display the following acknowledgement:
.\"	This product includes software developed by the University of
.\"	California, Berkeley and its contributors.
.\" 4. Neither the name of the University nor the names of its contributors
.\"    may be used to endorse or promote products derived from this software
.\"    without specific prior written permission.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" SUCH DAMAGE.
.\"
.\"	@(#)4.t	5.1 (Berkeley) 4/17/91
.\"
.ds RH Performance Improvements
.NH
Performance Improvements
.PP
This section outlines the changes made to the system 
since the 4.2BSD distribution.
The changes reported here were made in response
to the problems described in Section 3.
The improvements fall into two major classes;
changes to the kernel that are described in this section,
and changes to the system libraries and utilities that are
described in the following section.
.NH 2
Performance Improvements in the Kernel
.PP
Our goal has been to optimize system performance
for our general timesharing environment.
Since most sites running 4.2BSD have been forced to take
advantage of declining
memory costs rather than replace their existing machines with
ones that are more powerful, we have
chosen to optimize running time at the expense of memory.
This tradeoff may need to be reconsidered for personal workstations
that have smaller memories and higher latency disks.
Decreases in the running time of the system may be unnoticeable
because of higher paging rates incurred by a larger kernel.
Where possible, we have allowed the size of caches to be controlled
so that systems with limited memory may reduce them as appropriate.
.NH 3
Name Cacheing
.PP
Our initial profiling studies showed that more than one quarter
of the time in the system was spent in the
pathname translation routine, \fInamei\fP,
translating path names to inodes\u\s-21\s0\d\**.
.FS
\** \u\s-21\s0\d Inode is an abbreviation for ``Index node''.
Each file on the system is described by an inode;
the inode maintains access permissions, and an array of pointers to
the disk blocks that hold the data associated with the file.
.FE
An inspection of \fInamei\fP shows that
it consists of two nested loops.
The outer loop is traversed once per pathname component.
The inner loop performs a linear search through a directory looking
for a particular pathname component.
.PP
Our first idea was to reduce the number of iterations
around the inner loop of \fInamei\fP by observing that many programs 
step through a directory performing an operation on each entry in turn.
To improve performance for processes doing directory scans,
the system keeps track of the directory offset of the last component of the
most recently translated path name for each process.
If the next name the process requests is in the same directory,
the search is started from the offset that the previous name was found
(instead of from the beginning of the directory).
Changing directories invalidates the cache, as
does modifying the directory.
For programs that step sequentially through a directory with
.EQ
delim $$
.EN
$N$ files, search time decreases from $O ( N sup 2 )$ to $O(N)$.
.EQ
delim off
.EN
.PP
The cost of the cache is about 20 lines of code
(about 0.2 kilobytes) 
and 16 bytes per process, with the cached data
stored in a process's \fIuser\fP vector.
.PP
As a quick benchmark to verify the maximum effectiveness of the
cache we ran ``ls \-l''
on a directory containing 600 files.
Before the per-process cache this command
used 22.3 seconds of system time.
After adding the cache the program used the same amount
of user time, but the system time dropped to 3.3 seconds.
.PP
This change prompted our rerunning a profiled system
on a machine containing the new \fInamei\fP.
The results showed that the time in \fInamei\fP
dropped by only 2.6 ms/call and
still accounted for 36% of the system call time,
18% of the kernel, or about 10% of all the machine cycles.
This amounted to a drop in system time from 57% to about 55%.
The results are shown in Table 9.
.KF
.DS L
.TS
center box;
l r r.
part	time	% of kernel
_
self	11.0 ms/call	9.2%
child	10.6 ms/call	8.9%
_
total	21.6 ms/call	18.1%
.TE
.ce
Table 9. Call times for \fInamei\fP with per-process cache.
.DE
.KE
.PP
The small performance improvement
was caused by a low cache hit ratio.
Although the cache was 90% effective when hit,
it was only usable on about 25% of the names being translated.
An additional reason for the small improvement was that
although the amount of time spent in \fInamei\fP itself
decreased substantially,
more time was spent in the routines that it called
since each directory had to be accessed twice;
once to search from the middle to the end,
and once to search from the beginning to the middle.
.PP
Frequent requests for a small set of names are best handled
with a cache of recent name translations\**.
.FS
\** The cache is keyed on a name and the
inode and device number of the directory that contains it.
Associated with each entry is a pointer to the corresponding
entry in the inode table.
.FE
This has the effect of eliminating the inner loop of \fInamei\fP.
For each path name component,
\fInamei\fP first looks in its cache of recent translations
for the needed name.
If it exists, the directory search can be completely eliminated.
.PP
The system already maintained a cache of recently accessed inodes, 
so the initial name cache
maintained a simple name-inode association that was used to
check each component of a path name during name translations.
We considered implementing the cache by tagging each inode
with its most recently translated name,
but eventually decided to have a separate data structure that
kept names with pointers to the inode table.
Tagging inodes has two drawbacks;
many inodes such as those associated with login ports remain in
the inode table for a long period of time, but are never looked 
up by name.
Other inodes, such as those describing directories are looked up
frequently by many different names (\fIe.g.\fP ``..'').
By keeping a separate table of names, the cache can
truly reflect the most recently used names.
An added benefit is that the table can be sized independently
of the inode table, so that machines with small amounts of memory
can reduce the size of the cache (or even eliminate it)
without modifying the inode table structure.
.PP
Another issue to be considered is how the name cache should 
hold references to the inode table.
Normally processes hold ``hard references'' by incrementing the
reference count in the inode they reference.
Since the system reuses only inodes with zero reference counts,
a hard reference insures that the inode pointer will remain valid.
However, if the name cache holds hard references,
it is limited to some fraction of the size of the inode table,
since some inodes must be left free for new files.
It also makes it impossible for other parts of the kernel
to verify sole use of a device or file.
These reasons made it impractical to use hard references
without affecting the behavior of the inode cacheing scheme.
Thus, we chose instead to keep ``soft references'' protected
by a \fIcapability\fP \- a 32-bit number
guaranteed to be unique\u\s-22\s0\d \**.
.FS
\** \u\s-22\s0\d When all the numbers have been exhausted, all outstanding
capabilities are purged and numbering starts over from scratch.
Purging is possible as all capabilities are easily found in kernel memory.
.FE
When an entry is made in the name cache,
the capability of its inode is copied to the name cache entry.
When an inode is reused it is issued a new capability.
When a name cache hit occurs,
the capability of the name cache entry is compared
with the capability of the inode that it references.
If the capabilities do not match, the name cache entry is invalid.
Since the name cache holds only soft references,
it may be sized independent of the size of the inode table.
A final benefit of using capabilities is that all
cached names for an inode may be invalidated without
searching through the entire cache;
instead all you need to do is assign a new capability to the inode.
.PP
The cost of the name cache is about 200 lines of code
(about 1.2 kilobytes) 
and 48 bytes per cache entry.
Depending on the size of the system,
about 200 to 1000 entries will normally be configured,
using 10-50 kilobytes of physical memory.
The name cache is resident in memory at all times.
.PP
After adding the system wide name cache we reran ``ls \-l''
on the same directory.
The user time remained the same,
however the system time rose slightly to 3.7 seconds.
This was not surprising as \fInamei\fP
now had to maintain the cache,
but was never able to make any use of it.
.PP
Another profiled system was created and measurements
were collected over a 17 hour period.  These measurements
showed a 13 ms/call decrease in \fInamei\fP, with
\fInamei\fP accounting for only 26% of the system call time,
13% of the time in the kernel,
or about 7% of all the machine cycles.
System time dropped from 55% to about 49%.
The results are shown in Table 10.
.KF
.DS L
.TS
center box;
l r r.
part	time	% of kernel
_
self	4.2 ms/call	6.2%
child	4.4 ms/call	6.6%
_
total	8.6 ms/call	12.8%
.TE
.ce
Table 10.  Call times for \fInamei\fP with both caches.
.DE