chapter8.html

c语言编程-c语言作者的书。英文原版。非常好。

number and name are placed in a <tt>static</tt> structure and a pointer to that
is returned to the user. Each call overwrites the information from the
previous one.
<pre>
   #include &lt;sys/dir.h&gt;   /* local directory structure */

   /* readdir:  read directory entries in sequence */
   Dirent *readdir(DIR *dp)
   {
       struct direct dirbuf;  /* local directory structure */
       static Dirent  d;      /* return: portable structure */

       while (read(dp-&gt;fd, (char *) &dirbuf, sizeof(dirbuf))
                       == sizeof(dirbuf)) {
           if (dirbuf.d_ino == 0) /* slot not in use */
               continue;
           d.ino = dirbuf.d_ino;
           strncpy(d.name, dirbuf.d_name, DIRSIZ);
           d.name[DIRSIZ] = '\0';  /* ensure termination */
           return &d;
       }
       return NULL;
   }
</pre>
Although the <tt>fsize</tt> program is rather specialized, it does illustrate a
couple of important ideas. First, many programs are not ``system programs'';
they merely use information that is maintained by the operating system. For
such programs, it is crucial that the representation of the information
appear only in standard headers, and that programs include those headers
instead of embedding the declarations in themselves. The second observation
is that with care it is possible to create an interface to system-dependent
objects that is itself relatively system-independent. The functions of the
standard library are good examples.
<p>
<strong>Exercise 8-5.</strong> Modify the <tt>fsize</tt> program to print the
other information contained in the inode entry.

<h2><a name="s8.7">8.7 Example - A Storage Allocator</a></h2>
In <a href="chapter5.html">Chapter 5</a>, we presented a vary limited stack-oriented
storage allocator. The version that we will now write is unrestricted. Calls
to <tt>malloc</tt> and <tt>free</tt> may occur in any order; <tt>malloc</tt> calls
upon the operating system to obtain more memory as necessary. These routines
illustrate some of the considerations involved in writing machine-dependent
code in a relatively machine-independent way, and also show a real-life
application of structures, unions and <tt>typedef</tt>.
<p>
Rather than allocating from a compiled-in fixed-size array, <tt>malloc</tt> will
request space from the operating system as needed. Since other activities in
the program may also request space without calling this allocator, the space
that <tt>malloc</tt> manages may not be contiguous. Thus its free storage is kept
as a list of free blocks. Each block contains a size, a pointer to the next
block, and the space itself. The blocks are kept in order of increasing storage
address, and the last block (highest address) points to the first.
<p align="center">
<img src="pic81.gif">
<p>
When a request is made, the free list is scanned until a big-enough block is
found. This algorithm is called ``first fit,'' by contrast with ``best fit,''
which looks for the smallest block that will satisfy the request. If the block
is exactly the size requested it is unlinked from the list and returned to the
user. If the block is too big, it is split, and the proper amount is returned
to the user while the residue remains on the free list. If no big-enough block
is found, another large chunk is obtained by the operating system and linked
into the free list.
<p>
Freeing also causes a search of the free list, to find the proper place to
insert the block being freed. If the block being freed is adjacent to a free
block on either side, it is coalesced with it into a single bigger block, so
storage does not become too fragmented. Determining the adjacency is easy
because the free list is maintained in order of decreasing address.
<p>
One problem, which we alluded to in <a href="chapter5.html">Chapter 5</a>, is to ensure
that the storage returned by <tt>malloc</tt> is aligned properly for the objects
that will be stored in it. Although machines vary, for each machine there is
a most restrictive type: if the most restrictive type can be stored at a
particular address, all other types may be also. On some machines, the most
restrictive type is a <tt>double</tt>; on others, <tt>int</tt> or <tt>long</tt>
suffices.
<p>
A free block contains a pointer to the next block in the chain, a record of
the size of the block, and then the free space itself; the control information
at the beginning is called the ``header.'' To simplify alignment, all blocks
are multiples of the header size, and the header is aligned properly. This is
achieved by a union that contains the desired header structure and an instance
of the most restrictive alignment type, which we have arbitrarily made a
<tt>long</tt>:
<pre>
   typedef long Align;    /* for alignment to long boundary */

   union header {         /* block header */
       struct {
           union header *ptr; /* next block if on free list */
           unsigned size;     /* size of this block */
       } s;
       Align x;           /* force alignment of blocks */
   };

   typedef union header Header;
</pre>
The <tt>Align</tt> field is never used; it just forces each header to be aligned
on a worst-case boundary.
<p>
In <tt>malloc</tt>, the requested size in characters is rounded up to the
proper number of header-sized units; the block that will be allocated
contains one more unit, for the header itself, and this is the value recorded
in the <tt>size</tt> field of the header. The pointer returned by
<tt>malloc</tt> points at the free space, not at the header itself. The user
can do anything with the space requested, but if anything is written outside
of the allocated space the list is likely to be scrambled.
<p align="center">
<img src="pic82.gif">
<p>
The size field is necessary because the blocks controlled by <tt>malloc</tt> need
not be contiguous - it is not possible to compute sizes by pointer arithmetic.
<p>
The variable <tt>base</tt> is used to get started. If <tt>freep</tt> is
<tt>NULL</tt>, as it is at the first call of <tt>malloc</tt>, then a
degenerate free list is created; it contains one block of size zero, and
points to itself. In any case, the free list is then searched. The search for
a free block of adequate size begins at the point (<tt>freep</tt>) where the
last block was found; this strategy helps keep the list homogeneous. If a
too-big block is found, the tail end is returned to the user; in this way the
header of the original needs only to have its size adjusted. In all cases,
the pointer returned to the user points to the free space within the block,
which begins one unit beyond the header.
<pre>
   static Header base;       /* empty list to get started */
   static Header *freep = NULL;     /* start of free list */

   /* malloc:  general-purpose storage allocator */
   void *malloc(unsigned nbytes)
   {
       Header *p, *prevp;
       Header *moreroce(unsigned);
       unsigned nunits;

       nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
       if ((prevp = freep) == NULL) {   /* no free list yet */ 
           base.s.ptr = freeptr = prevptr = &base;
           base.s.size = 0;
       }
       for (p = prevp-&gt;s.ptr; ; prevp = p, p = p-&gt;s.ptr) {
           if (p-&gt;s.size &gt;= nunits) {  /* big enough */
               if (p-&gt;s.size == nunits)  /* exactly */
                   prevp-&gt;s.ptr = p-&gt;s.ptr;
               else {              /* allocate tail end */
                   p-&gt;s.size -= nunits;
                   p += p-&gt;s.size;
                   p-&gt;s.size = nunits;
               }
               freep = prevp;
               return (void *)(p+1);
           }
           if (p == freep)  /* wrapped around free list */
               if ((p = morecore(nunits)) == NULL)
                   return NULL;    /* none left */
       }
   }
</pre>
The function <tt>morecore</tt> obtains storage from the operating system. The
details of how it does this vary from system to system. Since asking the
system for memory is a comparatively expensive operation. we don't want to do
that on every call to <tt>malloc</tt>, so <tt>morecore</tt> requests al least
<tt>NALLOC</tt> units; this larger block will be chopped up as needed. After setting
the size field, <tt>morecore</tt> inserts the additional memory into the arena by
calling <tt>free</tt>.
<p>
The UNIX system call <tt>sbrk(n)</tt> returns a pointer to <tt>n</tt> more
bytes of storage. <tt>sbrk</tt> returns <tt>-1</tt> if there was no space,
even though <tt>NULL</tt> could have been a better design. The <tt>-1</tt>
must be cast to <tt>char *</tt> so it can be compared with the return value.
Again, casts make the function relatively immune to the details of pointer
representation on different machines. There is still one assumption, however,
that pointers to different blocks returned by <tt>sbrk</tt> can be
meaningfully compared. This is not guaranteed by the standard, which permits
pointer comparisons only within an array. Thus this version of
<tt>malloc</tt> is portable only among machines for which general pointer
comparison is meaningful.
<pre>
   #define NALLOC  1024   /* minimum #units to request */

   /* morecore:  ask system for more memory */
   static Header *morecore(unsigned nu)
   {
       char *cp, *sbrk(int);
       Header *up;

       if (nu &lt; NALLOC)
           nu = NALLOC;
       cp = sbrk(nu * sizeof(Header));
       if (cp == (char *) -1)   /* no space at all */
           return NULL;
       up = (Header *) cp;
       up-&gt;s.size = nu;
       free((void *)(up+1));
       return freep;
   }
</pre>
<tt>free</tt> itself is the last thing. It scans the free list, starting at
<tt>freep</tt>, looking for the place to insert the free block. This is
either between two existing blocks or at the end of the list. In any case, if
the block being freed is adjacent to either neighbor, the adjacent blocks are
combined. The only troubles are keeping the pointers pointing to the right
things and the sizes correct.
<pre>
   /* free:  put block ap in free list */
   void free(void *ap)
   {
       Header *bp, *p;

       bp = (Header *)ap - 1;    /* point to  block header */
       for (p = freep; !(bp &gt; p && bp &lt; p-&gt;s.ptr); p = p-&gt;s.ptr)
            if (p &gt;= p-&gt;s.ptr && (bp &gt; p || bp &lt; p-&gt;s.ptr))
                break;  /* freed block at start or end of arena */

       if (bp + bp-&gt;size == p-&gt;s.ptr) {    /* join to upper nbr */
           bp-&gt;s.size += p-&gt;s.ptr-&gt;s.size;
           bp-&gt;s.ptr = p-&gt;s.ptr-&gt;s.ptr;
       } else
           bp-&gt;s.ptr = p-&gt;s.ptr;
       if (p + p-&gt;size == bp) {            /* join to lower nbr */
           p-&gt;s.size += bp-&gt;s.size;
           p-&gt;s.ptr = bp-&gt;s.ptr;
       } else
           p-&gt;s.ptr = bp;
       freep = p;
   }
</pre>
Although storage allocation is intrinsically machine-dependent, the code above
illustrates how the machine dependencies can be controlled and confined to a
very small part of the program. The use of <tt>typedef</tt> and <tt>union</tt>
handles alignment (given that <tt>sbrk</tt> supplies an appropriate pointer).
Casts arrange that pointer conversions are made explicit, and even cope with a
badly-designed system interface. Even though the details here are related to
storage allocation, the general approach is applicable to other situations as
well.
<p>
<strong>Exercise 8-6.</strong> The standard library function
<tt>calloc(n,size)</tt> returns a pointer to <tt>n</tt> objects of size
<tt>size</tt>, with the storage initialized to zero. Write <tt>calloc</tt>,
by calling <tt>malloc</tt> or by modifying it.
<p>
<strong>Exercise 8-7.</strong> <tt>malloc</tt> accepts a size request without
checking its plausibility; <tt>free</tt> believes that the block it is asked
to free contains a valid size field. Improve these routines so they make more
pains with error checking.
<p>
<strong>Exercise 8-8.</strong> Write a routine <tt>bfree(p,n)</tt> that will
free any arbitrary block <tt>p</tt> of <tt>n</tt> characters into the free
list maintained by <tt>malloc</tt> and <tt>free</tt>. By using
<tt>bfree</tt>, a user can add a static or external array to the free list at
any time.
<p>
<hr>
<p align="center">
<a href="chapter7.html">Back to Chapter 7</a>&nbsp;--&nbsp;
<a href="kandr.html">Index</a>&nbsp;--&nbsp;
<a href="appa.html">Appendix A</a>
<p>
<hr>
</body>
</html>