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