vmm: refactor userspace's emsr_fakewrite()
[akaros.git] / kern / include / tree_file.h
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 to for a tree-based filesystem for 9ns
6  * devices.
7  */
8
9 #pragma once
10
11 #include <fs_file.h>
12 #include <ns.h>
13 #include <list.h>
14 #include <rcu.h>
15
16 struct tree_file;
17 struct tree_filesystem;
18
19 /* The walk cache encapsulates a couple things related to caching, similar to
20  * the dentry cache in the VFS.
21  * - the parent -> child links in a hash table
22  * - the LRU list, consisting of all tree files with kref == 0
23  *
24  * LRU notes.  Once a TF gets linked into a tree:
25  * - a TF is on the LRU IFF its refcnt == 0
26  * - a TF is on the LRU only if it is in the tree
27  * - any time kref gets set to 0, we consider putting it on the LRU (if not
28  *   DISCONNECTED / in the tree).  anytime it is increffed from 0, we yank it.
29  * - NEG entries are always kref == 0, and are on the LRU list if they are in
30  *   the tree.  They are never increffed, only rcu-read.
31  */
32 struct walk_cache {
33         spinlock_t                      lru_lock;
34         struct list_head                lru;
35         spinlock_t                      ht_lock;
36         struct hash_helper              hh;             /* parts are rcu-read */
37         struct hlist_head               *ht;
38         struct hlist_head               static_ht[HASH_INIT_SZ];
39 };
40
41 /* All ops that operate on a parent have the parent qlocked.
42  *
43  * free(): the TF is being freed.  Might be called on TFs that the TFS is
44  * unaware of (e.g. lookup threw an error).
45  *
46  * unlink(): child is being unlinked from the parent.
47  *
48  * lookup(): backends fill in the child TF with whatever it knows about the
49  * entry.  This function is optional.  TFSs whose entire tree is in the frontend
50  * (e.g.  ramfs) don't do lookups from the non-existent backend.  This
51  * structure, positive or negative, will be used until it is unlinked.
52  *
53  * create(): given parent and it's initialized child struct, create the file and
54  * do whatever else you need (e.g. 9p backend does the create).  Same as lookup,
55  * the TFS needs to fill in child->dir, except for name.  Note we don't pass
56  * omode.  That's handled in the device's front-end create: open the chan after
57  * creating.
58  *
59  * rename(): rename / move TF from the old_parent to the new_parent, and change
60  * the name to name (NULL == no change).  Note that the rename op does *not* set
61  * the TF's name yet.  Be careful changing any fields in the TF, since it is
62  * still in old_parent's HT.
63  *
64  * has_children(): TFSs that use the front end as a cache (e.g. #mnt) need to
65  * check with their backend to know if there are children or not.  Checking the
66  * children list isn't necessarily sufficient.
67  */
68 struct tree_file_ops {
69         void (*free)(struct tree_file *tf);
70         void (*unlink)(struct tree_file *parent, struct tree_file *child);
71         void (*lookup)(struct tree_file *parent, struct tree_file *child);
72         void (*create)(struct tree_file *parent, struct tree_file *child,
73                        int perm);
74         void (*rename)(struct tree_file *tf, struct tree_file *old_parent,
75                        struct tree_file *new_parent, const char *name,
76                        int flags);
77         bool (*has_children)(struct tree_file *parent);
78 };
79
80 struct tree_filesystem {
81         struct walk_cache               wc;
82         struct tree_file_ops            tf_ops;
83         struct fs_file_ops              fs_ops;
84         qlock_t                         rename_mtx;
85         struct tree_file                *root;
86         void                            *priv;
87 };
88
89 /* The tree_file is an fs_file (i.e. the first struct field) that exists in a
90  * tree filesystem with parent/child relationships.
91  *
92  * Children hold krefs on their parents.  Parents have weak refs (i.e. not a
93  * kref) on their children.  Parent's have a list of *known* children.  The
94  * backend of the FS (e.g. the other side of #mnt) may know of other children.
95  * In this way, the parent's list is a cache.  For devices like a ramfs or any
96  * dynamic, completely tree-based system (e.g. #srv), the tree filesystem is the
97  * authoritative FS; there is no backend.
98  *
99  * If we know of a parent-child relationship (i.e. it's in the tree_filesystem),
100  * then the following invariants are true:
101  * - The child is in the parent's list.
102  * - The child->parent == the parent's tree_file
103  * - There is an entry in the walk cache from {parent,name} -> child_tree_file.
104  * - The backend FS (if there is one) knows about the parent-child link
105  *
106  * To change these, hold the parent's qlock and you must change them all,
107  * with a slight exception: you must *set* child->parent = parent under the
108  * lock.  You may *clear* that reference (and decref the parent) outside the
109  * parent's qlock when freeing the child.  At this point, there are no
110  * references to child, it is off all lists and structures, and RCU readers are
111  * done.
112  *
113  * We'll need to make these changes for create, remove, rename, and lookup (add
114  * entries (positive or negative) that we didn't know about).  Note that even
115  * changing the basename, but not moving, a child during rename requires the
116  * parent's qlock.  (It changes the hashtable linkage).
117  *
118  * Keep in mind that the info in the frontend (tree_files) may be a subset of
119  * the real filesystem, which is the backend (e.g. 9p mount, disk structures,
120  * etc).  The frontend might not have everything from the backend, typically
121  * because of memory reclaim.
122  *
123  * Readers use the walk cache hash table and child->parent) with RCU read
124  * locks.  The linked list of children is only accessed under the parent's
125  * qlock.  If a child needs a ref on its parent, it will need to kref_get during
126  * rcu lock.  Children hold refs on parents, but a concurrent removal/rename
127  * could break that link and decref the parent.
128  *
129  * Synchronization rules
130  * ------------------
131  * Hold the lifetime spin lock when:
132  * - Changing or relying on the value of flags (e.g., during kcref upping)
133  * - Upping a kref from 0 during a lookup
134  * - Changing membership on LRU lists (e.g. during release or kcref upping)
135  *   The lock ordering is entry -> LRU list.  Note the LRU pruner will lock the
136  *   list first, then *trylock* the entry *and* the parent, skipping on failure.
137  *
138  * Refcounting rules: (subject to a device's whims)
139  * - All walked or attached chans (distinct; those that will be closed in the
140  *   device) have a refcounted tree_file.
141  * - The tree_files do not have to be in a lookup structure (parent's list /
142  *   hash table); they could have been unlinked/removed and waiting for the
143  *   final close.
144  * - tree_files can have 0 references.  Typically, files that are unopened
145  *   (technically, unwalked) will have their kref == 0.  On release, they can
146  *   stay in the tree/lookup system, and they are added to an LRU list.
147  * - negative tree_files (i.e. names for files that don't exist) always have a
148  *   refcnt == 0, and are candidates for being pruned at all times.
149  *
150  * Lock ordering:
151  * - Note the tree uses the qlock in the FS file.  In essence, they are the same
152  *   object (a tree_file is an fs_file).  This qlock is for changing the
153  *   contents of the file, whether that's the parent directories links to its
154  *   children, a file's contents (via write), or the metadata (dir) of either.
155  * - Parent qlock -> hash_table bucketlock
156  * - Parent qlock -> child lifetime spinlock -> LRU list spinlock
157  *   Note the LRU pruner inverts this ordering, and uses trylocks
158  * - Parent qlock -> child qlock (unlink and create/rename).
159  * - Qlocking multiple files that aren't parent->child requires the rename_mtx
160  */
161 struct tree_file {
162         struct fs_file                  file;
163         spinlock_t                      lifetime;
164         int                             flags;
165         struct kref                     kref;
166         struct rcu_head                 rcu;
167         struct tree_file                *parent;        /* rcu protected */
168         struct hlist_node               hash;           /* rcu protected */
169         struct list_head                siblings;
170         struct list_head                children;
171         struct list_head                lru;
172         bool                            can_have_children;
173         struct tree_filesystem          *tfs;
174 };
175
176 #define TF_F_DISCONNECTED       (1 << 0)
177 #define TF_F_NEGATIVE           (1 << 1)
178 #define TF_F_ON_LRU             (1 << 2)
179 #define TF_F_IS_ROOT            (1 << 3)
180 #define TF_F_HAS_BEEN_USED      (1 << 4)
181
182 /* Devices can put their tree_files / fs_files whereever they want.  For now,
183  * all of them will use aux.  We can make ops for this if we need it. */
184 static inline struct tree_file *chan_to_tree_file(struct chan *c)
185 {
186         return c->aux;
187 }
188
189 static inline void chan_set_tree_file(struct chan *c, struct tree_file *tf)
190 {
191         c->aux = tf;
192 }
193
194 static inline struct qid tree_file_to_qid(struct tree_file *tf)
195 {
196         return tf->file.dir.qid;
197 }
198
199 static inline bool tree_file_is_dir(struct tree_file *tf)
200 {
201         return tree_file_to_qid(tf).type & QTDIR ? true : false;
202 }
203
204 static inline bool tree_file_is_file(struct tree_file *tf)
205 {
206         return qid_is_file(tree_file_to_qid(tf));
207 }
208
209 static inline bool tree_file_is_symlink(struct tree_file *tf)
210 {
211         return tree_file_to_qid(tf).type & QTSYMLINK ? true : false;
212 }
213
214 static inline bool tree_file_is_negative(struct tree_file *tf)
215 {
216         return tf->flags & TF_F_NEGATIVE ? true : false;
217 }
218
219 static inline bool tree_file_is_root(struct tree_file *tf)
220 {
221         return tf == tf->tfs->root;
222 }
223
224 static inline char *tree_file_to_name(struct tree_file *tf)
225 {
226         return tf->file.dir.name;
227 }
228
229 static inline bool caller_has_tf_perms(struct tree_file *tf, int omode)
230 {
231         return caller_has_file_perms(&tf->file, omode);
232 }
233
234 static inline void tree_file_perm_check(struct tree_file *tf, int omode)
235 {
236         fs_file_perm_check(&tf->file, omode);
237 }
238
239 /* tree_file helpers */
240 bool tf_kref_get(struct tree_file *tf);
241 void tf_kref_put(struct tree_file *tf);
242 struct tree_file *tree_file_alloc(struct tree_filesystem *tfs,
243                                   struct tree_file *parent, const char *name);
244 struct walkqid *tree_file_walk(struct tree_file *from, char **name,
245                                unsigned int nname);
246 struct tree_file *tree_file_create(struct tree_file *parent, const char *name,
247                                    uint32_t perm, char *ext);
248 void tree_file_remove(struct tree_file *child);
249 void tree_file_rename(struct tree_file *tf, struct tree_file *new_parent,
250                       const char *name, int flags);
251 ssize_t tree_file_readdir(struct tree_file *parent, void *ubuf, size_t n,
252                           off64_t offset, int *dri);
253
254 /* tree_file helpers that operate on chans */
255 struct walkqid *tree_chan_walk(struct chan *c, struct chan *nc, char **name,
256                                unsigned int nname);
257 void tree_chan_create(struct chan *c, char *name, int omode, uint32_t perm,
258                       char *ext);
259 struct chan *tree_chan_open(struct chan *c, int omode);
260 void tree_chan_close(struct chan *c);
261 void tree_chan_remove(struct chan *c);
262 void tree_chan_rename(struct chan *c, struct chan *new_p_c, const char *name,
263                       int flags);
264 size_t tree_chan_read(struct chan *c, void *ubuf, size_t n, off64_t offset);
265 size_t tree_chan_write(struct chan *c, void *ubuf, size_t n, off64_t offset);
266 size_t tree_chan_stat(struct chan *c, uint8_t *m_buf, size_t m_buf_sz);
267 size_t tree_chan_wstat(struct chan *c, uint8_t *m_buf, size_t m_buf_sz);
268 struct fs_file *tree_chan_mmap(struct chan *c, struct vm_region *vmr, int prot,
269                                int flags);
270 unsigned long tree_chan_ctl(struct chan *c, int op, unsigned long a1,
271                             unsigned long a2, unsigned long a3,
272                             unsigned long a4);
273
274 struct chan *tree_file_alloc_chan(struct tree_file *tf, struct dev *dev,
275                                   char *name);
276 void tfs_init(struct tree_filesystem *tfs);
277 void tfs_destroy(struct tree_filesystem *tfs);
278 void tfs_frontend_for_each(struct tree_filesystem *tfs,
279                            void (*cb)(struct tree_file *tf));
280 void tfs_frontend_purge(struct tree_filesystem *tfs,
281                         void (*cb)(struct tree_file *tf));
282 void __tfs_dump(struct tree_filesystem *tfs);
283 void __tfs_dump_tf(struct tree_file *tf);
284
285 void tfs_lru_for_each(struct tree_filesystem *tfs, bool cb(struct tree_file *),
286                       size_t max_tfs);
287 void tfs_lru_prune_neg(struct tree_filesystem *tfs);