thttpd/mmc.c

/* mmc.c - mmap cache
**
** Copyright © 1998,2001 by Jef Poskanzer <jef@acme.com>.
** 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.
**
** THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
*/

#include <sys/types.h>
#include <sys/stat.h>
#include <sys/time.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <syslog.h>

#ifdef HAVE_MMAP
#include <sys/mman.h>
#endif /* HAVE_MMAP */

#include "mmc.h"


/* Defines. */
#ifndef DEFAULT_EXPIRE_AGE
#define DEFAULT_EXPIRE_AGE 600
#endif
#ifndef DESIRED_FREE_COUNT
#define DESIRED_FREE_COUNT 100
#endif
#ifndef DESIRED_MAX_MAPPED_FILES
#define DESIRED_MAX_MAPPED_FILES 2000
#endif
#ifndef INITIAL_HASH_SIZE
#define INITIAL_HASH_SIZE (1 << 10)
#endif

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))


/* The Map struct. */
typedef struct MapStruct {
    ino_t ino;
    dev_t dev;
    off_t size;
    time_t ctime;
    int refcount;
    time_t reftime;
    void* addr;
    unsigned int hash;
    int hash_idx;
    struct MapStruct* next;
    } Map;


/* Globals. */
static Map* maps = (Map*) 0;
static Map* free_maps = (Map*) 0;
static int alloc_count = 0, map_count = 0, free_count = 0;
static Map** hash_table = (Map**) 0;
static int hash_size;
static unsigned int hash_mask;
static time_t expire_age = DEFAULT_EXPIRE_AGE;


/* Forwards. */
static void really_unmap( Map** mm );
static int check_hash_size( void );
static int add_hash( Map* m );
static Map* find_hash( ino_t ino, dev_t dev, off_t size, time_t ctime );
static unsigned int hash( ino_t ino, dev_t dev, off_t size, time_t ctime );


void*
mmc_map( char* filename, struct stat* sbP, struct timeval* nowP )
    {
    time_t now;
    struct stat sb;
    Map* m;
    int fd;

    /* Stat the file, if necessary. */
    if ( sbP != (struct stat*) 0 )
        sb = *sbP;
    else
        {
        if ( stat( filename, &sb ) != 0 )
            {
            syslog( LOG_ERR, "stat - %m" );
            return (void*) 0;
            }
        }

    /* Get the current time, if necessary. */
    if ( nowP != (struct timeval*) 0 )
        now = nowP->tv_sec;
    else
        now = time( (time_t*) 0 );

    /* See if we have it mapped already, via the hash table. */
    if ( check_hash_size() < 0 )
        {
        syslog( LOG_ERR, "check_hash_size() failure" );
        return (void*) 0;
        }
    m = find_hash( sb.st_ino, sb.st_dev, sb.st_size, sb.st_ctime );
    if ( m != (Map*) 0 )
        {
        /* Yep.  Just return the existing map */
        ++m->refcount;
        m->reftime = now;
        return m->addr;
        }

    /* Open the file. */
    fd = open( filename, O_RDONLY );
    if ( fd < 0 )
        {
        syslog( LOG_ERR, "open - %m" );
        return (void*) 0;
        }

    /* Find a free Map entry or make a new one. */
    if ( free_maps != (Map*) 0 )
        {
        m = free_maps;
        free_maps = m->next;
        --free_count;
        }
    else
        {
        m = (Map*) malloc( sizeof(Map) );
        if ( m == (Map*) 0 )
            {
            (void) close( fd );
            syslog( LOG_ERR, "out of memory allocating a Map" );
            return (void*) 0;
            }
        ++alloc_count;
        }

    /* Fill in the Map entry. */
    m->ino = sb.st_ino;
    m->dev = sb.st_dev;
    m->size = sb.st_size;
    m->ctime = sb.st_ctime;
    m->refcount = 1;
    m->reftime = now;

    /* Avoid doing anything for zero-length files; some systems don't like
    ** to mmap them, other systems dislike mallocing zero bytes.
    */
    if ( m->size == 0 )
        m->addr = (void*) 1;    /* arbitrary non-NULL address */
    else
        {
#ifdef HAVE_MMAP
        /* Map the file into memory. */
        m->addr = mmap( 0, m->size, PROT_READ, MAP_SHARED, fd, 0 );
        if ( m->addr == (void*) -1 )
            {
            syslog( LOG_ERR, "mmap - %m" );
            (void) close( fd );
            free( (void*) m );
            --alloc_count;
            return (void*) 0;
            }
#else /* HAVE_MMAP */
        /* Read the file into memory. */
        m->addr = (void*) malloc( m->size );
        if ( m->addr == (void*) 0 )
            {
            syslog( LOG_ERR, "out of memory storing a file" );
            (void) close( fd );
            free( (void*) m );
            --alloc_count;
            return (void*) 0;
            }
        if ( read( fd, m->addr, m->size ) != m->size )
            {
            syslog( LOG_ERR, "read - %m" );
            (void) close( fd );
            free( (void*) m );
            --alloc_count;
            return (void*) 0;
            }
#endif /* HAVE_MMAP */
        }
    (void) close( fd );

    /* Put the Map into the hash table. */
    if ( add_hash( m ) < 0 )
        {
        syslog( LOG_ERR, "add_hash() failure" );
        free( (void*) m );
        --alloc_count;
        return (void*) 0;
        }

    /* Put the Map on the active list. */
    m->next = maps;
    maps = m;
    ++map_count;

    /* And return the address. */
    return m->addr;
    }


void
mmc_unmap( void* addr, struct stat* sbP, struct timeval* nowP )
    {
    Map* m = (Map*) 0;

    /* Find the Map entry for this address.  First try a hash. */
    if ( sbP != (struct stat*) 0 )
        {
        m = find_hash( sbP->st_ino, sbP->st_dev, sbP->st_size, sbP->st_ctime );
        if ( m != (Map*) 0 && m->addr != addr )
            m = (Map*) 0;
        }
    /* If that didn't work, try a full search. */
    if ( m == (Map*) 0 )
        for ( m = maps; m != (Map*) 0; m = m->next )
            if ( m->addr == addr )
                break;
    if ( m == (Map*) 0 )
        syslog( LOG_ERR, "mmc_unmap failed to find entry!" );
    else if ( m->refcount <= 0 )
        syslog( LOG_ERR, "mmc_unmap found zero or negative refcount!" );
    else
        {
        --m->refcount;
        if ( nowP != (struct timeval*) 0 )
            m->reftime = nowP->tv_sec;
        else
            m->reftime = time( (time_t*) 0 );
        }
    }


void
mmc_cleanup( struct timeval* nowP )
    {
    time_t now;
    Map** mm;
    Map* m;

    /* Get the current time, if necessary. */
    if ( nowP != (struct timeval*) 0 )
        now = nowP->tv_sec;
    else
        now = time( (time_t*) 0 );

    /* Really unmap any unreferenced entries older than the age limit. */
    for ( mm = &maps; *mm != (Map*) 0; )
        {
        m = *mm;
        if ( m->refcount == 0 && now - m->reftime >= expire_age )
            really_unmap( mm );
        else
            mm = &(*mm)->next;
        }

    /* If there are still too many (or too few) maps, adjust the age limit. */
    if ( map_count > DESIRED_MAX_MAPPED_FILES )
        expire_age = max( ( expire_age * 2 ) / 3, DEFAULT_EXPIRE_AGE / 10 );
    else if ( map_count < DESIRED_MAX_MAPPED_FILES / 2 )
        expire_age = min( ( expire_age * 5 ) / 4, DEFAULT_EXPIRE_AGE * 3 );

    /* Really free excess blocks on the free list. */
    while ( free_count > DESIRED_FREE_COUNT )
        {
        m = free_maps;
        free_maps = m->next;
        --free_count;
        free( (void*) m );
        --alloc_count;
        }
    }


static void
really_unmap( Map** mm )
    {
    Map* m;

    m = *mm;
    if ( m->size != 0 )
        {
#ifdef HAVE_MMAP
        if ( munmap( m->addr, m->size ) < 0 )
            syslog( LOG_ERR, "munmap - %m" );
#else /* HAVE_MMAP */
        free( (void*) m->addr );
#endif /* HAVE_MMAP */
        }
    /* And move the Map to the free list. */
    *mm = m->next;
    --map_count;
    m->next = free_maps;
    free_maps = m;
    ++free_count;
    /* This will sometimes break hash chains, but that's harmless; the
    ** unmapping code that searches the hash table knows to keep searching.
    */
    hash_table[m->hash_idx] = (Map*) 0;
    }


void
mmc_destroy( void )
    {
    Map* m;

    while ( maps != (Map*) 0 )
        really_unmap( &maps );
    while ( free_maps != (Map*) 0 )
        {
        m = free_maps;
        free_maps = m->next;
        --free_count;
        free( (void*) m );
        --alloc_count;
        }
    }


/* Make sure the hash table is big enough. */
static int
check_hash_size( void )
    {
    int i;
    Map* m;

    /* Are we just starting out? */
    if ( hash_table == (Map**) 0 )
        {
        hash_size = INITIAL_HASH_SIZE;
        hash_mask = hash_size - 1;
        }
    /* Is it at least three times bigger than the number of entries? */
    else if ( hash_size >= map_count * 3 )
        return 0;
    else
        {
        /* No, got to expand. */
        free( (void*) hash_table );
        /* Double the hash size until it's big enough. */
        do
            {
            hash_size = hash_size << 1;
            }
        while ( hash_size < map_count * 6 );
        hash_mask = hash_size - 1;
        }
    /* Make the new table. */
    hash_table = (Map**) malloc( hash_size * sizeof(Map*) );
    if ( hash_table == (Map**) 0 )
        return -1;
    /* Clear it. */
    for ( i = 0; i < hash_size; ++i )
        hash_table[i] = (Map*) 0;
    /* And rehash all entries. */
    for ( m = maps; m != (Map*) 0; m = m->next )
        if ( add_hash( m ) < 0 )
            return -1;
    return 0;
    }


static int
add_hash( Map* m )
    {
    unsigned int h, he, i;

    h = hash( m->ino, m->dev, m->size, m->ctime );
    he = ( h + hash_size - 1 ) & hash_mask;
    for ( i = h; ; i = ( i + 1 ) & hash_mask )
        {
        if ( hash_table[i] == (Map*) 0 )
            {
            hash_table[i] = m;
            m->hash = h;
            m->hash_idx = i;
            return 0;
            }
        if ( i == he )
            break;
        }
    return -1;
    }


static Map*
find_hash( ino_t ino, dev_t dev, off_t size, time_t ctime )
    {
    unsigned int h, he, i;
    Map* m;

    h = hash( ino, dev, size, ctime );
    he = ( h + hash_size - 1 ) & hash_mask;
    for ( i = h; ; i = ( i + 1 ) & hash_mask )
        {
        m = hash_table[i];
        if ( m == (Map*) 0 )
            break;
        if ( m->hash == h && m->ino == ino && m->dev == dev &&
             m->size == size && m->ctime == ctime )
            return m;
        if ( i == he )
            break;
        }
    return (Map*) 0;
    }


static unsigned int
hash( ino_t ino, dev_t dev, off_t size, time_t ctime )
    {
    unsigned int h = 177573;

    h ^= ino;
    h += h << 5;
    h ^= dev;
    h += h << 5;
    h ^= size;
    h += h << 5;
    h ^= ctime;

    return h & hash_mask;
    }


/* Generate debugging statistics syslog message. */
void
mmc_logstats( long secs )
    {
    syslog(
        LOG_NOTICE, "  map cache - %d allocated, %d active, %d free; hash size: %d; expire age: %ld",
        alloc_count, map_count, free_count, hash_size, expire_age );
    if ( map_count + free_count != alloc_count )
        syslog( LOG_ERR, "map counts don't add up!" );
    }
Revision:	1.1
Committed:	Mon Jun 18 21:11:57 2001 UTC (23 years ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	mp_j, dp_j, cp_j, HEAD
Branch point for:	connpatch, dirpatch, mmapppatch
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	/* mmc.c - mmap cache
2			**
3			** Copyright © 1998,2001 by Jef Poskanzer <jef@acme.com>.
4			** All rights reserved.
5			**
6			** Redistribution and use in source and binary forms, with or without
7			** modification, are permitted provided that the following conditions
8			** are met:
9			** 1. Redistributions of source code must retain the above copyright
10			** notice, this list of conditions and the following disclaimer.
11			** 2. Redistributions in binary form must reproduce the above copyright
12			** notice, this list of conditions and the following disclaimer in the
13			** documentation and/or other materials provided with the distribution.
14			**
15			** THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16			** ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17			** IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18			** ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19			** FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20			** DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21			** OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22			** HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23			** LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24			** OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25			** SUCH DAMAGE.
26			*/
27
28			#include <sys/types.h>
29			#include <sys/stat.h>
30			#include <sys/time.h>
31			#include <stdlib.h>
32			#include <unistd.h>
33			#include <fcntl.h>
34			#include <syslog.h>
35
36			#ifdef HAVE_MMAP
37			#include <sys/mman.h>
38			#endif /* HAVE_MMAP */
39
40			#include "mmc.h"
41
42
43			/* Defines. */
44			#ifndef DEFAULT_EXPIRE_AGE
45			#define DEFAULT_EXPIRE_AGE 600
46			#endif
47			#ifndef DESIRED_FREE_COUNT
48			#define DESIRED_FREE_COUNT 100
49			#endif
50			#ifndef DESIRED_MAX_MAPPED_FILES
51			#define DESIRED_MAX_MAPPED_FILES 2000
52			#endif
53			#ifndef INITIAL_HASH_SIZE
54			#define INITIAL_HASH_SIZE (1 << 10)
55			#endif
56
57			#define max(a,b) ((a)>(b)?(a):(b))
58			#define min(a,b) ((a)<(b)?(a):(b))
59
60
61			/* The Map struct. */
62			typedef struct MapStruct {
63			ino_t ino;
64			dev_t dev;
65			off_t size;
66			time_t ctime;
67			int refcount;
68			time_t reftime;
69			void* addr;
70			unsigned int hash;
71			int hash_idx;
72			struct MapStruct* next;
73			} Map;
74
75
76			/* Globals. */
77			static Map* maps = (Map*) 0;
78			static Map* free_maps = (Map*) 0;
79			static int alloc_count = 0, map_count = 0, free_count = 0;
80			static Map hash_table = (Map) 0;
81			static int hash_size;
82			static unsigned int hash_mask;
83			static time_t expire_age = DEFAULT_EXPIRE_AGE;
84
85
86
87			/* Forwards. */
88			static void really_unmap( Map** mm );
89			static int check_hash_size( void );
90			static int add_hash( Map* m );
91			static Map* find_hash( ino_t ino, dev_t dev, off_t size, time_t ctime );
92			static unsigned int hash( ino_t ino, dev_t dev, off_t size, time_t ctime );
93
94
95			void*
96			mmc_map( char* filename, struct stat* sbP, struct timeval* nowP )
97			{
98			time_t now;
99			struct stat sb;
100			Map* m;
101			int fd;
102
103			/* Stat the file, if necessary. */
104			if ( sbP != (struct stat*) 0 )
105			sb = *sbP;
106			else
107			{
108			if ( stat( filename, &sb ) != 0 )
109			{
110			syslog( LOG_ERR, "stat - %m" );
111			return (void*) 0;
112			}
113			}
114
115			/* Get the current time, if necessary. */
116			if ( nowP != (struct timeval*) 0 )
117			now = nowP->tv_sec;
118			else
119			now = time( (time_t*) 0 );
120
121			/* See if we have it mapped already, via the hash table. */
122			if ( check_hash_size() < 0 )
123			{
124			syslog( LOG_ERR, "check_hash_size() failure" );
125			return (void*) 0;
126			}
127			m = find_hash( sb.st_ino, sb.st_dev, sb.st_size, sb.st_ctime );
128			if ( m != (Map*) 0 )
129			{
130			/* Yep. Just return the existing map */
131			++m->refcount;
132			m->reftime = now;
133			return m->addr;
134			}
135
136			/* Open the file. */
137			fd = open( filename, O_RDONLY );
138			if ( fd < 0 )
139			{
140			syslog( LOG_ERR, "open - %m" );
141			return (void*) 0;
142			}
143
144			/* Find a free Map entry or make a new one. */
145			if ( free_maps != (Map*) 0 )
146			{
147			m = free_maps;
148			free_maps = m->next;
149			--free_count;
150			}
151			else
152			{
153			m = (Map*) malloc( sizeof(Map) );
154			if ( m == (Map*) 0 )
155			{
156			(void) close( fd );
157			syslog( LOG_ERR, "out of memory allocating a Map" );
158			return (void*) 0;
159			}
160			++alloc_count;
161			}
162
163			/* Fill in the Map entry. */
164			m->ino = sb.st_ino;
165			m->dev = sb.st_dev;
166			m->size = sb.st_size;
167			m->ctime = sb.st_ctime;
168			m->refcount = 1;
169			m->reftime = now;
170
171			/* Avoid doing anything for zero-length files; some systems don't like
172			** to mmap them, other systems dislike mallocing zero bytes.
173			*/
174			if ( m->size == 0 )
175			m->addr = (void) 1; / arbitrary non-NULL address */
176			else
177			{
178			#ifdef HAVE_MMAP
179			/* Map the file into memory. */
180			m->addr = mmap( 0, m->size, PROT_READ, MAP_SHARED, fd, 0 );
181			if ( m->addr == (void*) -1 )
182			{
183			syslog( LOG_ERR, "mmap - %m" );
184			(void) close( fd );
185			free( (void*) m );
186			--alloc_count;
187			return (void*) 0;
188			}
189			#else /* HAVE_MMAP */
190			/* Read the file into memory. */
191			m->addr = (void*) malloc( m->size );
192			if ( m->addr == (void*) 0 )
193			{
194			syslog( LOG_ERR, "out of memory storing a file" );
195			(void) close( fd );
196			free( (void*) m );
197			--alloc_count;
198			return (void*) 0;
199			}
200			if ( read( fd, m->addr, m->size ) != m->size )
201			{
202			syslog( LOG_ERR, "read - %m" );
203			(void) close( fd );
204			free( (void*) m );
205			--alloc_count;
206			return (void*) 0;
207			}
208			#endif /* HAVE_MMAP */
209			}
210			(void) close( fd );
211
212			/* Put the Map into the hash table. */
213			if ( add_hash( m ) < 0 )
214			{
215			syslog( LOG_ERR, "add_hash() failure" );
216			free( (void*) m );
217			--alloc_count;
218			return (void*) 0;
219			}
220
221			/* Put the Map on the active list. */
222			m->next = maps;
223			maps = m;
224			++map_count;
225
226			/* And return the address. */
227			return m->addr;
228			}
229
230
231			void
232			mmc_unmap( void* addr, struct stat* sbP, struct timeval* nowP )
233			{
234			Map* m = (Map*) 0;
235
236			/* Find the Map entry for this address. First try a hash. */
237			if ( sbP != (struct stat*) 0 )
238			{
239			m = find_hash( sbP->st_ino, sbP->st_dev, sbP->st_size, sbP->st_ctime );
240			if ( m != (Map*) 0 && m->addr != addr )
241			m = (Map*) 0;
242			}
243			/* If that didn't work, try a full search. */
244			if ( m == (Map*) 0 )
245			for ( m = maps; m != (Map*) 0; m = m->next )
246			if ( m->addr == addr )
247			break;
248			if ( m == (Map*) 0 )
249			syslog( LOG_ERR, "mmc_unmap failed to find entry!" );
250			else if ( m->refcount <= 0 )
251			syslog( LOG_ERR, "mmc_unmap found zero or negative refcount!" );
252			else
253			{
254			--m->refcount;
255			if ( nowP != (struct timeval*) 0 )
256			m->reftime = nowP->tv_sec;
257			else
258			m->reftime = time( (time_t*) 0 );
259			}
260			}
261
262
263			void
264			mmc_cleanup( struct timeval* nowP )
265			{
266			time_t now;
267			Map** mm;
268			Map* m;
269
270			/* Get the current time, if necessary. */
271			if ( nowP != (struct timeval*) 0 )
272			now = nowP->tv_sec;
273			else
274			now = time( (time_t*) 0 );
275
276			/* Really unmap any unreferenced entries older than the age limit. */
277			for ( mm = &maps; mm != (Map) 0; )
278			{
279			m = *mm;
280			if ( m->refcount == 0 && now - m->reftime >= expire_age )
281			really_unmap( mm );
282			else
283			mm = &(*mm)->next;
284			}
285
286			/* If there are still too many (or too few) maps, adjust the age limit. */
287			if ( map_count > DESIRED_MAX_MAPPED_FILES )
288			expire_age = max( ( expire_age * 2 ) / 3, DEFAULT_EXPIRE_AGE / 10 );
289			else if ( map_count < DESIRED_MAX_MAPPED_FILES / 2 )
290			expire_age = min( ( expire_age * 5 ) / 4, DEFAULT_EXPIRE_AGE * 3 );
291
292			/* Really free excess blocks on the free list. */
293			while ( free_count > DESIRED_FREE_COUNT )
294			{
295			m = free_maps;
296			free_maps = m->next;
297			--free_count;
298			free( (void*) m );
299			--alloc_count;
300			}
301			}
302
303
304			static void
305			really_unmap( Map** mm )
306			{
307			Map* m;
308
309			m = *mm;
310			if ( m->size != 0 )
311			{
312			#ifdef HAVE_MMAP
313			if ( munmap( m->addr, m->size ) < 0 )
314			syslog( LOG_ERR, "munmap - %m" );
315			#else /* HAVE_MMAP */
316			free( (void*) m->addr );
317			#endif /* HAVE_MMAP */
318			}
319			/* And move the Map to the free list. */
320			*mm = m->next;
321			--map_count;
322			m->next = free_maps;
323			free_maps = m;
324			++free_count;
325			/* This will sometimes break hash chains, but that's harmless; the
326			** unmapping code that searches the hash table knows to keep searching.
327			*/
328			hash_table[m->hash_idx] = (Map*) 0;
329			}
330
331
332			void
333			mmc_destroy( void )
334			{
335			Map* m;
336
337			while ( maps != (Map*) 0 )
338			really_unmap( &maps );
339			while ( free_maps != (Map*) 0 )
340			{
341			m = free_maps;
342			free_maps = m->next;
343			--free_count;
344			free( (void*) m );
345			--alloc_count;
346			}
347			}
348
349
350			/* Make sure the hash table is big enough. */
351			static int
352			check_hash_size( void )
353			{
354			int i;
355			Map* m;
356
357			/* Are we just starting out? */
358			if ( hash_table == (Map**) 0 )
359			{
360			hash_size = INITIAL_HASH_SIZE;
361			hash_mask = hash_size - 1;
362			}
363			/* Is it at least three times bigger than the number of entries? */
364			else if ( hash_size >= map_count * 3 )
365			return 0;
366			else
367			{
368			/* No, got to expand. */
369			free( (void*) hash_table );
370			/* Double the hash size until it's big enough. */
371			do
372			{
373			hash_size = hash_size << 1;
374			}
375			while ( hash_size < map_count * 6 );
376			hash_mask = hash_size - 1;
377			}
378			/* Make the new table. */
379			hash_table = (Map*) malloc( hash_size sizeof(Map*) );
380			if ( hash_table == (Map**) 0 )
381			return -1;
382			/* Clear it. */
383			for ( i = 0; i < hash_size; ++i )
384			hash_table[i] = (Map*) 0;
385			/* And rehash all entries. */
386			for ( m = maps; m != (Map*) 0; m = m->next )
387			if ( add_hash( m ) < 0 )
388			return -1;
389			return 0;
390			}
391
392
393			static int
394			add_hash( Map* m )
395			{
396			unsigned int h, he, i;
397
398			h = hash( m->ino, m->dev, m->size, m->ctime );
399			he = ( h + hash_size - 1 ) & hash_mask;
400			for ( i = h; ; i = ( i + 1 ) & hash_mask )
401			{
402			if ( hash_table[i] == (Map*) 0 )
403			{
404			hash_table[i] = m;
405			m->hash = h;
406			m->hash_idx = i;
407			return 0;
408			}
409			if ( i == he )
410			break;
411			}
412			return -1;
413			}
414
415
416			static Map*
417			find_hash( ino_t ino, dev_t dev, off_t size, time_t ctime )
418			{
419			unsigned int h, he, i;
420			Map* m;
421
422			h = hash( ino, dev, size, ctime );
423			he = ( h + hash_size - 1 ) & hash_mask;
424			for ( i = h; ; i = ( i + 1 ) & hash_mask )
425			{
426			m = hash_table[i];
427			if ( m == (Map*) 0 )
428			break;
429			if ( m->hash == h && m->ino == ino && m->dev == dev &&
430			m->size == size && m->ctime == ctime )
431			return m;
432			if ( i == he )
433			break;
434			}
435			return (Map*) 0;
436			}
437
438
439			static unsigned int
440			hash( ino_t ino, dev_t dev, off_t size, time_t ctime )
441			{
442			unsigned int h = 177573;
443
444			h ^= ino;
445			h += h << 5;
446			h ^= dev;
447			h += h << 5;
448			h ^= size;
449			h += h << 5;
450			h ^= ctime;
451
452			return h & hash_mask;
453			}
454
455
456			/* Generate debugging statistics syslog message. */
457			void
458			mmc_logstats( long secs )
459			{
460			syslog(
461			LOG_NOTICE, " map cache - %d allocated, %d active, %d free; hash size: %d; expire age: %ld",
462			alloc_count, map_count, free_count, hash_size, expire_age );
463			if ( map_count + free_count != alloc_count )
464			syslog( LOG_ERR, "map counts don't add up!" );
465			}