Fix data leak in fs_file_write()
[akaros.git] / kern / src / rcu_tree_helper.c
1 /*
2  * Read-Copy Update mechanism for mutual exclusion
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, you can access it online at
16  * http://www.gnu.org/licenses/gpl-2.0.html.
17  *
18  * Copyright IBM Corporation, 2008
19  *
20  * Authors: Dipankar Sarma <dipankar@in.ibm.com>
21  *          Manfred Spraul <manfred@colorfullife.com>
22  *          Paul E. McKenney <paulmck@linux.vnet.ibm.com> Hierarchical version
23  *
24  * Based on the original work by Paul McKenney <paulmck@us.ibm.com>
25  * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
26  *
27  * For detailed explanation of Read-Copy Update mechanism see -
28  *      Documentation/RCU
29  *
30  * AKAROS_PORT: was kernel/rcu/tree.c.
31  */
32
33
34 #include <rcu.h>
35 #include <assert.h>
36 #include <smp.h>
37
38 /* Control rcu_node-tree auto-balancing at boot time. */
39 bool rcu_fanout_exact;
40 /* Increase (but not decrease) the RCU_FANOUT_LEAF at boot time. */
41 int rcu_fanout_leaf = RCU_FANOUT_LEAF;
42 int rcu_num_lvls = RCU_NUM_LVLS;
43 /* Number of rcu_nodes at specified level. */
44 int num_rcu_lvl[] = NUM_RCU_LVL_INIT;
45 int rcu_num_nodes = NUM_RCU_NODES; /* Total # rcu_nodes in use. */
46 /* Number of cores RCU thinks exist.  Set to 0 or nothing to use 'num_cores'.
47  * The extra cores are called 'fake cores' in rcu.c, and are used for testing
48  * the tree. */
49 int rcu_num_cores;
50
51 /* in rcu.c */
52 extern struct rcu_state rcu_state;
53
54 /**
55  * get_state_synchronize_rcu - Snapshot current RCU state
56  *
57  * Returns a cookie that is used by a later call to cond_synchronize_rcu()
58  * to determine whether or not a full grace period has elapsed in the
59  * meantime.
60  */
61 unsigned long get_state_synchronize_rcu(void)
62 {
63         /*
64          * Any prior manipulation of RCU-protected data must happen
65          * before the load from ->gpnum.
66          */
67         mb();  /* ^^^ */
68
69         /*
70          * Make sure this load happens before the purportedly
71          * time-consuming work between get_state_synchronize_rcu()
72          * and cond_synchronize_rcu().
73          */
74         return smp_load_acquire(&rcu_state.gpnum);
75 }
76
77 /**
78  * cond_synchronize_rcu - Conditionally wait for an RCU grace period
79  *
80  * @oldstate: return value from earlier call to get_state_synchronize_rcu()
81  *
82  * If a full RCU grace period has elapsed since the earlier call to
83  * get_state_synchronize_rcu(), just return.  Otherwise, invoke
84  * synchronize_rcu() to wait for a full grace period.
85  *
86  * Yes, this function does not take counter wrap into account.  But
87  * counter wrap is harmless.  If the counter wraps, we have waited for
88  * more than 2 billion grace periods (and way more on a 64-bit system!),
89  * so waiting for one additional grace period should be just fine.
90  */
91 void cond_synchronize_rcu(unsigned long oldstate)
92 {
93         unsigned long newstate;
94
95         /*
96          * Ensure that this load happens before any RCU-destructive
97          * actions the caller might carry out after we return.
98          */
99         newstate = smp_load_acquire(&rcu_state.completed);
100         if (ULONG_CMP_GE(oldstate, newstate))
101                 synchronize_rcu();
102 }
103
104
105 /*
106  * Helper function for rcu_init() that initializes one rcu_state structure.
107  */
108 void rcu_init_one(struct rcu_state *rsp)
109 {
110         int levelspread[RCU_NUM_LVLS];          /* kids/node in each level. */
111         int cpustride = 1;
112         int i;
113         int j;
114         struct rcu_node *rnp;
115         struct rcu_pcpui *rpi;
116
117         rendez_init(&rsp->gp_ktask_rv);
118         rsp->gp_ktask_ctl = 0;
119         /* To test wraparound early */
120         rsp->gpnum = ULONG_MAX - 20;
121         rsp->completed = ULONG_MAX - 20;
122
123         /* Silence gcc 4.8 false positive about array index out of range. */
124         if (rcu_num_lvls <= 0 || rcu_num_lvls > RCU_NUM_LVLS)
125                 panic("rcu_init_one: rcu_num_lvls out of range");
126
127         /* Initialize the level-tracking arrays. */
128
129         rsp->level[0] = &rsp->node[0];
130         for (i = 1; i < rcu_num_lvls; i++)
131                 rsp->level[i] = rsp->level[i - 1] + num_rcu_lvl[i - 1];
132         rcu_init_levelspread(levelspread, num_rcu_lvl);
133
134         /* Initialize the elements themselves, starting from the leaves. */
135
136         for (i = rcu_num_lvls - 1; i >= 0; i--) {
137                 cpustride *= levelspread[i];
138                 rnp = rsp->level[i];
139                 for (j = 0; j < num_rcu_lvl[i]; j++, rnp++) {
140                         rnp->qsmask = 0;
141                         rnp->qsmaskinit = 0;
142                         rnp->grplo = j * cpustride;
143                         rnp->grphi = (j + 1) * cpustride - 1;
144                         if (rnp->grphi >= rcu_num_cores)
145                                 rnp->grphi = rcu_num_cores - 1;
146                         if (i == 0) {
147                                 rnp->grpnum = 0;
148                                 rnp->grpmask = 0;
149                                 rnp->parent = NULL;
150                         } else {
151                                 rnp->grpnum = j % levelspread[i - 1];
152                                 rnp->grpmask = 1UL << rnp->grpnum;
153                                 rnp->parent = rsp->level[i - 1] +
154                                                   j / levelspread[i - 1];
155                         }
156                         rnp->level = i;
157                 }
158         }
159
160         rnp = rsp->level[rcu_num_lvls - 1];
161         for_each_core(i) {
162                 while (i > rnp->grphi)
163                         rnp++;
164                 rpi = _PERCPU_VARPTR(rcu_pcpui, i);
165                 rpi->my_node = rnp;
166                 rcu_init_pcpui(rsp, rpi, i);
167         }
168         /* Akaros has static rnps, so we can init these once. */
169         rcu_for_each_node_breadth_first(rsp, rnp)
170                 if (rnp->parent)
171                         rnp->parent->qsmaskinit |= rnp->grpmask;
172 }
173
174 /*
175  * Compute the rcu_node tree geometry from kernel parameters.  This cannot
176  * replace the definitions in tree.h because those are needed to size
177  * the ->node array in the rcu_state structure.
178  */
179 void rcu_init_geometry(void)
180 {
181         int i;
182         int rcu_capacity[RCU_NUM_LVLS];
183         int nr_cpu_ids;
184
185         if (!rcu_num_cores)
186                 rcu_num_cores = num_cores;
187         nr_cpu_ids = rcu_num_cores;
188         /* If the compile-time values are accurate, just leave. */
189         if (rcu_fanout_leaf == RCU_FANOUT_LEAF &&
190                 nr_cpu_ids == NR_CPUS)
191                 return;
192         printk("RCU: Adjusting geometry for rcu_fanout_leaf=%d, nr_cpu_ids=%d\n",
193                 rcu_fanout_leaf, nr_cpu_ids);
194
195         /*
196          * The boot-time rcu_fanout_leaf parameter must be at least two
197          * and cannot exceed the number of bits in the rcu_node masks.
198          * Complain and fall back to the compile-time values if this
199          * limit is exceeded.
200          */
201         if (rcu_fanout_leaf < 2 ||
202                 rcu_fanout_leaf > sizeof(unsigned long) * 8) {
203                 rcu_fanout_leaf = RCU_FANOUT_LEAF;
204                 warn_on(1);
205                 return;
206         }
207
208         /*
209          * Compute number of nodes that can be handled an rcu_node tree
210          * with the given number of levels.
211          */
212         rcu_capacity[0] = rcu_fanout_leaf;
213         for (i = 1; i < RCU_NUM_LVLS; i++)
214                 rcu_capacity[i] = rcu_capacity[i - 1] * RCU_FANOUT;
215
216         /*
217          * The tree must be able to accommodate the configured number of CPUs.
218          * If this limit is exceeded, fall back to the compile-time values.
219          */
220         if (nr_cpu_ids > rcu_capacity[RCU_NUM_LVLS - 1]) {
221                 rcu_fanout_leaf = RCU_FANOUT_LEAF;
222                 warn_on(1);
223                 return;
224         }
225
226         /* Calculate the number of levels in the tree. */
227         for (i = 0; nr_cpu_ids > rcu_capacity[i]; i++) {
228         }
229         rcu_num_lvls = i + 1;
230
231         /* Calculate the number of rcu_nodes at each level of the tree. */
232         for (i = 0; i < rcu_num_lvls; i++) {
233                 int cap = rcu_capacity[(rcu_num_lvls - 1) - i];
234                 num_rcu_lvl[i] = DIV_ROUND_UP(nr_cpu_ids, cap);
235         }
236
237         /* Calculate the total number of rcu_node structures. */
238         rcu_num_nodes = 0;
239         for (i = 0; i < rcu_num_lvls; i++)
240                 rcu_num_nodes += num_rcu_lvl[i];
241 }
242
243 /*
244  * Dump out the structure of the rcu_node combining tree associated
245  * with the rcu_state structure referenced by rsp.
246  */
247 void rcu_dump_rcu_node_tree(struct rcu_state *rsp)
248 {
249         int level = 0;
250         struct rcu_node *rnp;
251
252         print_lock();
253         printk("rcu_node tree layout dump\n");
254         printk(" ");
255         rcu_for_each_node_breadth_first(rsp, rnp) {
256                 if (rnp->level != level) {
257                         printk("\n");
258                         printk(" ");
259                         level = rnp->level;
260                 }
261                 printk("%d:%d ^%d ", rnp->grplo, rnp->grphi, rnp->grpnum);
262         }
263         printk("\n");
264         print_unlock();
265 }