Update version-controlled scripts for bash
[akaros.git] / Documentation / kref.txt
1 Krefs and Topics on Refcounting:
2 ----------------------------
3 We do reference counting of our objects in much the same way as Linux.  The
4 stuff we do is based on the Linux way, discussed/described here:
5 - http://www.kroah.com/linux/talks/ols_2004_kref_paper/
6          Reprint-Kroah-Hartman-OLS2004.pdf
7 - http://lwn.net/Articles/336224/
8 - Linux's Documentation/kref.txt
9
10 To best understand krefs, keep in mind this quote (from their kref.txt): "the
11 kref is appropriate when the object doesn't outlive its last external
12 reference."  What we want is to know when all "external" references to an object
13 are gone.  At which point we can do something (cleanup, free, etc) and be sure
14 that no other code can get a reference.  We want to do this without locks, if
15 possible, so we make use of a variety of helpful atomics (though RAMP uses a
16 lock-per-atomic).
17
18 This document will ramble about the details and other stuff.
19 Here are things to keep in mind, which differ in some of the use cases:
20 - we want to do something when the refcount hits 0.
21 - we don't always know when that is.
22 - we might not have a function to call to explicitly remove the object.
23 - we might want to bring an object "back to life."  This is outliving your last
24   external reference, but it is something we want.  And so does Linux.
25
26 kref rules (adaptation of the linux ones):
27 1. If you pass a pointer somewhere or store it (a non-temporary copy),
28 kref_get() it first.  You can do this with no locking if you have a valid
29 external reference.
30 2. When you are done, kref_put() it.
31 3. If you do not have a valid *external* reference, you can try
32 kref_get_not_zero().  You must have an internal reference for this.  And to
33 protect that *internal* reference, you often need to lock or otherwise sync
34 around the source of that internal reference (usually a list-like structure
35 (LLS)), unless that ref is otherwise protected from concurrent freeing.
36 4. If you plan to resurrect an object (make its refcnt go from 0 to 1), you
37 need to use some other form of sync between the final freeing and the
38 resurrection.
39
40 We differ from Linux in a few of ways.  We have a kref_get_not_zero(), which
41 they talk about in some of their documents, to be a bit more clear about getting
42 refs when objects might be at 0.  Some of the differences is just semantics and
43 usage.  We also allow incrementing by more than one, which helps in some cases.
44 We don't allow decrementing by more than one to catch bugs (for now).  We also
45 put the release function in the kref, which is what Linux used to do.  We do it
46 to cut down on the number of places the function pointer is writen, since I
47 expect those to change a lot as subsystems use krefs.  Finally, we only use
48 krefs to trigger an object's release function, which might not free them
49 forever.  They can be "resurrected" back to having an external reference.  You
50 can do similar things in Linux, but it's not clear (to me) how separate that
51 idea is from a kref.
52
53 External (strong) vs internal (weak) references:
54 ----------------------------
55 I want something to happen (like for the obj to die) when its refcnt hits 0.  I
56 don't know when this will happen, or who will be the one who makes the final
57 decref.  So we have the kref - it automatically executes a callback when the
58 refcnt hits 0.  However, there are cases when we have "references" (possibly
59 uncounted pointers) to an object that we do not want to consider in this
60 calculation.  A good example is the superblock's list of all files.  If that
61 reference is counted, the file will never be freed - it's just a list for
62 managing the existing files.  There's a chicken-egg issue, since removing the
63 pointer to the file from the list is what should happen in the cleanup after the
64 refcount hits 0.  This is the nature of an internal (weak) reference.  External
65 (strong) references are those that count towards when an object should be
66 freed/called-back/whatever.
67
68 So now we have lists and other sources of a "reference" / pointer (and it
69 doesn't matter if is counted in some variable other than refcount).  We need to
70 be able to get valid external references for this.  Just about any time that you
71 want to use the object, you'll need to do this - or otherwise prevent it from
72 dying/being clean-up.  We can't simply kref_get(), since we don't already have a
73 valid external reference.  Instead we use kref_get_not_zero(), which uses
74 atomic_inc_not_zero() (or something similar).  Using this guarantees that if it
75 succeeded, there was *an* external reference - we just didn't have it.  It is
76 possible that this fails, and it's a bit slower, so only use it when going from
77 an internal reference to an external one.  For lists like the SB's file
78 list/tailq, this won't be too hard, since once we hit 0, we remove it from the
79 list and free it.  Things are more complicated if we want to do other things
80 when we hit 0 - specifically if we want to "come back from the dead" and go from
81 0 back to 1 or more.
82
83 However, things aren't quite this easy.  Short version: lock your list.  Long
84 version: kref_get_not_zero() only works when we have a valid internal reference.
85 It works based on the assumption that its pointer is still the object (and not
86 some freed memory).  You need to do something like: "lock the LLS, get your
87 pointer from the LLS, get_not_zero, unlock."  The lock protects your internal
88 reference.  Later on we talk about some other schemes, but ultimately you need
89 to sync or otherwise guarantee your internal reference is valid.
90
91 This is probably why we want to either lock outside our list-solution, or
92 integrate the list/hash structure into the owning subsystem.  (mentioned in more
93 detail below).  Also note, with locking you need to be careful of deadlocking.
94 kref_put() will return 1 if the refcnt hit 0, so you can unlock and do some
95 other cleanup without holding a list's lock.  This effectively allows you to
96 split the release between what kref_put() does automatically with whatever else
97 you want done.
98
99 What about an 'internal' kref?  If we refcnt the refs on lists, we still have
100 the same issue of syncing between a list reader and a list writer.  The reader
101 needs to atomically read and kref_get (not_zero or otherwise).  Otherwise,
102 someone can remove, put, free, and do whatever to the item between the read and
103 the kref_get (in theory).
104
105 The reason for this is the same reason we have trouble with lists and internal
106 references in the first place: both the list reader and the writer are sharing
107 the same reference.  One is trying to kref_get() it, while another is trying to
108 kref_put() it.  If the freeing happens in between getting the pointer from the
109 list and the kref_getting, we'll have a bug.  (unless we do some tricks related
110 to seq counters and grace periods, discussed below).  This is the same issue,
111 regardless of whether the internal reference is using another kref or if it uses
112 some other scheme (like lock the object and check its state).
113
114 Resurrecting an object after it hit 0
115 ----------------------------
116 So when we hit 0, we might not be completely done with the object.  This is part
117 of the "kcref" (c == cached) design pattern the Linux guys talk about.  The main
118 example they use (and we will too) is the dentry - you want to cache them, even
119 if their refcnt is 0.  Once their refcount is 0, you still want to do things -
120 just not free them.  Specifically, we'll set their state to show they are unused
121 (and thus freeable when there is pressure).  The tricky thing is that when a
122 cache lookup finds the dentry, whose refcount is still 0, we need to be able to
123 get it and set its external refcount to 1 (bring it "back to life").  We can use
124 kref_init() or some other function for this - the important thing is that it
125 cannot happen while the object is being freed for real (when it is removed from
126 the cache).  One way or another, we need to synchronize.
127
128 The way Linux handles this is that there is a lock for the dentry object and one
129 overall one for the dentry cache.  You can't convert an internal reference to an
130 external reference without hold this lock.  Just locking on the object could
131 result in issues where an object is freed and reused as a *different* object,
132 which then the cache reader gets instead of failing at trying to get the
133 original object.  The kref refcount only helps when the refcount goes from 1 to
134 0, and on triggering the followup/release action.
135
136 To resurrect, we can't just do:
137         if (!kref_refcnt(&dentry->d_kref))
138                 kref_init(&dentry->d_kref, dentry_release, 1);
139         else
140                 kref_get(&dentry->d_kref, 1);
141
142 There is a race on reading the refcnt and mucking with it.  If it is
143 concurrently going from 1 -> 0, and we read 0, it is okay.  We still up it to 1.
144 However, if we go from 1 -> 0 and read 1, we'll panic when we try to kref_get a
145 0'd kref.  Also, doing this would be dangerous going from 0 -> 1 if other code
146 would resurrect (which it does not!).  The solution is to use a kref_get that
147 doesn't care about 0 (__kref_get()).
148
149 Elsewhere in this documentation, we talk about kref_get_not_zero().  That one
150 will try and fail gracefully (used by pid2proc()).  kref_get() will fail on
151 zero.  __kref_get() will not fail on zero and will blindly increment, which is
152 what we want. 
153
154 Trickiness with lockless data structures:
155 ----------------------------
156 Ideally, we want concurrent access to the dentry cache (or whatever cache has
157 krefd objects that we want to resurrect).  Perhaps this is with CAS on linked
158 lists, or locks per hash bucket.  Since we need to prevent the resurrection of
159 objects from proceeding while another thread could be trying to remove them, we
160 need some sync between readers and writers.  Both threads in the scenario we've
161 been talking about are going to be writers for the object, though from the
162 perspective of the list-like-structure, only one is a writer - the one who makes
163 it such that we cannot create an external ref from an internal one, because the
164 object is dying.
165
166 Simply doing this: "lookup, object lock, muck with state" will result in bugs,
167 since the state change changes the lookup, but the locking happens after the
168 lookup.  We could be manipulating a newly slab-allocated object (or anything,
169 really), that has an unlocked byte where we expect it (and thus our spin_lock()
170 succeeded).
171
172 At this point, there are two options: Handle it in the list-like-structure, or
173 play more clever games:
174
175 1: Push it into the list-like structure (LLS)
176 ----------------
177 In the first case, the state changing needs to be pushed into the data structure
178 managing the objects for these types of scenarios.  For example, a
179 spinlock-per-hashbucket scenario would need to know to execute a certain
180 function on the object if it finds it before unlocking the bucket.  Sync systems
181 based on RCU will need to be careful with the final delete function.  I think
182 this is part of the reason why Linux doesn't have a built-in solution for a hash
183 table - subsystems roll their own using tools (instead of solutions), since the
184 removal is coupled with how the subsystem works.
185
186 2: Seq-ctrs and Reused objects
187 ----------------
188 The other way, and one we may look into, is to push a seq-ctr into the object.
189 The plan is then: "{lookup, object lock} (while seq changed), muck with state"
190 (being careful to unlock, etc).  The idea is that the seq-ctr gets incremented
191 when the object is freed / given back to the slab allocator (which is done by
192 the removal thread).  If the seq-ctr changed, that means we are no longer
193 looking at the same object, and we need to retry the lookup (start over).  The
194 seq-ctr exists for the memory region dedicated to the object, not for a specific
195 object.
196
197 This approach needs a little more help: it assumes that any freed object will
198 continue to be an object of that type for a little while.  We are dealing with
199 slab-allocated objects, so that is a bit more true than when dealing with
200 kmalloc().  However, it is possible that there was memory pressure and the slab
201 subsystem freed those pages.  We need to be sure that this event has not
202 happened before we try to lock the object.  It's okay to lock and unlock an
203 'unrelated' dentry.  It's not okay to try and lock a random spot in memory.  We
204 could have a variety of read-mostly globals to perhaps signal slab-pressure,
205 dentry-slab-pressure, or something like that, depending on who else needs to
206 know about that event.  These seem tricky, and probably require some form of
207 locking, which leads to the most likely candidate: RCU-style grace periods.
208
209 The thing we really care about is that the pages are not allocated to some other
210 use.  For unrelated (TLB) reasons, we may build an RCU-like mechanism for
211 dealing with free pages, and we could consider using this - though if the slab
212 allocator is asked for memory, it is because we are running out, and we don't
213 want to wait for grace periods.  Anyway, we'll probably never do any of this, at
214 least until it becomse a problem.
215
216 FYI: the whole lock on possibly the next incarnation of the object will only
217 work if we unlock it at some point - might be a while, if it doesn't get
218 unlocked until it's spinlock_init()ed as the new object.  If we do this, we
219 ought to unlock before slab-freeing.
220
221 Final Notes
222 ----------------------------
223 There is a difference between removing references to you from all over the place
224 and cleaning up references that you know about (like when you know you are in a
225 TAILQ all the time vs. being in a process's file list).
226
227 Process management is a bit different, since it does not want to destroy or free
228 you until there was some explicit action (calling proc_destroy()).  We still use
229 krefs, since we don't know who is the "last one out" to do the freeing, so we
230 layer proc_destroy() on top of kref/__proc_free().  This is why we have the "one
231 ref to keep the object alive."  For a little while, this ref was stored in the
232 pid2proc hash, but that is now holds an internal reference (we have the tech, it
233 keeps things in sync with other usage models, and it makes proc_destroy and
234 sys_trywait easier).  Note the runnable_list has external references, in part
235 because it is a different subsystem (scheduler).
236
237 Remember: the reason for why we have trouble with lists and (internal)
238 references: both the list reader and the writer are sharing the same
239 reference/pointer.  We need to either make sure that a reader can use the
240 pointer (pinned, kref_get(), a flag, whatever while preventing access to the
241 pointer from another thread (lock the list)), or that it can *safely* find out
242 it needs to try again.  "Safe" means not accessing freed memory - hence the
243 grace periods on slab-freed pages.
244
245 Kreffing works because we have a known, synchronous initialization point where
246 we kref_init() the refcount to 1.  We can't do that easily when resurrecting or
247 even kref_get_not_zero() because another thread may be trying to permanently
248 free the object.
249
250 The difference between kref_get_not_zero() and resurrection is that
251 get_not_zero() is trying to get an external reference and the object's release
252 method has not been called (or it has, and we should fail since our source is a
253 weak/internal reference source).  Resurrection is when we've already hit 0,
254 release()d, and now want to reuse that object.  For concrete examples:
255 get_not_zero() works when getting a file off the superblock file list - it only
256 should work if the file is still in the system and not about to be removed from
257 the list.  Resurrection is for objects that don't get freed when they lose
258 their external references, such as dentries (they get put on the dentry cache).
259 On a cache hit for an unreferenced dentry, we'll need to change its state and
260 reinit its refcount.  Next time it is kref_put()d to 0, it'll rerun its
261 release() method.
262
263 Deadlocking is still an issue, and might be what forces us to more lock-free
264 lists.  Here's an example of what not to do: grab the SB's tailq lock, for each
265 file, kref_put it, then unlock.  That code might be trying to force all files to
266 close, which is just fundamentally flawed anyways (since you're decreffing an
267 internal reference, instead of an external one).  But you'll deadlock too, since
268 the file's kref release() method will try and grab the same lock to rip the item
269 off the list.  So this is a contrived example, but it goes to show that you need
270 to be careful about where you are locking and what functions your kref_put()
271 might trigger.