vmm: refactor userspace's emsr_fakewrite()
[akaros.git] / kern / include / radix.h
1 /* Copyright (c) 2010 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Radix Tree, modeled after Linux's (described here:
6  * http://lwn.net/Articles/175432/).
7  *
8  * It maps unsigned longs to void*s, growing the depth of the tree as needed to
9  * handle more items.  It won't allow the insertion of existing keys, and it
10  * can fail due to lack of memory.
11  *
12  * There are some utility functions, probably unimplemented til we need them,
13  * that will make the tree have enough memory for future calls.
14  *
15  * You can also store a tag along with the void* for a given item, and do
16  * lookups based on those tags.  Or you will be able to, once it is
17  * implemented. */
18
19 #pragma once
20
21 #define LOG_RNODE_SLOTS 6
22 #define NR_RNODE_SLOTS (1 << LOG_RNODE_SLOTS)
23
24 #include <ros/common.h>
25 #include <kthread.h>
26 #include <atomic.h>
27 #include <rcu.h>
28
29 struct radix_node {
30         struct rcu_head                 rcu;
31         void                            *items[NR_RNODE_SLOTS];
32         unsigned int                    num_items;
33         bool                            leaf;
34         struct radix_node               *parent;
35         struct radix_node               **my_slot;
36 };
37
38 /* writers (insert, delete, and callbacks) must synchronize externally, e.g. a
39  * qlock in the pagemap.
40  *
41  * radix_lookup_slot returns an rcu-protected pointer that needs to be
42  * rcu_read_locked.  The item in the slot (either by *slot or by a regular
43  * radix_lookup) has limited protections.  Higher layers (pagemap) can do their
44  * own thing.  For instance, the page cache writers can zero an item if they
45  * know they cleared the page without someone else grabbing a ref.  We'll
46  * rcu-protect the item pointer, so that higher layers can use RCU for the
47  * actual object.
48  *
49  * Basically the only functions that don't need the caller to hold a qlock are
50  * the two lookup routines: the readers.  The seq counter protects the atomicity
51  * of root, depth, and upper_bound, which defines the reader's start point.  RCU
52  * protects the lifetime of the rnodes, which is where lookup_slot's pointer
53  * points to.
54  *
55  * Note that we use rcu_assign_pointer and rcu_dereference whenever we
56  * manipulate pointers in the tree (pointers to or within rnodes).  We use RCU
57  * for the item pointer too, so that our callers can use RCU if they want.  Both
58  * the slot pointer and what it points to are protected by RCU.
59  */
60 struct radix_tree {
61         seq_ctr_t                       seq;
62         struct radix_node               *root;
63         unsigned int                    depth;
64         unsigned long                   upper_bound;
65 };
66
67 void radix_init(void);          /* initializes the whole radix system */
68 void radix_tree_init(struct radix_tree *tree);  /* inits one tree */
69 void radix_tree_destroy(struct radix_tree *tree);
70
71 /* Item management */
72 int radix_insert(struct radix_tree *tree, unsigned long key, void *item,
73                  void ***slot_p);
74 void *radix_delete(struct radix_tree *tree, unsigned long key);
75 void *radix_lookup(struct radix_tree *tree, unsigned long key);
76 void **radix_lookup_slot(struct radix_tree *tree, unsigned long key);
77
78 typedef bool (*radix_cb_t)(void **slot, unsigned long tree_idx, void *arg);
79 void radix_for_each_slot(struct radix_tree *tree, radix_cb_t cb, void *arg);
80 /* [start_idx, end_idx) */
81 void radix_for_each_slot_in_range(struct radix_tree *tree,
82                                   unsigned long start_idx,
83                                   unsigned long end_idx,
84                                   radix_cb_t cb, void *arg);
85
86 /* Memory management */
87 int radix_grow(struct radix_tree *tree, unsigned long max);
88 int radix_preload(struct radix_tree *tree, int flags);
89
90 /* Tag management */
91 void *radix_tag_set(struct radix_tree *tree, unsigned long key, int tag);
92 void *radix_tag_clear(struct radix_tree *tree, unsigned long key, int tag);
93 int radix_tag_get(struct radix_tree *tree, unsigned long key, int tag);
94 int radix_tree_tagged(struct radix_tree *tree, int tag);
95 int radix_tag_gang_lookup(struct radix_tree *tree, void **results,
96                           unsigned long first, unsigned int max_items, int tag);
97
98 /* Debugging */
99 void print_radix_tree(struct radix_tree *tree);