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