KVM: Use kzalloc to avoid allocating kvm_regs from kernel stack
[linux-2.6.git] / fs / autofs / dirhash.c
1 /* -*- linux-c -*- --------------------------------------------------------- *
2  *
3  * linux/fs/autofs/dirhash.c
4  *
5  *  Copyright 1997-1998 Transmeta Corporation -- All Rights Reserved
6  *
7  * This file is part of the Linux kernel and is made available under
8  * the terms of the GNU General Public License, version 2, or at your
9  * option, any later version, incorporated herein by reference.
10  *
11  * ------------------------------------------------------------------------- */
12
13 #include "autofs_i.h"
14
15 /* Functions for maintenance of expiry queue */
16
17 static void autofs_init_usage(struct autofs_dirhash *dh,
18                               struct autofs_dir_ent *ent)
19 {
20         list_add_tail(&ent->exp, &dh->expiry_head);
21         ent->last_usage = jiffies;
22 }
23
24 static void autofs_delete_usage(struct autofs_dir_ent *ent)
25 {
26         list_del(&ent->exp);
27 }
28
29 void autofs_update_usage(struct autofs_dirhash *dh,
30                          struct autofs_dir_ent *ent)
31 {
32         autofs_delete_usage(ent);   /* Unlink from current position */
33         autofs_init_usage(dh,ent);  /* Relink at queue tail */
34 }
35
36 struct autofs_dir_ent *autofs_expire(struct super_block *sb,
37                                      struct autofs_sb_info *sbi,
38                                      struct vfsmount *mnt)
39 {
40         struct autofs_dirhash *dh = &sbi->dirhash;
41         struct autofs_dir_ent *ent;
42         struct dentry *dentry;
43         unsigned long timeout = sbi->exp_timeout;
44
45         while (1) {
46                 if ( list_empty(&dh->expiry_head) || sbi->catatonic )
47                         return NULL;    /* No entries */
48                 /* We keep the list sorted by last_usage and want old stuff */
49                 ent = list_entry(dh->expiry_head.next, struct autofs_dir_ent, exp);
50                 if (jiffies - ent->last_usage < timeout)
51                         break;
52                 /* Move to end of list in case expiry isn't desirable */
53                 autofs_update_usage(dh, ent);
54
55                 /* Check to see that entry is expirable */
56                 if ( ent->ino < AUTOFS_FIRST_DIR_INO )
57                         return ent; /* Symlinks are always expirable */
58
59                 /* Get the dentry for the autofs subdirectory */
60                 dentry = ent->dentry;
61
62                 if ( !dentry ) {
63                         /* Should only happen in catatonic mode */
64                         printk("autofs: dentry == NULL but inode range is directory, entry %s\n", ent->name);
65                         autofs_delete_usage(ent);
66                         continue;
67                 }
68
69                 if ( !dentry->d_inode ) {
70                         dput(dentry);
71                         printk("autofs: negative dentry on expiry queue: %s\n",
72                                ent->name);
73                         autofs_delete_usage(ent);
74                         continue;
75                 }
76
77                 /* Make sure entry is mounted and unused; note that dentry will
78                    point to the mounted-on-top root. */
79                 if (!S_ISDIR(dentry->d_inode->i_mode)||!d_mountpoint(dentry)) {
80                         DPRINTK(("autofs: not expirable (not a mounted directory): %s\n", ent->name));
81                         continue;
82                 }
83                 mntget(mnt);
84                 dget(dentry);
85                 if (!follow_down(&mnt, &dentry)) {
86                         dput(dentry);
87                         mntput(mnt);
88                         DPRINTK(("autofs: not expirable (not a mounted directory): %s\n", ent->name));
89                         continue;
90                 }
91                 while (d_mountpoint(dentry) && follow_down(&mnt, &dentry))
92                         ;
93                 dput(dentry);
94
95                 if ( may_umount(mnt) ) {
96                         mntput(mnt);
97                         DPRINTK(("autofs: signaling expire on %s\n", ent->name));
98                         return ent; /* Expirable! */
99                 }
100                 DPRINTK(("autofs: didn't expire due to may_umount: %s\n", ent->name));
101                 mntput(mnt);
102         }
103         return NULL;            /* No expirable entries */
104 }
105
106 void autofs_initialize_hash(struct autofs_dirhash *dh) {
107         memset(&dh->h, 0, AUTOFS_HASH_SIZE*sizeof(struct autofs_dir_ent *));
108         INIT_LIST_HEAD(&dh->expiry_head);
109 }
110
111 struct autofs_dir_ent *autofs_hash_lookup(const struct autofs_dirhash *dh, struct qstr *name)
112 {
113         struct autofs_dir_ent *dhn;
114
115         DPRINTK(("autofs_hash_lookup: hash = 0x%08x, name = ", name->hash));
116         autofs_say(name->name,name->len);
117
118         for ( dhn = dh->h[(unsigned) name->hash % AUTOFS_HASH_SIZE] ; dhn ; dhn = dhn->next ) {
119                 if ( name->hash == dhn->hash &&
120                      name->len == dhn->len &&
121                      !memcmp(name->name, dhn->name, name->len) )
122                         break;
123         }
124
125         return dhn;
126 }
127
128 void autofs_hash_insert(struct autofs_dirhash *dh, struct autofs_dir_ent *ent)
129 {
130         struct autofs_dir_ent **dhnp;
131
132         DPRINTK(("autofs_hash_insert: hash = 0x%08x, name = ", ent->hash));
133         autofs_say(ent->name,ent->len);
134
135         autofs_init_usage(dh,ent);
136         if (ent->dentry)
137                 dget(ent->dentry);
138
139         dhnp = &dh->h[(unsigned) ent->hash % AUTOFS_HASH_SIZE];
140         ent->next = *dhnp;
141         ent->back = dhnp;
142         *dhnp = ent;
143         if ( ent->next )
144                 ent->next->back = &(ent->next);
145 }
146
147 void autofs_hash_delete(struct autofs_dir_ent *ent)
148 {
149         *(ent->back) = ent->next;
150         if ( ent->next )
151                 ent->next->back = ent->back;
152
153         autofs_delete_usage(ent);
154
155         if ( ent->dentry )
156                 dput(ent->dentry);
157         kfree(ent->name);
158         kfree(ent);
159 }
160
161 /*
162  * Used by readdir().  We must validate "ptr", so we can't simply make it
163  * a pointer.  Values below 0xffff are reserved; calling with any value
164  * <= 0x10000 will return the first entry found.
165  *
166  * "last" can be NULL or the value returned by the last search *if* we
167  * want the next sequential entry.
168  */
169 struct autofs_dir_ent *autofs_hash_enum(const struct autofs_dirhash *dh,
170                                         off_t *ptr, struct autofs_dir_ent *last)
171 {
172         int bucket, ecount, i;
173         struct autofs_dir_ent *ent;
174
175         bucket = (*ptr >> 16) - 1;
176         ecount = *ptr & 0xffff;
177
178         if ( bucket < 0 ) {
179                 bucket = ecount = 0;
180         } 
181
182         DPRINTK(("autofs_hash_enum: bucket %d, entry %d\n", bucket, ecount));
183
184         ent = last ? last->next : NULL;
185
186         if ( ent ) {
187                 ecount++;
188         } else {
189                 while  ( bucket < AUTOFS_HASH_SIZE ) {
190                         ent = dh->h[bucket];
191                         for ( i = ecount ; ent && i ; i-- )
192                                 ent = ent->next;
193                         
194                         if (ent) {
195                                 ecount++; /* Point to *next* entry */
196                                 break;
197                         }
198                         
199                         bucket++; ecount = 0;
200                 }
201         }
202
203 #ifdef DEBUG
204         if ( !ent )
205                 printk("autofs_hash_enum: nothing found\n");
206         else {
207                 printk("autofs_hash_enum: found hash %08x, name", ent->hash);
208                 autofs_say(ent->name,ent->len);
209         }
210 #endif
211
212         *ptr = ((bucket+1) << 16) + ecount;
213         return ent;
214 }
215
216 /* Iterate over all the ents, and remove all dentry pointers.  Used on
217    entering catatonic mode, in order to make the filesystem unmountable. */
218 void autofs_hash_dputall(struct autofs_dirhash *dh)
219 {
220         int i;
221         struct autofs_dir_ent *ent;
222
223         for ( i = 0 ; i < AUTOFS_HASH_SIZE ; i++ ) {
224                 for ( ent = dh->h[i] ; ent ; ent = ent->next ) {
225                         if ( ent->dentry ) {
226                                 dput(ent->dentry);
227                                 ent->dentry = NULL;
228                         }
229                 }
230         }
231 }
232
233 /* Delete everything.  This is used on filesystem destruction, so we
234    make no attempt to keep the pointers valid */
235 void autofs_hash_nuke(struct autofs_sb_info *sbi)
236 {
237         int i;
238         struct autofs_dir_ent *ent, *nent;
239
240         for ( i = 0 ; i < AUTOFS_HASH_SIZE ; i++ ) {
241                 for ( ent = sbi->dirhash.h[i] ; ent ; ent = nent ) {
242                         nent = ent->next;
243                         if ( ent->dentry )
244                                 dput(ent->dentry);
245                         kfree(ent->name);
246                         kfree(ent);
247                 }
248         }
249 }