9ns: Add tree_chan_ctl()
[akaros.git] / kern / src / ns / tree_file.c
1 /* Copyright (c) 2018 Google Inc
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * tree_file: structs and helpers for a tree-based filesystem for 9ns devices.
6  */
7
8 #include <tree_file.h>
9 #include <kmalloc.h>
10 #include <string.h>
11 #include <stdio.h>
12 #include <assert.h>
13 #include <error.h>
14
15 /* Adds to the LRU if it was not on it.
16  *
17  * Caller holds the TF lock or o/w knows it has the only ref to tf. */
18 static void __add_to_lru(struct tree_file *tf)
19 {
20         struct walk_cache *wc = &tf->tfs->wc;
21
22         if (tf->flags & TF_F_ON_LRU)
23                 return;
24         tf->flags |= TF_F_ON_LRU;
25         spin_lock(&wc->lru_lock);
26         list_add_tail(&tf->lru, &wc->lru);
27         spin_unlock(&wc->lru_lock);
28 }
29
30 /* Removes from the LRU if it was on it.
31  *
32  * Caller holds the TF lock or o/w knows it has the only ref to tf. */
33 static void __remove_from_lru(struct tree_file *tf)
34 {
35         struct walk_cache *wc = &tf->tfs->wc;
36
37         if (!(tf->flags & TF_F_ON_LRU))
38                 return;
39         assert(kref_refcnt(&tf->kref) == 0);
40         tf->flags &= ~TF_F_ON_LRU;
41         spin_lock(&wc->lru_lock);
42         list_del(&tf->lru);
43         spin_unlock(&wc->lru_lock);
44 }
45
46 /* Caller holds the parent's qlock.  Separate helpers here in case we track
47  * nr_children. */
48 static void __add_to_parent_list(struct tree_file *parent,
49                                  struct tree_file *child)
50 {
51         list_add(&child->siblings, &parent->children);
52 }
53
54 /* Caller holds the parent's qlock */
55 static void __remove_from_parent_list(struct tree_file *parent,
56                                       struct tree_file *child)
57 {
58         list_del(&child->siblings);
59 }
60
61 /* Safely grabs a kref on TF, possibly resurrecting from 0, at which point the
62  * file would be on an LRU list.  This syncs with tree removers, including
63  * unlinking from the tree on remove and LRU cache pruners.  Returns true if we
64  * got the ref, false if we lost and the file was disconnected. */
65 bool tf_kref_get(struct tree_file *tf)
66 {
67         spin_lock(&tf->lifetime);
68         if (tf->flags & TF_F_DISCONNECTED) {
69                 spin_unlock(&tf->lifetime);
70                 return false;
71         }
72         __remove_from_lru(tf);
73         __kref_get(&tf->kref, 1);
74         tf->flags |= TF_F_HAS_BEEN_USED;
75         spin_unlock(&tf->lifetime);
76         return true;
77 }
78
79 void tf_kref_put(struct tree_file *tf)
80 {
81         kref_put(&tf->kref);
82 }
83
84 static void __tf_free(struct tree_file *tf)
85 {
86         struct tree_file *parent = tf->parent;
87         struct tree_filesystem *tfs = tf->tfs;
88
89         tf->tfs->tf_ops.free(tf);
90         if (tf->flags & TF_F_IS_ROOT) {
91                 assert(tfs->root == tf);
92                 assert(!parent);
93         }
94         cleanup_fs_file((struct fs_file*)tf);
95         kfree(tf);
96         /* the reason for decreffing the parent now is for convenience on releasing.
97          * When we unlink the child from the LRU pruner, we don't want to release
98          * the parent immediately while we hold the parent's qlock (and other
99          * locks). */
100         if (parent)
101                 tf_kref_put(parent);
102 }
103
104 static void __tf_free_rcu(struct rcu_head *head)
105 {
106         struct tree_file *tf = container_of(head, struct tree_file, rcu);
107
108         __tf_free(tf);
109 }
110
111 static void tf_release(struct kref *kref)
112 {
113         struct tree_file *tf = container_of(kref, struct tree_file, kref);
114
115         assert(!(tf->flags & TF_F_NEGATIVE));
116
117         spin_lock(&tf->lifetime);
118         if (kref_refcnt(&tf->kref) > 0) {
119                 /* Someone resurrected after we decreffed to 0. */
120                 assert(!(tf->flags & TF_F_ON_LRU));
121                 spin_unlock(&tf->lifetime);
122                 return;
123         }
124         if (!(tf->flags & (TF_F_DISCONNECTED | TF_F_IS_ROOT))) {
125                 /* It's possible that we paused before locking, then another thread
126                  * upped, downed, and put it on the LRU list already.  The helper deals
127                  * with that. */
128                 __add_to_lru(tf);
129                 spin_unlock(&tf->lifetime);
130                 return;
131         }
132         spin_unlock(&tf->lifetime);
133         /* Need RCU, since we could have had a reader who saw the object and still
134          * needs to try to kref (and fail).  call_rcu, since we can't block. */
135         call_rcu(&tf->rcu, __tf_free_rcu);
136 }
137
138 static unsigned long hash_string(const char *name)
139 {
140         unsigned long hash = 5381;
141
142         for (const char *p = name; *p; p++) {
143                 /* hash * 33 + c, djb2's technique */
144                 hash = ((hash << 5) + hash) + *p;
145         }
146         return hash;
147 }
148
149 static void wc_init(struct walk_cache *wc)
150 {
151         spinlock_init(&wc->lru_lock);
152         INIT_LIST_HEAD(&wc->lru);
153         spinlock_init(&wc->ht_lock);
154         wc->ht = wc->static_ht;
155         hash_init_hh(&wc->hh);
156         for (int i = 0; i < wc->hh.nr_hash_lists; i++)
157                 INIT_HLIST_HEAD(&wc->ht[i]);
158 }
159
160 static void wc_destroy(struct walk_cache *wc)
161 {
162         assert(list_empty(&wc->lru));
163         for (int i = 0; i < wc->hh.nr_hash_lists; i++)
164                 assert(hlist_empty(&wc->ht[i]));
165         if (wc->ht != wc->static_ht)
166                 kfree(wc->ht);
167 }
168
169 /* Looks up the child of parent named 'name' in the walk cache hash table.
170  * Caller needs to hold an rcu read lock. */
171 static struct tree_file *wc_lookup_child(struct tree_file *parent,
172                                          const char *name)
173 {
174         struct walk_cache *wc = &parent->tfs->wc;
175         unsigned long hash_val = hash_string(name);
176         struct hlist_head *bucket;
177         struct tree_file *i;
178
179         bucket = &wc->ht[hash_val % wc->hh.nr_hash_bits];
180         hlist_for_each_entry_rcu(i, bucket, hash) {
181                 /* Note 'i' is an rcu protected pointer.  That deref is safe.  i->parent
182                  * is also a pointer that in general we want to protect.  In this case,
183                  * even though we don't dereference it, we want a pointer that is good
184                  * enough to dereference so we can do the comparison. */
185                 if (rcu_dereference(i->parent) != parent)
186                         continue;
187                 /* The file's name should never change while it is in the table, so no
188                  * need for a seq-reader.  Can't assert though, since there are valid
189                  * reasons for other seq lockers. */
190                 if (!strcmp(tree_file_to_name(i), name))
191                         return i;
192         }
193         return NULL;
194 }
195
196 /* Caller should hold the parent's qlock */
197 static void wc_insert_child(struct tree_file *parent, struct tree_file *child)
198 {
199         struct walk_cache *wc = &parent->tfs->wc;
200         unsigned long hash_val = hash_string(tree_file_to_name(child));
201         struct hlist_head *bucket;
202
203         assert(child->parent == parent);        /* catch bugs from our callers */
204         /* TODO: consider bucket locks and/or growing the HT.  Prob need a seq_ctr
205          * in the WC, used on the read side during resizing.  Removal probably would
206          * need something other than the bucket lock too (confusion about which
207          * bucket during the op). */
208         spin_lock(&wc->ht_lock);
209         bucket = &wc->ht[hash_val % wc->hh.nr_hash_bits];
210         hlist_add_head_rcu(&child->hash, bucket);
211         spin_unlock(&wc->ht_lock);
212 }
213
214 /* Caller should hold the parent's qlock */
215 static void wc_remove_child(struct tree_file *parent, struct tree_file *child)
216 {
217         struct walk_cache *wc = &parent->tfs->wc;
218
219         assert(child->parent == parent);        /* catch bugs from our callers */
220         spin_lock(&wc->ht_lock);
221         hlist_del_rcu(&child->hash);
222         spin_unlock(&wc->ht_lock);
223 }
224
225 /* Helper: returns a refcounted pointer to the potential parent.  May return 0.
226  *
227  * Caller needs to qlock the parent and recheck tf->parent.  Callers always need
228  * to get a kref on the parent.  We can rcu-read the parent and *attempt* to
229  * qlock under rcu, but we might block.  Then, say, the TF and the parent got
230  * removed, and *then* we get the qlock.  We're too late. */
231 static struct tree_file *__tf_get_potential_parent(struct tree_file *tf)
232 {
233         struct tree_file *parent;
234
235         rcu_read_lock();
236         parent = rcu_dereference(tf->parent);
237         if (!parent) {
238                 /* the root of the tree has no parent */
239                 rcu_read_unlock();
240                 return NULL;
241         }
242         if (!tf_kref_get(parent))
243                 parent = NULL;
244         rcu_read_unlock();
245         return parent;
246 }
247
248 /* Returns a refcounted and qlocked parent for child.  NULL on failure. */
249 static struct tree_file *get_locked_and_kreffed_parent(struct tree_file *child)
250 {
251         struct tree_file *parent;
252
253         parent = __tf_get_potential_parent(child);
254         if (!parent)
255                 return NULL;
256         qlock(&parent->file.qlock);
257         /* Checking the parent == child->parent isn't enough here.  That works for
258          * rename, but not removal/unlink.  Older versions of TF code cleared
259          * child->parent, but now that's dealt with in tf_free.
260          *
261          * We're doing a lockless peek at child's flags.  We hold the potential
262          * parent's lock, so if they are ours, no one will be messing with the
263          * disconnected flag.  If they are messing with it, then parent !=
264          * child->parent.  Also, once disconnected is set, it is never clear. */
265         if ((child->flags & TF_F_DISCONNECTED) || (parent != child->parent)) {
266                 qunlock(&parent->file.qlock);
267                 tf_kref_put(parent);
268                 return NULL;
269         }
270         return parent;
271 }
272
273 static bool __mark_disconnected(struct tree_file *tf)
274 {
275         bool need_to_free;
276
277         spin_lock(&tf->lifetime);
278         tf->flags |= TF_F_DISCONNECTED;
279         __remove_from_lru(tf);
280         need_to_free = kref_refcnt(&tf->kref) == 0;
281         spin_unlock(&tf->lifetime);
282         return need_to_free;
283 }
284
285 /* Disconnects child from the in-memory tree structure (i.e. only the front
286  * end).  Caller holds the parent qlock.  Assumes child is a child of parent.
287  * Once you disconnect, you can't touch the child object.
288  *
289  * Racing with concurrent lookups, who might grab a ref if they get in before
290  * DISCONNECTED, and racing with release (after ref = 0), who might free, if it
291  * was already unlinked. */
292 static void __disconnect_child(struct tree_file *parent,
293                                struct tree_file *child)
294 {
295         bool need_to_free;
296
297         need_to_free = __mark_disconnected(child);
298         /* Note child->parent is still set.  We clear that in __tf_free. */
299         __remove_from_parent_list(parent, child);
300         wc_remove_child(parent, child);
301         if (need_to_free)
302                 call_rcu(&child->rcu, __tf_free_rcu);
303 }
304
305 /* Backend will need to fill in dir, except for name.  Note this has a kref ==
306  * 0, but is not on the LRU yet. */
307 struct tree_file *tree_file_alloc(struct tree_filesystem *tfs,
308                                   struct tree_file *parent, const char *name)
309 {
310         struct tree_file *tf;
311
312         tf = kzmalloc(sizeof(struct tree_file), MEM_WAIT);
313         fs_file_init((struct fs_file*)tf, name, &tfs->fs_ops);
314         kref_init(&tf->kref, tf_release, 0);
315         spinlock_init(&tf->lifetime);
316         /* Need to set the parent early on, even if the child isn't linked yet, so
317          * that the TFS ops know who the parent is. */
318         tf->parent = parent;
319         if (parent)
320                 kref_get(&parent->kref, 1);
321         INIT_LIST_HEAD(&tf->children);
322         tf->can_have_children = true;
323         tf->tfs = tfs;
324         return tf;
325 }
326
327 /* Callers must hold the parent's qlock. */
328 static void __link_child(struct tree_file *parent, struct tree_file *child)
329 {
330         /* Devices may have already increffed ("+1 for existing").  Those that don't
331          * need to be on the LRU.  We haven't linked to the parent yet, so we hold
332          * the only ref.  Once we unlock in __add_to_lru, we're discoverable via
333          * that list, even though we're not linked.  The lru pruner is careful to
334          * not muck with the parent's or wc linkage without qlocking the parent,
335          * which we currently hold. */
336         if (kref_refcnt(&child->kref) == 0)
337                 __add_to_lru(child);
338         /* This was set in tree_file_alloc */
339         assert(child->parent == parent);
340         __add_to_parent_list(parent, child);
341         wc_insert_child(parent, child);
342 }
343
344 /* Hold the dir's qlock.  This probably works with any directory, though we only
345  * use it when we remove a directory.  The normal way to drop negative entries
346  * involves working directly with the WC (tfs_lru_prune_neg). */
347 static void __prune_dir_negatives(struct tree_file *dir)
348 {
349         struct tree_file *child, *temp;
350
351         list_for_each_entry_safe(child, temp, &dir->children, siblings) {
352                 if (!tree_file_is_negative(child))
353                         continue;
354                 spin_lock(&child->lifetime);
355                 assert(kref_refcnt(&child->kref) == 0);
356                 /* This mark prevents new lookups.  We'll disconnect it shortly. */
357                 child->flags |= TF_F_DISCONNECTED;
358                 spin_unlock(&child->lifetime);
359                 assert(child->parent == dir);
360                 __disconnect_child(dir, child);
361         }
362 }
363
364 static void neuter_directory(struct tree_file *dir)
365 {
366         qlock(&dir->file.qlock);
367         if (dir->tfs->tf_ops.has_children(dir)) {
368                 qunlock(&dir->file.qlock);
369                 error(ENOTEMPTY, "can't remove dir with children");
370         }
371         dir->can_have_children = false;
372         /* Even if we don't have real children, we might have some negatives.  Those
373          * aren't a reason to abort an rmdir, we just need to drop them. */
374         __prune_dir_negatives(dir);
375         qunlock(&dir->file.qlock);
376 }
377
378 /* Unlink a child from the tree.  Last ref will clean it up, which will not be
379  * us.  Caller should hold krefs on the child and parent.  The child's kref will
380  * actually keep the parent's alive, but all practical callers will have the
381  * parent kreff'ed and qlocked - which is required to ensure the child is still
382  * a child of parent. */
383 static void __unlink_child(struct tree_file *parent, struct tree_file *child)
384 {
385         /* Need to make sure concurrent creates/renames do not add children to
386          * directories that are unlinked.  Note we don't undo the neutering if the
387          * backend fails. */
388         if (tree_file_is_dir(child))
389                 neuter_directory(child);
390         /* The ramfs backend will probably decref the "+1 for existing" ref.
391          * This is OK.  If that was the last ref, the child will briefly be on
392          * the LRU list (which ramfs ignores).  When we disconnect, we'll yank
393          * the child back off the list and then free it (after rcu). */
394         parent->tfs->tf_ops.unlink(parent, child);
395         __disconnect_child(parent, child);
396 }
397
398 /* Talks to the backend and ensures a tree_file for the child exists, either
399  * positive or negative.  Throws an error; doesn't return NULL.
400  *
401  * This returns with an rcu read lock sufficient to protect the returned TF, but
402  * it is *not* kreffed.  It could be a negative entry, which is not kreffed.
403  *
404  * It is possible that at the moment we qunlock, someone comes along and removes
405  * the entry (LRU prune or file removal (for positive entries)).  That's fine -
406  * we have an rcu read lock, just like during a regular walk, when the removal
407  * could happen anyways. */
408 static struct tree_file *lookup_child_entry(struct tree_file *parent,
409                                             const char *name)
410 {
411         ERRSTACK(1);
412         struct tree_file *child;
413
414         qlock(&parent->file.qlock);
415         child = wc_lookup_child(parent, name);
416         if (child) {
417                 /* Since we last looked, but before we qlocked, someone else added our
418                  * entry. */
419                 rcu_read_lock();
420                 qunlock(&parent->file.qlock);
421                 return child;
422         }
423         if (!parent->can_have_children) {
424                 qunlock(&parent->file.qlock);
425                 error(ENOENT, "lookup failed, parent dir being removed");
426         }
427         child = tree_file_alloc(parent->tfs, parent, name);
428         if (waserror()) {
429                 /* child wasn't fully created, so freeing it may be tricky, esp on the
430                  * device ops side (might see something they never created). */
431                 __tf_free(child);
432                 qunlock(&parent->file.qlock);
433                 nexterror();
434         }
435         parent->tfs->tf_ops.lookup(parent, child);
436         poperror();
437         __link_child(parent, child);
438         rcu_read_lock();
439         qunlock(&parent->file.qlock);
440         return child;
441 }
442
443 /* Walks a tree filesystem from 'from' for array of null-terminated names.
444  * Devices will often use tree_chan_walk(), but can use this directly if they
445  * want more control.
446  *
447  * Returns the WQ of qids.  On complete/successful walks, we hang a refcnted TF
448  * on wq->clone.
449  *
450  * Walks can return intermediate results, which is when there is an error but we
451  * have walked at least once.  The partial return is useful for namec(), which
452  * can succeed if something was mounted on an intermediate QID.  Walks that have
453  * no results set error and return NULL, which is what namec() expects. */
454 struct walkqid *tree_file_walk(struct tree_file *from, char **name,
455                                unsigned int nname)
456 {
457         ERRSTACK(2);
458         struct tree_file *at, *next;
459         struct tree_filesystem *tfs = from->tfs;
460         struct walkqid *wq;
461
462         wq = kzmalloc(sizeof(struct walkqid) + nname * sizeof(struct qid),
463                                   MEM_WAIT);
464         /* A walk with zero names means "make me a copy."  If we go through the
465          * regular walker, our usual tf_kref_get will fail - similar to failing if
466          * we got a walk for "foo/../" during a concurrent removal of ourselves.
467          * We'll let a walk of zero names work, but if you provide any names, the
468          * actual walk must happen.
469          *
470          * This is tricky, and confused me a little.  We're returning a *TF* through
471          * wq->clone, not a chan, and that is refcounted.  Normally for chans that
472          * end up with wq->clone == c, we do not incref the object hanging off the
473          * chan (see k/d/d/eventfd.c), since there is just one chan with a kreffed
474          * object hanging off e.g. c->aux.  But here, wq->clone is considered a
475          * distinct refcnt to some TF, and it might be 'from.'  Our *caller* needs
476          * to deal with the "wq->clone == from_chan", since they deal with chans.
477          * We deal with tree files. */
478         if (!nname) {
479                 kref_get(&from->kref, 1);
480                 wq->clone = (struct chan*)from;
481                 return wq;
482         }
483         if (waserror()) {
484                 kfree(wq);
485                 poperror();
486                 return NULL;
487         }
488         rcu_read_lock();
489         at = from;
490         for (int i = 0; i < nname; i++) {
491                 /* Walks end if we reach a regular file, i.e. you can't walk through a
492                  * file, only a dir.  But even if there are more names, the overall walk
493                  * might succeed.  E.g. a directory could be mounted on top of the
494                  * current file we're at.  That's just not our job. */
495                 if (tree_file_is_file(at)) {
496                         if (i == 0)
497                                 error(ENOTDIR, "initial walk from a file");
498                         break;
499                 }
500                 /* Normally, symlinks stop walks, and namec's walk() will deal with it.
501                  * We allow walks 'through' symlinks, but only for .. and only for the
502                  * first name.  This is for relative lookups so we can find the parent
503                  * of a symlink. */
504                 if (tree_file_is_symlink(at)) {
505                         if (i != 0)
506                                 break;
507                         if (strcmp(name[i], ".."))
508                                 error(ELOOP, "walk from a symlink that wasn't ..");
509                 }
510                 if (!caller_has_tf_perms(at, O_READ)) {
511                         if (i == 0)
512                                 error(EACCES, "missing perm for lookup");
513                         break;
514                 }
515                 if (!strcmp(name[i], ".")) {
516                         wq->qid[wq->nqid++] = tree_file_to_qid(at);
517                         continue;
518                 }
519                 if (!strcmp(name[i], "..")) {
520                         next = rcu_dereference(at->parent);
521                         if (!next) {
522                                 if (tree_file_is_root(at)) {
523                                         wq->qid[wq->nqid++] = tree_file_to_qid(at);
524                                         /* I think namec should never give us DOTDOT that isn't at
525                                          * the end of the names array.  Though devwalk() seems to
526                                          * expect it. */
527                                         if (i != nname - 1)
528                                                 warn("Possible namec DOTDOT bug, call for help!");
529                                         continue;
530                                 }
531                                 /* We lost our parent due to a removal/rename.  We might have
532                                  * walked enough for our walk to succeed (e.g.  there's a mount
533                                  * point in the WQ), so we can return what we have.  Though if
534                                  * we've done nothing, it's a failure.
535                                  *
536                                  * Note the removal could have happened a long time ago:
537                                  * consider an O_PATH open, then namec_from().
538                                  *
539                                  * We also could walk up and see the *new* parent during
540                                  * rename().  For instance, /src/x/../y could get the old /src/y
541                                  * or the new /dst/y.  If we want to avoid that, then we'll need
542                                  * some sort of sync with rename to make sure we don't get the
543                                  * new one.  Though this can happen with namec_from(), so I'm
544                                  * not sure I care. */
545                                 if (i == 0)
546                                         error(ENOENT, "file lost its parent during lookup");
547                                 break;
548                         }
549                         at = next;
550                         wq->qid[wq->nqid++] = tree_file_to_qid(at);
551                         continue;
552                 }
553                 next = wc_lookup_child(at, name[i]);
554                 if (!next) {
555                         /* TFSs with no backend have the entire tree in the WC HT. */
556                         if (!tfs->tf_ops.lookup) {
557                                 if (i == 0)
558                                         error(ENOENT, "file does not exist");
559                                 break;
560                         }
561                         /* Need to hold a kref on 'at' before we rcu_read_unlock().  Our
562                          * TFS op might block. */
563                         if (!tf_kref_get(at)) {
564                                 if (i == 0)
565                                         error(ENOENT, "file was removed during lookup");
566                                 /* WQ has a qid for 'at' from a previous loop.  We can't grab a
567                                  * ref, so it's being removed/renamed.  Yet it's still OK to
568                                  * report this as part of the wq, since we could fail for other
569                                  * reasons (thus not getting nnames) and have the same race,
570                                  * which we handle below (i.e. we only get a ref when it was the
571                                  * last name).  Here we're just *noticing* the race. */
572                                 break;
573                         }
574                         rcu_read_unlock();
575                         /* propagate the error only on the first name.  Note we run the
576                          * 'else' case, and run the poperror case for non-errors and
577                          * non-name=0-errors. */
578                         if (waserror()) {
579                                 tf_kref_put(at);
580                                 if (i == 0)
581                                         nexterror();
582                                 /* In this case, we're discarding the waserror, same as in the
583                                  * other i != 0 cases. */
584                                 poperror();
585                                 break;
586                         }
587                         /* This returns with an rcu_read_lock protecting 'next' */
588                         next = lookup_child_entry(at, name[i]);
589                         tf_kref_put(at);
590                         poperror();
591                         assert(next);
592                 }
593                 if (tree_file_is_negative(next)) {
594                         /* lockless peek.  other flag users aren't atomic, etc. */
595                         if (!(next->flags & TF_F_HAS_BEEN_USED)) {
596                                 spin_lock(&next->lifetime);
597                                 next->flags |= TF_F_HAS_BEEN_USED;
598                                 spin_unlock(&next->lifetime);
599                         }
600                         if (i == 0)
601                                 error(ENOENT, "file does not exist");
602                         break;
603                 }
604                 at = next;
605                 wq->qid[wq->nqid++] = tree_file_to_qid(at);
606         }
607         if (wq->nqid == nname || tree_file_is_symlink(at)) {
608                 if (!tf_kref_get(at)) {
609                         /* We need to undo our last result as if we never saw it. */
610                         wq->nqid--;
611                         if (wq->nqid == 0)
612                                 error(ENOENT, "file was removed during lookup");
613                 } else {
614                         /* Hanging the refcounted TF off the wq->clone, which is cheating.
615                          * Our walker shim knows to expect this. */
616                         wq->clone = (struct chan*)at;
617                 }
618         }
619         rcu_read_unlock();
620         poperror();
621         return wq;
622 }
623
624 /* Most tree devices will use this for their walk op, similar to devwalk. */
625 struct walkqid *tree_chan_walk(struct chan *c, struct chan *nc, char **name,
626                                unsigned int nname)
627 {
628         struct tree_file *from, *to;
629         struct walkqid *wq;
630
631         from = chan_to_tree_file(c);
632         wq = tree_file_walk(from, name, nname);
633         if (!wq)
634                 return NULL;
635         if (!wq->clone)
636                 return wq;
637         if (!nc)
638                 nc = devclone(c);
639         /* Not sure if callers that specify nc must have a chan from our device */
640         assert(nc->type == c->type);
641         to = (struct tree_file*)wq->clone;
642         nc->qid = tree_file_to_qid(to);
643         chan_set_tree_file(nc, to);
644         wq->clone = nc;
645         /* We might be returning the same chan, so there's actually just one ref */
646         if (wq->clone == c)
647                 tf_kref_put(chan_to_tree_file(c));
648         return wq;
649 }
650
651 /* Creates a tree file under parent with name, omode, and perm.  Returns a
652  * kreffed tree_file for the new child.  Throws on error. */
653 struct tree_file *tree_file_create(struct tree_file *parent, const char *name,
654                                    uint32_t perm, char *ext)
655 {
656         ERRSTACK(2);
657         struct tree_file *child;
658         bool got_ref;
659         struct timespec now;
660
661         qlock(&parent->file.qlock);
662         if (waserror()) {
663                 qunlock(&parent->file.qlock);
664                 nexterror();
665         }
666         if (!caller_has_tf_perms(parent, O_WRITE))
667                 error(EACCES, "missing create permission on dir");
668         if (!parent->can_have_children)
669                 error(ENOENT, "create failed, parent dir being removed");
670         child = wc_lookup_child(parent, name);
671         if (child) {
672                 /* The create(5) message fails if the file exists, which differs from
673                  * the syscall.  namec() handles this. */
674                 if (!tree_file_is_negative(child))
675                         error(EEXIST, "file exists");
676                 /* future lookups that find no entry will qlock.  concurrent ones that
677                  * see the child, even if disconnected, will see it was negative and
678                  * fail. */
679                 __disconnect_child(parent, child);
680         }
681         child = tree_file_alloc(parent->tfs, parent, name);
682         if (waserror()) {
683                 __tf_free(child);
684                 nexterror();
685         }
686         /* Backend will need to know the ext for its create.  This gets cleaned up
687          * on error. */
688         if (perm & DMSYMLINK)
689                 kstrdup(&child->file.dir.ext, ext);
690         /* Backend will need to fill in dir, except for name. */
691         parent->tfs->tf_ops.create(parent, child, perm);
692         now = nsec2timespec(epoch_nsec());
693         __set_acmtime_to(&child->file,
694                          FSF_ATIME | FSF_BTIME | FSF_CTIME | FSF_MTIME, &now);
695         poperror();
696         /* At this point, the child is visible, so it must be ready to go */
697         __link_child(parent, child);
698         got_ref = tf_kref_get(child);
699         assert(got_ref);        /* we hold the qlock, no one should have removed */
700         __set_acmtime_to(&parent->file, FSF_CTIME | FSF_MTIME, &now);
701         qunlock(&parent->file.qlock);
702         poperror();
703         return child;
704 }
705
706 /* Most tree devices will use this for their create op. */
707 void tree_chan_create(struct chan *c, char *name, int omode, uint32_t perm,
708                       char *ext)
709 {
710         struct tree_file *parent, *child;
711
712         parent = chan_to_tree_file(c);
713         child = tree_file_create(parent, name, perm, ext);
714         c->qid = tree_file_to_qid(child);
715         c->mode = openmode(omode);
716         chan_set_tree_file(c, child);
717         tf_kref_put(parent);
718 }
719
720 struct chan *tree_chan_open(struct chan *c, int omode)
721 {
722         struct tree_file *tf = chan_to_tree_file(c);
723
724         if ((c->qid.type & QTDIR) && (omode & O_WRITE))
725                 error(EISDIR, "can't open a dir for writing");
726         if (c->qid.type & QTSYMLINK)
727                 error(ELOOP, "can't open a symlink");
728         tree_file_perm_check(tf, omode);
729         /* TODO: if we want to support DMEXCL on dir.mode, we'll need to lock/sync
730          * on the fs_file (have a flag for FSF_IS_OPEN, handle in close).  We'll
731          * also need a way to pass it in to the dir.mode during create/wstat/etc. */
732         if (omode & O_TRUNC)
733                 fs_file_truncate(&tf->file, 0);
734         c->mode = openmode(omode);
735         c->flag |= COPEN;
736         c->offset = 0;
737         return c;
738 }
739
740 void tree_chan_close(struct chan *c)
741 {
742         struct tree_file *tf = chan_to_tree_file(c);
743
744         tf_kref_put(tf);
745 }
746
747 void tree_file_remove(struct tree_file *child)
748 {
749         ERRSTACK(1);
750         struct tree_file *parent;
751
752         parent = get_locked_and_kreffed_parent(child);
753         if (!parent)
754                 error(ENOENT, "%s had no parent", tree_file_to_name(child));
755         if (waserror()) {
756                 qunlock(&parent->file.qlock);
757                 tf_kref_put(parent);
758                 nexterror();
759         }
760         if (!caller_has_tf_perms(parent, O_WRITE))
761                 error(EACCES, "missing remove perm for dir");
762         __unlink_child(parent, child);
763         __set_acmtime(&parent->file, FSF_CTIME | FSF_MTIME);
764         poperror();
765         qunlock(&parent->file.qlock);
766         tf_kref_put(parent);
767 }
768
769 void tree_chan_remove(struct chan *c)
770 {
771         ERRSTACK(1);
772         struct tree_file *tf = chan_to_tree_file(c);
773
774         /* sysremove expects a chan that is disconnected from the device, regardless
775          * of whether or not we fail.  See sysremove(); it will clear type, ensuring
776          * our close is never called. */
777         if (waserror()) {
778                 chan_set_tree_file(c, NULL);
779                 tf_kref_put(tf);        /* The ref from the original walk */
780                 nexterror();
781         }
782         tree_file_remove(tf);
783         chan_set_tree_file(c, NULL);
784         tf_kref_put(tf);        /* The ref from the original walk */
785         poperror();
786 }
787
788 static bool is_descendant_of(struct tree_file *descendant,
789                              struct tree_file *ancestor)
790 {
791         if (!tree_file_is_dir(ancestor))
792                 return false;
793         rcu_read_lock();
794         for (struct tree_file *i = rcu_dereference(descendant->parent);
795              i;
796              i = rcu_dereference(i->parent)) {
797                 if (i == ancestor) {
798                         rcu_read_unlock();
799                         return true;
800                 }
801         }
802         rcu_read_unlock();
803         return false;
804 }
805
806 /* Caller should hold the rename mutex.  This qlocks a and b, which can be the
807  * same file, and this handles lock ordering.  Recall the rule: parents before
808  * children, and otherwise only the renamer can lock. */
809 static void qlock_tree_files(struct tree_file *a, struct tree_file *b)
810 {
811         if (a == b) {
812                 qlock(&a->file.qlock);
813                 return;
814         }
815         if (is_descendant_of(a, b)) {
816                 qlock(&b->file.qlock);
817                 qlock(&a->file.qlock);
818         } else {
819                 qlock(&a->file.qlock);
820                 qlock(&b->file.qlock);
821         }
822 }
823
824 static void qunlock_tree_files(struct tree_file *a, struct tree_file *b)
825 {
826         if (a != b)
827                 qunlock(&a->file.qlock);
828         qunlock(&b->file.qlock);
829 }
830
831 /* Higher layers (namec) ensure that tf and new_parent are in the same device.
832  * The device (e.g. #mnt) ensures that they are in the same instance.
833  * new_parent could be the parent of tf; everything should still work if the
834  * move is within the same directory. */
835 void tree_file_rename(struct tree_file *tf, struct tree_file *new_parent,
836                       const char *name, int flags)
837 {
838         ERRSTACK(1);
839         struct tree_file *old_parent;
840         struct tree_file *prev_dst;
841         struct timespec now;
842
843         old_parent = __tf_get_potential_parent(tf);
844         if (!old_parent)
845                 error(ENOENT, "renamed file had no parent");
846         /* global mtx helps with a variety of weird races, including the "can't move
847          * to a subdirectory of yourself" case and the lock ordering of parents
848          * (locks flow from parent->child). */
849         qlock(&tf->tfs->rename_mtx);
850         qlock_tree_files(old_parent, new_parent);
851         if (waserror()) {
852                 qunlock_tree_files(old_parent, new_parent);
853                 qunlock(&tf->tfs->rename_mtx);
854                 tf_kref_put(old_parent);
855                 nexterror();
856         };
857         if (old_parent != tf->parent)
858                 error(ENOENT, "renamed file lost its parent");
859         /* Probably a namec bug (that code isn't written yet). */
860         assert(tree_file_is_dir(new_parent));
861         if (!new_parent->can_have_children)
862                 error(ENOENT, "target dir being removed");
863         if (!caller_has_tf_perms(old_parent, O_WRITE))
864                 error(EACCES, "missing remove perm for src dir");
865         if (!caller_has_tf_perms(new_parent, O_WRITE))
866                 error(EACCES, "missing create perm for dst dir");
867         /* can't move tf to one of its subdirs */
868         if (is_descendant_of(new_parent, tf))
869                 error(EINVAL, "can't rename to a child directory");
870         /* We hold new_parent's qlock, so there's no worry about prev_dst
871          * disappearing, so no need for an rcu read lock. */
872         prev_dst = wc_lookup_child(new_parent, name);
873         if (prev_dst) {
874                 if (tree_file_is_dir(prev_dst)) {
875                         if (!tree_file_is_dir(tf))
876                                 error(EISDIR, "can't rename a file onto a dir");
877                         /* We need to ensure prev_dst is childless and remains so.  That
878                          * requires grabbing its qlock, but there's a potential lock
879                          * ordering issue with old_parent.  We could have this:
880                          * new_parent/dst/x/y/z/old_parent/src.  That will fail, but we need
881                          * to check for that case instead of grabbing prev_dst's qlock. */
882                         if (is_descendant_of(prev_dst, old_parent))
883                                 error(ENOTEMPTY, "old_parent descends from dst");
884                         neuter_directory(prev_dst);
885                 } else {
886                         if (tree_file_is_dir(tf))
887                                 error(ENOTDIR, "can't rename a dir onto a file");
888                 }
889         }
890         /* We check with the backend first, so that it has a chance to fail early.
891          * Once we make the changes to the front end, lookups can see the effects of
892          * the change, which we can't roll back.  Since we hold the parents' qlocks,
893          * no one should be able to get the info from the backend either (lookups
894          * that require the backend, readdir, etc). */
895         tf->tfs->tf_ops.rename(tf, old_parent, new_parent, name, flags);
896         /* Similar to __disconnect_child, we don't clear tf->parent.  rcu readers at
897          * TF will be able to walk up (with ..).  Same with namec_from an FD.  If we
898          * atomically replace tf->parent, we should be good.  See tree_file_walk().
899          *
900          * Further, we don't mark the tf disconnected.  Someone might lookup from
901          * the old location, and that's fine.  We just don't want issues with
902          * decrefs. */
903         __remove_from_parent_list(old_parent, tf);
904         wc_remove_child(old_parent, tf);
905         synchronize_rcu();
906         /* Now, no new lookups will find it at the old location.  That change is not
907          * atomic wrt src, but it will be wrt dst.  Importantly, no one will see
908          * /path/to/old_parent/new_basename */
909         fs_file_change_basename((struct fs_file*)tf, name);
910         /* We're clobbering the old_parent ref, which we'll drop later */
911         rcu_assign_pointer(tf->parent, new_parent);
912         kref_get(&new_parent->kref, 1);
913         __add_to_parent_list(new_parent, tf);
914         wc_insert_child(new_parent, tf);
915         /* Now both the prev_dst (if it existed) or the tf file are in the walk
916          * cache / HT and either could have been looked up by a concurrent reader.
917          * Readers will always get one or the other, but never see nothing.  This is
918          * the atomic guarantee of rename. */
919         if (prev_dst) {
920                 __remove_from_parent_list(new_parent, prev_dst);
921                 wc_remove_child(new_parent, prev_dst);
922                 synchronize_rcu();
923                 /* Now no one can find prev_dst.  Someone might still have a ref, or it
924                  * might be on the LRU list (if kref == 0).  Now we can mark
925                  * disconnected.  Had we disconnected earlier, then lookup code would
926                  * see that and treat it as a failure.  Using rcu and putting the
927                  * complexity in rename was easier and simpler than changing lookup.
928                  *
929                  * We still need RCU here for freeing the prev_dst.  We could have had
930                  * an LRU pruner, etc, looking.  The synchronize_rcu above only dealt
931                  * with lookups via parent in this function. */
932                 if (__mark_disconnected(prev_dst))
933                         call_rcu(&prev_dst->rcu, __tf_free_rcu);
934         }
935         now = nsec2timespec(epoch_nsec());
936         __set_acmtime_to(&old_parent->file, FSF_CTIME | FSF_MTIME, &now);
937         __set_acmtime_to(&new_parent->file, FSF_CTIME | FSF_MTIME, &now);
938         /* Can we unlock earlier?  No.  We need to at least hold new_parent's qlock,
939          * which was the parent of old_dst, until old_dst is marked disconnected.
940          * Even though old_dst is removed from new_parent's HT, it is still in the
941          * LRU list. */
942         qunlock_tree_files(old_parent, new_parent);
943         qunlock(&tf->tfs->rename_mtx);
944         poperror();
945         tf_kref_put(old_parent);        /* the original tf->parent ref we clobbered */
946         tf_kref_put(old_parent);        /* the one we grabbed when we started */
947 }
948
949 void tree_chan_rename(struct chan *c, struct chan *new_p_c, const char *name,
950                       int flags)
951 {
952         struct tree_file *tf = chan_to_tree_file(c);
953         struct tree_file *new_parent = chan_to_tree_file(new_p_c);
954
955         tree_file_rename(tf, new_parent, name, flags);
956 }
957
958 /* dri is a pointer to the chan->dri, which is a count of how many directory
959  * entries that have been read from this chan so far.  9ns handles it; we just
960  * need to increment it for every successful entry.  Note we ignore offset. */
961 ssize_t tree_file_readdir(struct tree_file *parent, void *ubuf, size_t n,
962                           off64_t offset, int *dri)
963 {
964         ERRSTACK(1);
965         struct tree_file *i;
966         size_t dir_amt, so_far = 0;
967         uint8_t *write_pos = ubuf;
968         int child_nr = 0;
969
970         qlock(&parent->file.qlock);
971         if (waserror()) {
972                 qunlock(&parent->file.qlock);
973                 nexterror();
974         }
975         list_for_each_entry(i, &parent->children, siblings) {
976                 if (child_nr++ < *dri)
977                         continue;
978                 qlock(&i->file.qlock);
979                 dir_amt = convD2M(&i->file.dir, write_pos, n - so_far);
980                 qunlock(&i->file.qlock);
981                 if (dir_amt <= BIT16SZ) {
982                         if (!so_far)
983                                 error(EINVAL, "buffer to small for readdir");
984                         break;
985                 }
986                 write_pos += dir_amt;
987                 so_far += dir_amt;
988                 assert(n - so_far >= 0);
989                 (*dri)++;
990         }
991         /* If we care about directory atime, we can do that here. (if so_far) */
992         qunlock(&parent->file.qlock);
993         poperror();
994         return so_far;
995 }
996
997 /* Note this only works for backend-less TFSs.  It calls tree_file_readdir,
998  * which only looks at the frontend's tree. */
999 size_t tree_chan_read(struct chan *c, void *ubuf, size_t n, off64_t offset)
1000 {
1001         struct tree_file *tf = chan_to_tree_file(c);
1002
1003         if (tree_file_is_dir(tf))
1004                 return tree_file_readdir(tf, ubuf, n, offset, &c->dri);
1005         return fs_file_read(&tf->file, ubuf, n, offset);
1006 }
1007
1008 size_t tree_chan_write(struct chan *c, void *ubuf, size_t n, off64_t offset)
1009 {
1010         struct tree_file *tf = chan_to_tree_file(c);
1011
1012         /* sysfile.c:rwrite checked the chan's type. */
1013         assert(!tree_file_is_dir(tf));
1014         return fs_file_write(&tf->file, ubuf, n, offset);
1015 }
1016
1017 size_t tree_chan_stat(struct chan *c, uint8_t *m_buf, size_t m_buf_sz)
1018 {
1019         struct tree_file *tf = chan_to_tree_file(c);
1020
1021         return fs_file_stat(&tf->file, m_buf, m_buf_sz);
1022 }
1023
1024 size_t tree_chan_wstat(struct chan *c, uint8_t *m_buf, size_t m_buf_sz)
1025 {
1026         struct tree_file *tf = chan_to_tree_file(c);
1027
1028         return fs_file_wstat(&tf->file, m_buf, m_buf_sz);
1029 }
1030
1031 struct fs_file *tree_chan_mmap(struct chan *c, struct vm_region *vmr, int prot,
1032                                int flags)
1033 {
1034         struct fs_file *f = &chan_to_tree_file(c)->file;
1035
1036         /* TODO: In the future, we'll check the prot, establish hooks with the VMR,
1037          * and other things, mostly in something like fs_file_mmap, which will be
1038          * able to handle mmaping something that doesn't use the page cache.  For
1039          * now, I'm aggressively qlocking to catch bugs. */
1040         qlock(&f->qlock);
1041         if ((prot & PROT_WRITE) && (flags & MAP_SHARED))
1042                 f->flags |= FSF_DIRTY;
1043         qunlock(&f->qlock);
1044         return f;
1045 }
1046
1047 unsigned long tree_chan_ctl(struct chan *c, int op, unsigned long a1,
1048                             unsigned long a2, unsigned long a3,
1049                             unsigned long a4)
1050 {
1051         switch (op) {
1052         default:
1053                 error(EINVAL, "%s does not support chanctl %d", chan_dev_name(c), op);
1054         }
1055 }
1056
1057 /* Given a tree file, construct a chan that points to the TF for the given
1058  * device.  Careful with this - it's for bootstrapping. */
1059 struct chan *tree_file_alloc_chan(struct tree_file *tf, struct dev *dev,
1060                                   char *name)
1061 {
1062         struct chan *c;
1063
1064         c = newchan();
1065         c->type = dev - devtab;
1066         c->name = newcname(name);
1067         kref_get(&tf->kref, 1);
1068         chan_set_tree_file(c, tf);
1069         c->qid = tree_file_to_qid(tf);
1070         return c;
1071 }
1072
1073 /* Caller needs to set its customizable fields: tf_ops, pm_ops, etc.  root is
1074  * created with a ref of 1, but needs filled in by the particular TFS. */
1075 void tfs_init(struct tree_filesystem *tfs)
1076 {
1077         wc_init(&tfs->wc);
1078         qlock_init(&tfs->rename_mtx);
1079         tfs->root = tree_file_alloc(tfs, NULL, ".");
1080         tfs->root->flags |= TF_F_IS_ROOT;
1081         assert(!(tfs->root->flags & TF_F_ON_LRU));
1082         __kref_get(&tfs->root->kref, 1);
1083 }
1084
1085 void tfs_destroy(struct tree_filesystem *tfs)
1086 {
1087         tfs->root = NULL;       /* was just freed in __tf_free() */
1088         wc_destroy(&tfs->wc);
1089 }
1090
1091 /* For every file except root, we hold our parent's qlock (root has no parent).
1092  * This prevents TF's removal/rename and any changes to tf->parent. */
1093 static void tf_dfs_cb(struct tree_file *tf, void (*cb)(struct tree_file *tf))
1094 {
1095         struct tree_file *child;
1096
1097         if (tree_file_is_dir(tf)) {
1098                 qlock(&tf->file.qlock);
1099                 /* Note we don't have a kref on our child's TF - we have a weak
1100                  * reference (the list membership).  We hold the parent's qlock, which
1101                  * prevents removal/unlinking/disconnecting/etc.  The child's membership
1102                  * on the LRU list can change repeatedly.
1103                  *
1104                  * If we want to avoid holding the parent's qlock, we could grab a kref
1105                  * on the child.  However, our list walk would be in jeopardy - both
1106                  * child and temp could be removed from the list.  So we'd need to qlock
1107                  * the parent, grab krefs on all children, and put them on a local list.
1108                  * Also, grabbing krefs on our children will muck with the LRU list;
1109                  * when we're done, it would be like we sorted the LRU list in the DFS
1110                  * order. */
1111                 list_for_each_entry(child, &tf->children, siblings)
1112                         tf_dfs_cb(child, cb);
1113                 qunlock(&tf->file.qlock);
1114         }
1115         if (!tree_file_is_negative(tf))
1116                 cb(tf);
1117 }
1118
1119 /* Runs CB on all in-memory, non-negative TFs from the TFS in a depth-first
1120  * search.  Compared to the other CB walkers (purge, LRU, etc), this never
1121  * removes/prunes/disconnects a TF from the tree.  You can use it for syncing FS
1122  * trees or pruning page maps (i.e. discarding non-dirty pages).
1123  *
1124  * One thing to note is that it qlocks the tree as part of its DFS.  We can
1125  * change that, but at a slight cost in complexity and tampering with the LRU
1126  * list.  Translation: we can do it if there's a performance problem.
1127  *
1128  * The tfs->root reference is also weak.  It's up to the user to make sure
1129  * there is no concurrent tfs_destroy.  Typically, if we're called on any
1130  * mounted device, we're fine (e.g. #tmpfs) or a device that is never destroyed
1131  * (e.g. #kfs). */
1132 void tfs_frontend_for_each(struct tree_filesystem *tfs,
1133                            void (*cb)(struct tree_file *tf))
1134 {
1135         tf_dfs_cb(tfs->root, cb);
1136 }
1137
1138 /* We should be single-user, so no need for concurrency protections.  I keep
1139  * them around for paranoia/future use/documentation. */
1140 static void tf_dfs_purge(struct tree_file *tf, void (*cb)(struct tree_file *tf))
1141 {
1142         struct tree_file *child, *temp;
1143
1144         if (tree_file_is_dir(tf)) {
1145                 qlock(&tf->file.qlock);
1146                 /* Note we don't have a kref on TF, and one of our children should
1147                  * decref *us* to 0.  We aren't disconnected yet, and we can't be
1148                  * removed (parent's qlock is held), so we'll just end up on the LRU
1149                  * list, which is OK.
1150                  *
1151                  * Our child should remove itself from our list, so we need the _safe.
1152                  *
1153                  * Also note that the child decrefs us in a call_rcu.  CB can block, and
1154                  * technically so can qlock, so we might run RCU callbacks while
1155                  * qlocked.  We'll need to rcu_barrier so that our children's decrefs
1156                  * occur before we remove ourselves from our parent. */
1157                 list_for_each_entry_safe(child, temp, &tf->children, siblings)
1158                         tf_dfs_purge(child, cb);
1159                 qunlock(&tf->file.qlock);
1160         }
1161         rcu_barrier();
1162         /* ramfs will drop the "+1 for existing" ref here */
1163         if (!tree_file_is_negative(tf))
1164                 cb(tf);
1165         spin_lock(&tf->lifetime);
1166         /* should be unused, with no children.  we have a ref on root, to keep the
1167          * TFS around while we destroy the tree. */
1168         assert(kref_refcnt(&tf->kref) == 0 || tree_file_is_root(tf));
1169         /* This mark prevents new lookups.  We'll disconnect it shortly. */
1170         tf->flags |= TF_F_DISCONNECTED;
1171         spin_unlock(&tf->lifetime);
1172         if (tf->parent)
1173                 __disconnect_child(tf->parent, tf);
1174 }
1175
1176 /* Purges all in-memory TFs from the TFS in a depth-first search, both positive
1177  * and negative.  We run CB on all non-negative TFs.  It's up to the caller to
1178  * ensure there is no concurrency.
1179  *
1180  * The caller must make sure they have an extra ref on tfs->root to keep the
1181  * TFS around while it gets destroyed.  The root TF will get freed when it is
1182  * released, unlike other TFs that are still connected.
1183  *
1184  * This is for devices that want to destroy themselves, such as an unmounted
1185  * #tmpfs or #gtfs/#mnt, that want to do some extra work (e.g. sync).
1186  * Typically, those devices will call this after they have no users (e.g. mounts
1187  * or open chans). */
1188 void tfs_frontend_purge(struct tree_filesystem *tfs,
1189                         void (*cb)(struct tree_file *tf))
1190 {
1191         assert(kref_refcnt(&tfs->root->kref) > 0);
1192         tf_dfs_purge(tfs->root, cb);
1193 }
1194
1195 static void print_tf(struct tree_file *tf)
1196 {
1197         if (tree_file_is_negative(tf)) {
1198                 printk("%-10s: Negative\n", tree_file_to_name(tf));
1199                 return;
1200         }
1201         printk("%-10s: Q: %5d, R: %2d, U %s, %c%o %s\n",
1202                    tree_file_to_name(tf),
1203                    tf->file.dir.qid.path,
1204                    kref_refcnt(&tf->kref),
1205                    tf->file.dir.uid,
1206                    tree_file_is_dir(tf) ? 'd' :
1207                                                                 tf->file.dir.mode & DMSYMLINK ? 'l' : '-',
1208                    tf->file.dir.mode & S_PMASK,
1209                    tf->file.dir.mode & DMSYMLINK ? tf->file.dir.ext : ""
1210                    );
1211 }
1212
1213 static void dump_tf(struct tree_file *tf, int tabs)
1214 {
1215         struct tree_file *child;
1216
1217         if (!!(tf->file.dir.mode & DMSYMLINK) !=
1218             !!(tf->file.dir.qid.type & QTSYMLINK))
1219                 warn("%s has differing symlink bits", tree_file_to_name(tf));
1220
1221         print_lock();
1222         for (int i = 0; i < tabs; i++)
1223                 printk("    ");
1224         print_tf(tf);
1225         if (tree_file_is_dir(tf)) {
1226                 for (int i = 0; i < tabs; i++)
1227                         printk("    ");
1228                 printk("---------------------\n");
1229                 list_for_each_entry(child, &tf->children, siblings)
1230                         dump_tf(child, tabs + 1);
1231         }
1232         print_unlock();
1233 }
1234
1235 void __tfs_dump(struct tree_filesystem *tfs)
1236 {
1237         dump_tf(tfs->root, 0);
1238 }
1239
1240 /* Runs a callback on every non-negative TF on the LRU list, for a given
1241  * snapshot of the LRU list.  The CB returns true if it wants us to attempt to
1242  * free the TF.  One invariant is that we can never remove a TF from the tree
1243  * while it is dirty; it is the job of the CB to maintain that.  Note the CB can
1244  * run on a TF as soon as that TF was linked to the parent (see lookup).
1245  *
1246  * The work list is a list of strong refs.  We need to keep one in case the file
1247  * is disconnected while we're running our CBs.  Since we incref, we yank from
1248  * the LRU list.  We could design the rest of the TF code so that we stay on the
1249  * LRU list throughout, but I like the invariant of "kref == 0 IFF on LRU".
1250  *
1251  * Since we're only on one list at a time ('wc->lru' or 'work'), we can use the
1252  * lru list_head in the TF.  We know that so long as we hold our kref on a TF,
1253  * no one will attempt to put it back on the LRU list. */
1254 void tfs_lru_for_each(struct tree_filesystem *tfs, bool cb(struct tree_file *),
1255                       size_t max_tfs)
1256 {
1257         struct list_head work = LIST_HEAD_INIT(work);
1258         struct walk_cache *wc = &tfs->wc;
1259         struct tree_file *tf, *temp, *parent;
1260         size_t nr_tfs = 0;
1261
1262         /* We can have multiple LRU workers in flight, though a given TF will be on
1263          * only one CB list at a time. */
1264         spin_lock(&wc->lru_lock);
1265         list_for_each_entry_safe(tf, temp, &wc->lru, lru) {
1266                 /* lockless peak at the flag.  once it's NEGATIVE, it never goes back */
1267                 if (tree_file_is_negative(tf))
1268                         continue;
1269                 /* Normal lock order is TF -> LRU.  Best effort is fine for LRU. */
1270                 if (!spin_trylock(&tf->lifetime))
1271                         continue;
1272                 /* Can't be disconnected and on LRU */
1273                 assert(!(tf->flags & TF_F_DISCONNECTED));
1274                 assert((tf->flags & TF_F_ON_LRU));
1275                 tf->flags &= ~TF_F_ON_LRU;
1276                 list_del(&tf->lru);
1277                 __kref_get(&tf->kref, 1);
1278                 /* The 'used' bit is the what allows us to detect a user in between our
1279                  * callback and the disconnection/freeing.  It's a moot point if the CB
1280                  * returns false. */
1281                 tf->flags &= ~TF_F_HAS_BEEN_USED;
1282                 spin_unlock(&tf->lifetime);
1283                 list_add_tail(&tf->lru, &work);
1284                 if (++nr_tfs >= max_tfs)
1285                         break;
1286         }
1287         spin_unlock(&wc->lru_lock);
1288
1289         /* We have a snapshot of the LRU list.  As soon as we unlocked a file,
1290          * someone could incref it (e.g. to something > 1), and they'll set the used
1291          * bit.  That won't abort the CB.  New TFs could be added to the LRU list.
1292          * Those are ignored for this pass. */
1293         list_for_each_entry_safe(tf, temp, &work, lru) {
1294                 if (!cb(tf)) {
1295                         list_del(&tf->lru);
1296                         tf_kref_put(tf);
1297                         continue;
1298                 }
1299         }
1300
1301         /* Now we have a list of victims to be removed, so long as they haven't been
1302          * used since. */
1303         list_for_each_entry_safe(tf, temp, &work, lru) {
1304                 parent = get_locked_and_kreffed_parent(tf);
1305                 if (!parent) {
1306                         list_del(&tf->lru);
1307                         tf_kref_put(tf);
1308                         continue;
1309                 }
1310                 spin_lock(&tf->lifetime);
1311                 if (tf->flags & TF_F_HAS_BEEN_USED) {
1312                         spin_unlock(&tf->lifetime);
1313                         qunlock(&parent->file.qlock);
1314                         tf_kref_put(parent);
1315                         list_del(&tf->lru);
1316                         tf_kref_put(tf);
1317                         continue;
1318                 }
1319                 tf->flags |= TF_F_DISCONNECTED;
1320                 /* We hold a ref, so it shouldn't have found its way back on LRU */
1321                 assert(!(tf->flags & TF_F_ON_LRU));
1322                 spin_unlock(&tf->lifetime);
1323                 __remove_from_parent_list(parent, tf);
1324                 wc_remove_child(parent, tf);
1325                 /* If we get tired of unlocking and relocking, we could see if the next
1326                  * parent is the current parent before unlocking. */
1327                 qunlock(&parent->file.qlock);
1328                 tf_kref_put(parent);
1329         }
1330         /* Now we have a list of refs that are all disconnected, kref == 1 (because
1331          * no one used them since we increffed them when they were LRU, which was
1332          * when the refcnt was 0).  Each TF has a ref on its parent btw, so parents
1333          * will never be on the LRU list.  (leaves only).
1334          *
1335          * We need to synchronize_rcu() too, since we could have had lockless
1336          * lookups that have pointers to TF and are waiting to notice that it is
1337          * disconnected. */
1338         synchronize_rcu();
1339         list_for_each_entry_safe(tf, temp, &work, lru) {
1340                 assert(kref_refcnt(&tf->kref) == 1);
1341                 list_del(&tf->lru);
1342                 /* We could decref, but instead we can directly free.  We know the ref
1343                  * == 1 and it is disconnected.  Directly freeing bypasses call_rcu. */
1344                 __tf_free(tf);
1345         }
1346 }
1347
1348 /* Does a one-cycle 'clock' algorithm to detect use.  On a given pass, we either
1349  * clear HAS_BEEN_USED xor we remove it.  For negative entries, that bit is used
1350  * when we look at an entry (use it), compared to positive entries, which is
1351  * used when we get a reference.  (we never get refs on negatives). */
1352 void tfs_lru_prune_neg(struct tree_filesystem *tfs)
1353 {
1354         struct list_head work = LIST_HEAD_INIT(work);
1355         struct walk_cache *wc = &tfs->wc;
1356         struct tree_file *tf, *temp, *parent;
1357
1358         spin_lock(&wc->lru_lock);
1359         list_for_each_entry_safe(tf, temp, &wc->lru, lru) {
1360                 if (!tree_file_is_negative(tf))
1361                         continue;
1362                 if (!spin_trylock(&tf->lifetime))
1363                         continue;
1364                 if (tf->flags & TF_F_HAS_BEEN_USED) {
1365                         tf->flags &= ~TF_F_HAS_BEEN_USED;
1366                         spin_unlock(&tf->lifetime);
1367                         continue;
1368                 }
1369                 rcu_read_lock();        /* holding a spinlock, but just to be clear. */
1370                 parent = rcu_dereference(tf->parent);
1371                 /* Again, inverting the lock order, so best effort trylock */
1372                 if (!canqlock(&parent->file.qlock)) {
1373                         rcu_read_unlock();
1374                         spin_unlock(&tf->lifetime);
1375                         continue;
1376                 }
1377                 __remove_from_parent_list(parent, tf);
1378                 wc_remove_child(parent, tf);
1379                 qunlock(&parent->file.qlock);
1380                 /* We're off the list, but our kref == 0 still.  We can break that
1381                  * invariant since we have the only ref and are about to free the TF. */
1382                 tf->flags &= ~TF_F_ON_LRU;
1383                 list_del(&tf->lru);
1384                 spin_unlock(&tf->lifetime);
1385                 list_add_tail(&tf->lru, &work);
1386         }
1387         spin_unlock(&wc->lru_lock);
1388         /* Now we have a list of refs that are all unlinked (but actually not
1389          * flagged DISCONNECTED; that's only necessary for positives), kref == 0
1390          * (because they are negatives).
1391          *
1392          * We need to synchronize_rcu() too, since we could have had lockless
1393          * lookups that have pointers to TF, and they may even mark HAS_BEEN_USED.
1394          * Too late. */
1395         synchronize_rcu();
1396         list_for_each_entry_safe(tf, temp, &work, lru) {
1397                 assert(kref_refcnt(&tf->kref) == 0);
1398                 list_del(&tf->lru);
1399                 __tf_free(tf);
1400         }
1401 }