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