git: track the specific branch only
[akaros.git] / kern / include / radix.h
index 1fd3bea..c30f462 100644 (file)
  * lookups based on those tags.  Or you will be able to, once it is
  * implemented. */
 
-#ifndef ROS_KERN_RADIX_H
-#define ROS_KERN_RADIX_H
+#pragma once
 
 #define LOG_RNODE_SLOTS 6
 #define NR_RNODE_SLOTS (1 << LOG_RNODE_SLOTS)
 
 #include <ros/common.h>
+#include <kthread.h>
+#include <atomic.h>
+#include <rcu.h>
 
 struct radix_node {
-       void                                            *items[NR_RNODE_SLOTS];
-       unsigned int                            num_items;
-       bool                                            leaf;
-       struct radix_node                       *parent;
-       struct radix_node                       **my_slot;
+       struct rcu_head                 rcu;
+       void                            *items[NR_RNODE_SLOTS];
+       unsigned int                    num_items;
+       bool                            leaf;
+       struct radix_node               *parent;
+       struct radix_node               **my_slot;
 };
 
-/* Defines the whole tree. */
+/* writers (insert, delete, and callbacks) must synchronize externally, e.g. a
+ * qlock in the pagemap.
+ *
+ * radix_lookup_slot returns an rcu-protected pointer that needs to be
+ * rcu_read_locked.  The item in the slot (either by *slot or by a regular
+ * radix_lookup) has limited protections.  Higher layers (pagemap) can do their
+ * own thing.  For instance, the page cache writers can zero an item if they
+ * know they cleared the page without someone else grabbing a ref.  We'll
+ * rcu-protect the item pointer, so that higher layers can use RCU for the
+ * actual object.
+ *
+ * Basically the only functions that don't need the caller to hold a qlock are
+ * the two lookup routines: the readers.  The seq counter protects the atomicity
+ * of root, depth, and upper_bound, which defines the reader's start point.  RCU
+ * protects the lifetime of the rnodes, which is where lookup_slot's pointer
+ * points to.
+ *
+ * Note that we use rcu_assign_pointer and rcu_dereference whenever we
+ * manipulate pointers in the tree (pointers to or within rnodes).  We use RCU
+ * for the item pointer too, so that our callers can use RCU if they want.  Both
+ * the slot pointer and what it points to are protected by RCU.
+ */
 struct radix_tree {
-       struct radix_node                       *root;
-       unsigned int                            depth;
-       unsigned long                           upper_bound;
+       seq_ctr_t                       seq;
+       struct radix_node               *root;
+       unsigned int                    depth;
+       unsigned long                   upper_bound;
 };
 
 void radix_init(void);         /* initializes the whole radix system */
-#define RADIX_INITIALIZER {0, 0, 0}
 void radix_tree_init(struct radix_tree *tree); /* inits one tree */
 void radix_tree_destroy(struct radix_tree *tree);
 
 /* Item management */
-int radix_insert(struct radix_tree *tree, unsigned long key, void *item);
+int radix_insert(struct radix_tree *tree, unsigned long key, void *item,
+                 void ***slot_p);
 void *radix_delete(struct radix_tree *tree, unsigned long key);
 void *radix_lookup(struct radix_tree *tree, unsigned long key);
 void **radix_lookup_slot(struct radix_tree *tree, unsigned long key);
-int radix_gang_lookup(struct radix_tree *tree, void **results,
-                      unsigned long first, unsigned int max_items);
+
+typedef bool (*radix_cb_t)(void **slot, unsigned long tree_idx, void *arg);
+void radix_for_each_slot(struct radix_tree *tree, radix_cb_t cb, void *arg);
+/* [start_idx, end_idx) */
+void radix_for_each_slot_in_range(struct radix_tree *tree,
+                                  unsigned long start_idx,
+                                  unsigned long end_idx,
+                                  radix_cb_t cb, void *arg);
 
 /* Memory management */
 int radix_grow(struct radix_tree *tree, unsigned long max);
@@ -66,5 +97,3 @@ int radix_tag_gang_lookup(struct radix_tree *tree, void **results,
 
 /* Debugging */
 void print_radix_tree(struct radix_tree *tree);
-
-#endif /* !ROS_KERN_RADIX_H */