acache.c

非常好的dns解析软件

/*
 * Copyright (C) 2004-2006  Internet Systems Consortium, Inc. ("ISC")
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */

/* $Id: acache.c,v 1.3.2.16 2006/07/19 00:34:56 marka Exp $ */

#include <config.h>

#include <isc/atomic.h>
#include <isc/event.h>
#include <isc/hash.h>
#include <isc/magic.h>
#include <isc/mem.h>
#include <isc/mutex.h>
#include <isc/random.h>
#include <isc/refcount.h>
#include <isc/rwlock.h>
#include <isc/task.h>
#include <isc/time.h>
#include <isc/timer.h>

#include <dns/acache.h>
#include <dns/db.h>
#include <dns/events.h>
#include <dns/log.h>
#include <dns/message.h>
#include <dns/name.h>
#include <dns/rdataset.h>
#include <dns/result.h>
#include <dns/zone.h>

#define ACACHE_MAGIC			ISC_MAGIC('A', 'C', 'H', 'E')
#define DNS_ACACHE_VALID(acache)	ISC_MAGIC_VALID(acache, ACACHE_MAGIC)

#define ACACHEENTRY_MAGIC		ISC_MAGIC('A', 'C', 'E', 'T')
#define DNS_ACACHEENTRY_VALID(entry)	ISC_MAGIC_VALID(entry, ACACHEENTRY_MAGIC)

#define DBBUCKETS	67

#if 0
#define ATRACE(m)       isc_log_write(dns_lctx, \
				      DNS_LOGCATEGORY_DATABASE, \
				      DNS_LOGMODULE_ACACHE, \
				      ISC_LOG_DEBUG(3), \
				      "acache %p: %s", acache, (m))
#define AATRACE(a,m)    isc_log_write(dns_lctx, \
				      DNS_LOGCATEGORY_DATABASE, \
				      DNS_LOGMODULE_ACACHE, \
				      ISC_LOG_DEBUG(3), \
				      "acache %p: %s", (a), (m))
#else
#define ATRACE(m)
#define AATRACE(a, m)
#endif

/*
 * The following variables control incremental cleaning.
 * MINSIZE is how many bytes is the floor for dns_acache_setcachesize().
 * CLEANERINCREMENT is how many entries are examined in one pass.
 * (XXX simply derived from definitions in cache.c  There may be better
 *  constants here.)
 */
#define DNS_ACACHE_MINSIZE 		2097152	/* Bytes.  2097152 = 2 MB */
#define DNS_ACACHE_CLEANERINCREMENT	1000	/* Number of entries. */

#define DEFAULT_ACACHE_ENTRY_LOCK_COUNT	1009	/*%< Should be prime. */

#if defined(ISC_RWLOCK_USEATOMIC) && defined(ISC_PLATFORM_HAVEATOMICSTORE)
#define ACACHE_USE_RWLOCK 1
#endif

#ifdef ACACHE_USE_RWLOCK
#define ACACHE_INITLOCK(l)	isc_rwlock_init((l), 0, 0)
#define ACACHE_DESTROYLOCK(l)	isc_rwlock_destroy(l)
#define ACACHE_LOCK(l, t)	RWLOCK((l), (t))
#define ACACHE_UNLOCK(l, t)	RWUNLOCK((l), (t))

#define acache_storetime(entry, t) \
	(isc_atomic_store((isc_int32_t *)&(entry)->lastused, (t)))
#else
#define ACACHE_INITLOCK(l)	isc_mutex_init(l)
#define ACACHE_DESTROYLOCK(l)	DESTROYLOCK(l)
#define ACACHE_LOCK(l, t)	LOCK(l)
#define ACACHE_UNLOCK(l, t)	UNLOCK(l)

#define acache_storetime(entry, t) ((entry)->lastused = (t))
#endif

/* Locked by acache lock */
typedef struct dbentry {
	ISC_LINK(struct dbentry)	link;

	dns_db_t			*db;
	ISC_LIST(dns_acacheentry_t)	originlist;
	ISC_LIST(dns_acacheentry_t)	referlist;
} dbentry_t;

typedef ISC_LIST(dbentry_t) dbentrylist_t;

typedef struct acache_cleaner acache_cleaner_t;

typedef enum {
	cleaner_s_idle,	/* Waiting for cleaning-interval to expire. */
	cleaner_s_busy,	/* Currently cleaning. */
	cleaner_s_done  /* Freed enough memory after being overmem. */
} cleaner_state_t;

/*
 * Convenience macros for comprehensive assertion checking.
 */
#define CLEANER_IDLE(c) ((c)->state == cleaner_s_idle && \
			 (c)->resched_event != NULL)
#define CLEANER_BUSY(c) ((c)->state == cleaner_s_busy && \
			 (c)->resched_event == NULL)

struct acache_cleaner {
	isc_mutex_t		lock;
	/*
	 * Locks overmem_event, overmem.  (See cache.c)
	 */

	dns_acache_t		*acache;
	unsigned int		cleaning_interval; /* The cleaning-interval
						      from named.conf,
						      in seconds. */

	isc_stdtime_t		last_cleanup_time; /* The time when the last
      						      cleanup task completed */

	isc_timer_t 		*cleaning_timer;
	isc_event_t		*resched_event;	/* Sent by cleaner task to
						   itself to reschedule */
	isc_event_t		*overmem_event;

	dns_acacheentry_t	*current_entry;	/* The bookmark entry to
						   restart the cleaning.
						   Locked by acache lock. */
	int 		 	increment;	/* Number of entries to
						   clean in one increment */

	unsigned long		ncleaned;	/* Number of entries cleaned
						   up (for logging purposes) */
	cleaner_state_t  	state;		/* Idle/Busy/Done. */
	isc_boolean_t	 	overmem;	/* The acache is in an overmem
						   state. */
};

struct dns_acachestats {
	unsigned int			hits;
	unsigned int			queries;
	unsigned int			misses;
	unsigned int			adds;
	unsigned int			deleted;
	unsigned int			cleaned;
	unsigned int			cleaner_runs;
	unsigned int			overmem;
	unsigned int			overmem_nocreates;
	unsigned int			nomem;
};

/*
 * The actual acache object.
 */

struct dns_acache {
	unsigned int			magic;

	isc_mem_t			*mctx;
	isc_refcount_t			refs;

#ifdef ACACHE_USE_RWLOCK
	isc_rwlock_t 			*entrylocks;
#else
	isc_mutex_t 			*entrylocks;
#endif

	isc_mutex_t			lock;

	int				live_cleaners;
	acache_cleaner_t		cleaner;
	ISC_LIST(dns_acacheentry_t)	entries;
	unsigned int			dbentries;
	dbentrylist_t			dbbucket[DBBUCKETS];

	isc_boolean_t			shutting_down;

	isc_task_t 			*task;
	isc_event_t			cevent;
	isc_boolean_t			cevent_sent;

	dns_acachestats_t		stats;
};

struct dns_acacheentry {
	unsigned int 		magic;

	unsigned int		locknum;
	isc_refcount_t 		references;

	dns_acache_t 		*acache;

	/* Data for Management of cache entries */
	ISC_LINK(dns_acacheentry_t) link;
	ISC_LINK(dns_acacheentry_t) olink;
	ISC_LINK(dns_acacheentry_t) rlink;

	dns_db_t 		*origdb; /* reference to the DB
					    holding this entry */

	/* Cache data */
	dns_zone_t 		*zone;		/* zone this entry
						   belongs to */
	dns_db_t		*db;   		/* DB this entry belongs to */
	dns_dbversion_t		*version;	/* the version of the DB */
	dns_dbnode_t 		*node;		/* node this entry
						   belongs to */
	dns_name_t 		*foundname;	/* corresponding DNS name
						   and rdataset */

	/* Callback function and its argument */
	void 			(*callback)(dns_acacheentry_t *, void **);
	void 			*cbarg;

	/* Timestamp of the last time this entry is referred to */
	isc_stdtime32_t		lastused;
};

/*
 *	Internal functions (and prototypes).
 */
static inline isc_boolean_t check_noentry(dns_acache_t *acache);
static void destroy(dns_acache_t *acache);
static void shutdown_entries(dns_acache_t *acache);
static void shutdown_buckets(dns_acache_t *acache);
static void destroy_entry(dns_acacheentry_t *ent);
static inline void unlink_dbentries(dns_acache_t *acache,
				    dns_acacheentry_t *ent);
static inline isc_result_t finddbent(dns_acache_t *acache,
				     dns_db_t *db, dbentry_t **dbentryp);
static inline void clear_entry(dns_acache_t *acache, dns_acacheentry_t *entry);
static isc_result_t acache_cleaner_init(dns_acache_t *acache,
					isc_timermgr_t *timermgr,
					acache_cleaner_t *cleaner);
static void acache_cleaning_timer_action(isc_task_t *task, isc_event_t *event);
static void acache_incremental_cleaning_action(isc_task_t *task,
					       isc_event_t *event);
static void acache_overmem_cleaning_action(isc_task_t *task,
					   isc_event_t *event);
static void acache_cleaner_shutdown_action(isc_task_t *task,
					   isc_event_t *event);

/*
 * acache should be locked.  If it is not, the stats can get out of whack,
 * which is not a big deal for us since this is for debugging / stats
 */
static void
reset_stats(dns_acache_t *acache) {
	acache->stats.hits = 0;
	acache->stats.queries = 0;
	acache->stats.misses = 0;
	acache->stats.adds = 0;
	acache->stats.deleted = 0;
	acache->stats.cleaned = 0;
	acache->stats.overmem = 0;
	acache->stats.overmem_nocreates = 0;
	acache->stats.nomem = 0;
}

/*
 * The acache must be locked before calling.
 */
static inline isc_boolean_t
check_noentry(dns_acache_t *acache) {
	if (ISC_LIST_EMPTY(acache->entries) && acache->dbentries == 0) {
		return (ISC_TRUE);
	}

	return (ISC_FALSE);
}

/*
 * The acache must be locked before calling.
 */
static void
shutdown_entries(dns_acache_t *acache) {
	dns_acacheentry_t *entry, *entry_next;

	REQUIRE(DNS_ACACHE_VALID(acache));
	INSIST(acache->shutting_down);

	/*
	 * Release the dependency of all entries, and detach them.
	 */
	for (entry = ISC_LIST_HEAD(acache->entries);
	     entry != NULL;
	     entry = entry_next) {
		entry_next = ISC_LIST_NEXT(entry, link);

		ACACHE_LOCK(&acache->entrylocks[entry->locknum],
			    isc_rwlocktype_write);

		/*
		 * If the cleaner holds this entry, it will be unlinked and
		 * freed in the cleaner later.
		 */
		if (acache->cleaner.current_entry != entry)
			ISC_LIST_UNLINK(acache->entries, entry, link);
		unlink_dbentries(acache, entry);
		if (entry->callback != NULL) {
			(entry->callback)(entry, &entry->cbarg);
			entry->callback = NULL;
		}

		ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
			      isc_rwlocktype_write);

		if (acache->cleaner.current_entry != entry)
			dns_acache_detachentry(&entry);
	}
}

/*
 * The acache must be locked before calling.
 */
static void
shutdown_buckets(dns_acache_t *acache) {
	int i;
	dbentry_t *dbent;

	REQUIRE(DNS_ACACHE_VALID(acache));
	INSIST(acache->shutting_down);

	for (i = 0; i < DBBUCKETS; i++) {
		while ((dbent = ISC_LIST_HEAD(acache->dbbucket[i])) != NULL) {
			INSIST(ISC_LIST_EMPTY(dbent->originlist) &&
			       ISC_LIST_EMPTY(dbent->referlist));
			ISC_LIST_UNLINK(acache->dbbucket[i], dbent, link);
						
			dns_db_detach(&dbent->db);

			isc_mem_put(acache->mctx, dbent, sizeof(*dbent));
				    
			acache->dbentries--;
		}
	}

	INSIST(acache->dbentries == 0);
}

static void
shutdown_task(isc_task_t *task, isc_event_t *ev) {
	dns_acache_t *acache;

	UNUSED(task);

	acache = ev->ev_arg;
	INSIST(DNS_ACACHE_VALID(acache));

	isc_event_free(&ev);

	LOCK(&acache->lock);

	shutdown_entries(acache);
	shutdown_buckets(acache);

	UNLOCK(&acache->lock);

	dns_acache_detach(&acache);
}

/* The acache and the entry must be locked before calling. */
static inline void
unlink_dbentries(dns_acache_t *acache, dns_acacheentry_t *ent) {
	isc_result_t result;
	dbentry_t *dbent;

	if (ISC_LINK_LINKED(ent, olink)) {
		INSIST(ent->origdb != NULL);
		dbent = NULL;
		result = finddbent(acache, ent->origdb, &dbent);
		INSIST(result == ISC_R_SUCCESS);

		ISC_LIST_UNLINK(dbent->originlist, ent, olink);
	}
	if (ISC_LINK_LINKED(ent, rlink)) {
		INSIST(ent->db != NULL);
		dbent = NULL;
		result = finddbent(acache, ent->db, &dbent);
		INSIST(result == ISC_R_SUCCESS);

		ISC_LIST_UNLINK(dbent->referlist, ent, rlink);
	}
}

/* There must not be a reference to this entry. */
static void
destroy_entry(dns_acacheentry_t *entry) {
	dns_acache_t *acache;

	REQUIRE(DNS_ACACHEENTRY_VALID(entry));

	acache = entry->acache;
	REQUIRE(DNS_ACACHE_VALID(acache));

	/*
	 * Since there is no reference to this entry, it is safe to call
	 * clear_entry() here.
	 */
	clear_entry(acache, entry);

	isc_mem_put(acache->mctx, entry, sizeof(*entry));

	dns_acache_detach(&acache);
}

static void
destroy(dns_acache_t *acache) {
	int i;

	REQUIRE(DNS_ACACHE_VALID(acache));

	ATRACE("destroy");

	isc_mem_setwater(acache->mctx, NULL, NULL, 0, 0);

	if (acache->cleaner.overmem_event != NULL)
		isc_event_free(&acache->cleaner.overmem_event);

	if (acache->cleaner.resched_event != NULL)
		isc_event_free(&acache->cleaner.resched_event);

	if (acache->task != NULL)
		isc_task_detach(&acache->task);