/* -*- linux-c -*- --------------------------------------------------------- *
|
/* -*- linux-c -*- --------------------------------------------------------- *
|
*
|
*
|
* linux/fs/autofs/dirhash.c
|
* linux/fs/autofs/dirhash.c
|
*
|
*
|
* Copyright 1997 Transmeta Corporation -- All Rights Reserved
|
* Copyright 1997 Transmeta Corporation -- All Rights Reserved
|
*
|
*
|
* This file is part of the Linux kernel and is made available under
|
* This file is part of the Linux kernel and is made available under
|
* the terms of the GNU General Public License, version 2, or at your
|
* the terms of the GNU General Public License, version 2, or at your
|
* option, any later version, incorporated herein by reference.
|
* option, any later version, incorporated herein by reference.
|
*
|
*
|
* ------------------------------------------------------------------------- */
|
* ------------------------------------------------------------------------- */
|
|
|
#include "autofs_i.h"
|
#include "autofs_i.h"
|
|
|
/* Functions for maintenance of expiry queue */
|
/* Functions for maintenance of expiry queue */
|
|
|
static void autofs_init_usage(struct autofs_dirhash *dh,
|
static void autofs_init_usage(struct autofs_dirhash *dh,
|
struct autofs_dir_ent *ent)
|
struct autofs_dir_ent *ent)
|
{
|
{
|
ent->exp_next = &dh->expiry_head;
|
ent->exp_next = &dh->expiry_head;
|
ent->exp_prev = dh->expiry_head.exp_prev;
|
ent->exp_prev = dh->expiry_head.exp_prev;
|
dh->expiry_head.exp_prev->exp_next = ent;
|
dh->expiry_head.exp_prev->exp_next = ent;
|
dh->expiry_head.exp_prev = ent;
|
dh->expiry_head.exp_prev = ent;
|
ent->last_usage = jiffies;
|
ent->last_usage = jiffies;
|
}
|
}
|
|
|
static void autofs_delete_usage(struct autofs_dir_ent *ent)
|
static void autofs_delete_usage(struct autofs_dir_ent *ent)
|
{
|
{
|
ent->exp_prev->exp_next = ent->exp_next;
|
ent->exp_prev->exp_next = ent->exp_next;
|
ent->exp_next->exp_prev = ent->exp_prev;
|
ent->exp_next->exp_prev = ent->exp_prev;
|
}
|
}
|
|
|
void autofs_update_usage(struct autofs_dirhash *dh,
|
void autofs_update_usage(struct autofs_dirhash *dh,
|
struct autofs_dir_ent *ent)
|
struct autofs_dir_ent *ent)
|
{
|
{
|
autofs_delete_usage(ent); /* Unlink from current position */
|
autofs_delete_usage(ent); /* Unlink from current position */
|
autofs_init_usage(dh,ent); /* Relink at queue tail */
|
autofs_init_usage(dh,ent); /* Relink at queue tail */
|
}
|
}
|
|
|
struct autofs_dir_ent *autofs_expire(struct autofs_dirhash *dh,
|
struct autofs_dir_ent *autofs_expire(struct autofs_dirhash *dh,
|
unsigned long timeout)
|
unsigned long timeout)
|
{
|
{
|
struct autofs_dir_ent *ent;
|
struct autofs_dir_ent *ent;
|
|
|
ent = dh->expiry_head.exp_next;
|
ent = dh->expiry_head.exp_next;
|
|
|
if ( ent == &(dh->expiry_head) ) return NULL;
|
if ( ent == &(dh->expiry_head) ) return NULL;
|
return (jiffies - ent->last_usage >= timeout) ? ent : NULL;
|
return (jiffies - ent->last_usage >= timeout) ? ent : NULL;
|
}
|
}
|
|
|
/* Adapted from the Dragon Book, page 436 */
|
/* Adapted from the Dragon Book, page 436 */
|
/* This particular hashing algorithm requires autofs_hash_t == u32 */
|
/* This particular hashing algorithm requires autofs_hash_t == u32 */
|
autofs_hash_t autofs_hash(const char *name, int len)
|
autofs_hash_t autofs_hash(const char *name, int len)
|
{
|
{
|
autofs_hash_t h = 0;
|
autofs_hash_t h = 0;
|
while ( len-- ) {
|
while ( len-- ) {
|
h = (h << 4) + (unsigned char) (*name++);
|
h = (h << 4) + (unsigned char) (*name++);
|
h ^= ((h & 0xf0000000) >> 24);
|
h ^= ((h & 0xf0000000) >> 24);
|
}
|
}
|
return h;
|
return h;
|
}
|
}
|
|
|
void autofs_initialize_hash(struct autofs_dirhash *dh) {
|
void autofs_initialize_hash(struct autofs_dirhash *dh) {
|
memset(&dh->h, 0, AUTOFS_HASH_SIZE*sizeof(struct autofs_dir_ent *));
|
memset(&dh->h, 0, AUTOFS_HASH_SIZE*sizeof(struct autofs_dir_ent *));
|
dh->expiry_head.exp_next = dh->expiry_head.exp_prev =
|
dh->expiry_head.exp_next = dh->expiry_head.exp_prev =
|
&dh->expiry_head;
|
&dh->expiry_head;
|
}
|
}
|
|
|
struct autofs_dir_ent *autofs_hash_lookup(const struct autofs_dirhash *dh, autofs_hash_t hash, const char *name, int len)
|
struct autofs_dir_ent *autofs_hash_lookup(const struct autofs_dirhash *dh, autofs_hash_t hash, const char *name, int len)
|
{
|
{
|
struct autofs_dir_ent *dhn;
|
struct autofs_dir_ent *dhn;
|
|
|
DPRINTK(("autofs_hash_lookup: hash = 0x%08x, name = ", hash));
|
DPRINTK(("autofs_hash_lookup: hash = 0x%08x, name = ", hash));
|
autofs_say(name,len);
|
autofs_say(name,len);
|
|
|
for ( dhn = dh->h[hash % AUTOFS_HASH_SIZE] ; dhn ; dhn = dhn->next ) {
|
for ( dhn = dh->h[hash % AUTOFS_HASH_SIZE] ; dhn ; dhn = dhn->next ) {
|
if ( hash == dhn->hash &&
|
if ( hash == dhn->hash &&
|
len == dhn->len &&
|
len == dhn->len &&
|
!memcmp(name, dhn->name, len) )
|
!memcmp(name, dhn->name, len) )
|
break;
|
break;
|
}
|
}
|
|
|
return dhn;
|
return dhn;
|
}
|
}
|
|
|
void autofs_hash_insert(struct autofs_dirhash *dh, struct autofs_dir_ent *ent)
|
void autofs_hash_insert(struct autofs_dirhash *dh, struct autofs_dir_ent *ent)
|
{
|
{
|
struct autofs_dir_ent **dhnp;
|
struct autofs_dir_ent **dhnp;
|
|
|
DPRINTK(("autofs_hash_insert: hash = 0x%08x, name = ", ent->hash));
|
DPRINTK(("autofs_hash_insert: hash = 0x%08x, name = ", ent->hash));
|
autofs_say(ent->name,ent->len);
|
autofs_say(ent->name,ent->len);
|
|
|
autofs_init_usage(dh,ent);
|
autofs_init_usage(dh,ent);
|
|
|
dhnp = &dh->h[ent->hash % AUTOFS_HASH_SIZE];
|
dhnp = &dh->h[ent->hash % AUTOFS_HASH_SIZE];
|
ent->next = *dhnp;
|
ent->next = *dhnp;
|
ent->back = dhnp;
|
ent->back = dhnp;
|
*dhnp = ent;
|
*dhnp = ent;
|
}
|
}
|
|
|
void autofs_hash_delete(struct autofs_dir_ent *ent)
|
void autofs_hash_delete(struct autofs_dir_ent *ent)
|
{
|
{
|
*(ent->back) = ent->next;
|
*(ent->back) = ent->next;
|
|
|
autofs_delete_usage(ent);
|
autofs_delete_usage(ent);
|
|
|
kfree(ent->name);
|
kfree(ent->name);
|
kfree(ent);
|
kfree(ent);
|
}
|
}
|
|
|
/*
|
/*
|
* Used by readdir(). We must validate "ptr", so we can't simply make it
|
* Used by readdir(). We must validate "ptr", so we can't simply make it
|
* a pointer. Values below 0xffff are reserved; calling with any value
|
* a pointer. Values below 0xffff are reserved; calling with any value
|
* <= 0x10000 will return the first entry found.
|
* <= 0x10000 will return the first entry found.
|
*/
|
*/
|
struct autofs_dir_ent *autofs_hash_enum(const struct autofs_dirhash *dh, off_t *ptr)
|
struct autofs_dir_ent *autofs_hash_enum(const struct autofs_dirhash *dh, off_t *ptr)
|
{
|
{
|
int bucket, ecount, i;
|
int bucket, ecount, i;
|
struct autofs_dir_ent *ent;
|
struct autofs_dir_ent *ent;
|
|
|
bucket = (*ptr >> 16) - 1;
|
bucket = (*ptr >> 16) - 1;
|
ecount = *ptr & 0xffff;
|
ecount = *ptr & 0xffff;
|
|
|
if ( bucket < 0 ) {
|
if ( bucket < 0 ) {
|
bucket = ecount = 0;
|
bucket = ecount = 0;
|
}
|
}
|
|
|
DPRINTK(("autofs_hash_enum: bucket %d, entry %d\n", bucket, ecount));
|
DPRINTK(("autofs_hash_enum: bucket %d, entry %d\n", bucket, ecount));
|
|
|
ent = NULL;
|
ent = NULL;
|
|
|
while ( bucket < AUTOFS_HASH_SIZE ) {
|
while ( bucket < AUTOFS_HASH_SIZE ) {
|
ent = dh->h[bucket];
|
ent = dh->h[bucket];
|
for ( i = ecount ; ent && i ; i-- )
|
for ( i = ecount ; ent && i ; i-- )
|
ent = ent->next;
|
ent = ent->next;
|
|
|
if (ent) {
|
if (ent) {
|
ecount++; /* Point to *next* entry */
|
ecount++; /* Point to *next* entry */
|
break;
|
break;
|
}
|
}
|
|
|
bucket++; ecount = 0;
|
bucket++; ecount = 0;
|
}
|
}
|
|
|
#ifdef DEBUG
|
#ifdef DEBUG
|
if ( !ent )
|
if ( !ent )
|
printk("autofs_hash_enum: nothing found\n");
|
printk("autofs_hash_enum: nothing found\n");
|
else {
|
else {
|
printk("autofs_hash_enum: found hash %08x, name", ent->hash);
|
printk("autofs_hash_enum: found hash %08x, name", ent->hash);
|
autofs_say(ent->name,ent->len);
|
autofs_say(ent->name,ent->len);
|
}
|
}
|
#endif
|
#endif
|
|
|
*ptr = ((bucket+1) << 16) + ecount;
|
*ptr = ((bucket+1) << 16) + ecount;
|
return ent;
|
return ent;
|
}
|
}
|
|
|
/* Delete everything. This is used on filesystem destruction, so we
|
/* Delete everything. This is used on filesystem destruction, so we
|
make no attempt to keep the pointers valid */
|
make no attempt to keep the pointers valid */
|
void autofs_hash_nuke(struct autofs_dirhash *dh)
|
void autofs_hash_nuke(struct autofs_dirhash *dh)
|
{
|
{
|
int i;
|
int i;
|
struct autofs_dir_ent *ent, *nent;
|
struct autofs_dir_ent *ent, *nent;
|
|
|
for ( i = 0 ; i < AUTOFS_HASH_SIZE ; i++ ) {
|
for ( i = 0 ; i < AUTOFS_HASH_SIZE ; i++ ) {
|
for ( ent = dh->h[i] ; ent ; ent = nent ) {
|
for ( ent = dh->h[i] ; ent ; ent = nent ) {
|
nent = ent->next;
|
nent = ent->next;
|
kfree(ent->name);
|
kfree(ent->name);
|
kfree(ent);
|
kfree(ent);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
