gc.c 9.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /* Key garbage collector
  3. *
  4. * Copyright (C) 2009-2011 Red Hat, Inc. All Rights Reserved.
  5. * Written by David Howells (dhowells@redhat.com)
  6. */
  7. #include <linux/slab.h>
  8. #include <linux/security.h>
  9. #include <keys/keyring-type.h>
  10. #include "internal.h"
  11. /*
  12. * Delay between key revocation/expiry in seconds
  13. */
  14. unsigned key_gc_delay = 5 * 60;
  15. /*
  16. * Reaper for unused keys.
  17. */
  18. static void key_garbage_collector(struct work_struct *work);
  19. DECLARE_WORK(key_gc_work, key_garbage_collector);
  20. /*
  21. * Reaper for links from keyrings to dead keys.
  22. */
  23. static void key_gc_timer_func(struct timer_list *);
  24. static DEFINE_TIMER(key_gc_timer, key_gc_timer_func);
  25. static time64_t key_gc_next_run = TIME64_MAX;
  26. static struct key_type *key_gc_dead_keytype;
  27. static unsigned long key_gc_flags;
  28. #define KEY_GC_KEY_EXPIRED 0 /* A key expired and needs unlinking */
  29. #define KEY_GC_REAP_KEYTYPE 1 /* A keytype is being unregistered */
  30. #define KEY_GC_REAPING_KEYTYPE 2 /* Cleared when keytype reaped */
  31. /*
  32. * Any key whose type gets unregistered will be re-typed to this if it can't be
  33. * immediately unlinked.
  34. */
  35. struct key_type key_type_dead = {
  36. .name = ".dead",
  37. };
  38. /*
  39. * Schedule a garbage collection run.
  40. * - time precision isn't particularly important
  41. */
  42. void key_schedule_gc(time64_t gc_at)
  43. {
  44. unsigned long expires;
  45. time64_t now = ktime_get_real_seconds();
  46. kenter("%lld", gc_at - now);
  47. if (gc_at <= now || test_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags)) {
  48. kdebug("IMMEDIATE");
  49. schedule_work(&key_gc_work);
  50. } else if (gc_at < key_gc_next_run) {
  51. kdebug("DEFERRED");
  52. key_gc_next_run = gc_at;
  53. expires = jiffies + (gc_at - now) * HZ;
  54. mod_timer(&key_gc_timer, expires);
  55. }
  56. }
  57. /*
  58. * Schedule a dead links collection run.
  59. */
  60. void key_schedule_gc_links(void)
  61. {
  62. set_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags);
  63. schedule_work(&key_gc_work);
  64. }
  65. /*
  66. * Some key's cleanup time was met after it expired, so we need to get the
  67. * reaper to go through a cycle finding expired keys.
  68. */
  69. static void key_gc_timer_func(struct timer_list *unused)
  70. {
  71. kenter("");
  72. key_gc_next_run = TIME64_MAX;
  73. key_schedule_gc_links();
  74. }
  75. /*
  76. * Reap keys of dead type.
  77. *
  78. * We use three flags to make sure we see three complete cycles of the garbage
  79. * collector: the first to mark keys of that type as being dead, the second to
  80. * collect dead links and the third to clean up the dead keys. We have to be
  81. * careful as there may already be a cycle in progress.
  82. *
  83. * The caller must be holding key_types_sem.
  84. */
  85. void key_gc_keytype(struct key_type *ktype)
  86. {
  87. kenter("%s", ktype->name);
  88. key_gc_dead_keytype = ktype;
  89. set_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
  90. smp_mb();
  91. set_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags);
  92. kdebug("schedule");
  93. schedule_work(&key_gc_work);
  94. kdebug("sleep");
  95. wait_on_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE,
  96. TASK_UNINTERRUPTIBLE);
  97. key_gc_dead_keytype = NULL;
  98. kleave("");
  99. }
  100. /*
  101. * Garbage collect a list of unreferenced, detached keys
  102. */
  103. static noinline void key_gc_unused_keys(struct list_head *keys)
  104. {
  105. while (!list_empty(keys)) {
  106. struct key *key =
  107. list_entry(keys->next, struct key, graveyard_link);
  108. short state = key->state;
  109. list_del(&key->graveyard_link);
  110. kdebug("- %u", key->serial);
  111. key_check(key);
  112. #ifdef CONFIG_KEY_NOTIFICATIONS
  113. remove_watch_list(key->watchers, key->serial);
  114. key->watchers = NULL;
  115. #endif
  116. /* Throw away the key data if the key is instantiated */
  117. if (state == KEY_IS_POSITIVE && key->type->destroy)
  118. key->type->destroy(key);
  119. security_key_free(key);
  120. /* deal with the user's key tracking and quota */
  121. if (test_bit(KEY_FLAG_IN_QUOTA, &key->flags)) {
  122. spin_lock(&key->user->lock);
  123. key->user->qnkeys--;
  124. key->user->qnbytes -= key->quotalen;
  125. spin_unlock(&key->user->lock);
  126. }
  127. atomic_dec(&key->user->nkeys);
  128. if (state != KEY_IS_UNINSTANTIATED)
  129. atomic_dec(&key->user->nikeys);
  130. key_user_put(key->user);
  131. key_put_tag(key->domain_tag);
  132. kfree(key->description);
  133. memzero_explicit(key, sizeof(*key));
  134. kmem_cache_free(key_jar, key);
  135. }
  136. }
  137. /*
  138. * Garbage collector for unused keys.
  139. *
  140. * This is done in process context so that we don't have to disable interrupts
  141. * all over the place. key_put() schedules this rather than trying to do the
  142. * cleanup itself, which means key_put() doesn't have to sleep.
  143. */
  144. static void key_garbage_collector(struct work_struct *work)
  145. {
  146. static LIST_HEAD(graveyard);
  147. static u8 gc_state; /* Internal persistent state */
  148. #define KEY_GC_REAP_AGAIN 0x01 /* - Need another cycle */
  149. #define KEY_GC_REAPING_LINKS 0x02 /* - We need to reap links */
  150. #define KEY_GC_SET_TIMER 0x04 /* - We need to restart the timer */
  151. #define KEY_GC_REAPING_DEAD_1 0x10 /* - We need to mark dead keys */
  152. #define KEY_GC_REAPING_DEAD_2 0x20 /* - We need to reap dead key links */
  153. #define KEY_GC_REAPING_DEAD_3 0x40 /* - We need to reap dead keys */
  154. #define KEY_GC_FOUND_DEAD_KEY 0x80 /* - We found at least one dead key */
  155. struct rb_node *cursor;
  156. struct key *key;
  157. time64_t new_timer, limit;
  158. kenter("[%lx,%x]", key_gc_flags, gc_state);
  159. limit = ktime_get_real_seconds();
  160. if (limit > key_gc_delay)
  161. limit -= key_gc_delay;
  162. else
  163. limit = key_gc_delay;
  164. /* Work out what we're going to be doing in this pass */
  165. gc_state &= KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2;
  166. gc_state <<= 1;
  167. if (test_and_clear_bit(KEY_GC_KEY_EXPIRED, &key_gc_flags))
  168. gc_state |= KEY_GC_REAPING_LINKS | KEY_GC_SET_TIMER;
  169. if (test_and_clear_bit(KEY_GC_REAP_KEYTYPE, &key_gc_flags))
  170. gc_state |= KEY_GC_REAPING_DEAD_1;
  171. kdebug("new pass %x", gc_state);
  172. new_timer = TIME64_MAX;
  173. /* As only this function is permitted to remove things from the key
  174. * serial tree, if cursor is non-NULL then it will always point to a
  175. * valid node in the tree - even if lock got dropped.
  176. */
  177. spin_lock(&key_serial_lock);
  178. cursor = rb_first(&key_serial_tree);
  179. continue_scanning:
  180. while (cursor) {
  181. key = rb_entry(cursor, struct key, serial_node);
  182. cursor = rb_next(cursor);
  183. if (refcount_read(&key->usage) == 0)
  184. goto found_unreferenced_key;
  185. if (unlikely(gc_state & KEY_GC_REAPING_DEAD_1)) {
  186. if (key->type == key_gc_dead_keytype) {
  187. gc_state |= KEY_GC_FOUND_DEAD_KEY;
  188. set_bit(KEY_FLAG_DEAD, &key->flags);
  189. key->perm = 0;
  190. goto skip_dead_key;
  191. } else if (key->type == &key_type_keyring &&
  192. key->restrict_link) {
  193. goto found_restricted_keyring;
  194. }
  195. }
  196. if (gc_state & KEY_GC_SET_TIMER) {
  197. if (key->expiry > limit && key->expiry < new_timer) {
  198. kdebug("will expire %x in %lld",
  199. key_serial(key), key->expiry - limit);
  200. new_timer = key->expiry;
  201. }
  202. }
  203. if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2))
  204. if (key->type == key_gc_dead_keytype)
  205. gc_state |= KEY_GC_FOUND_DEAD_KEY;
  206. if ((gc_state & KEY_GC_REAPING_LINKS) ||
  207. unlikely(gc_state & KEY_GC_REAPING_DEAD_2)) {
  208. if (key->type == &key_type_keyring)
  209. goto found_keyring;
  210. }
  211. if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3))
  212. if (key->type == key_gc_dead_keytype)
  213. goto destroy_dead_key;
  214. skip_dead_key:
  215. if (spin_is_contended(&key_serial_lock) || need_resched())
  216. goto contended;
  217. }
  218. contended:
  219. spin_unlock(&key_serial_lock);
  220. maybe_resched:
  221. if (cursor) {
  222. cond_resched();
  223. spin_lock(&key_serial_lock);
  224. goto continue_scanning;
  225. }
  226. /* We've completed the pass. Set the timer if we need to and queue a
  227. * new cycle if necessary. We keep executing cycles until we find one
  228. * where we didn't reap any keys.
  229. */
  230. kdebug("pass complete");
  231. if (gc_state & KEY_GC_SET_TIMER && new_timer != (time64_t)TIME64_MAX) {
  232. new_timer += key_gc_delay;
  233. key_schedule_gc(new_timer);
  234. }
  235. if (unlikely(gc_state & KEY_GC_REAPING_DEAD_2) ||
  236. !list_empty(&graveyard)) {
  237. /* Make sure that all pending keyring payload destructions are
  238. * fulfilled and that people aren't now looking at dead or
  239. * dying keys that they don't have a reference upon or a link
  240. * to.
  241. */
  242. kdebug("gc sync");
  243. synchronize_rcu();
  244. }
  245. if (!list_empty(&graveyard)) {
  246. kdebug("gc keys");
  247. key_gc_unused_keys(&graveyard);
  248. }
  249. if (unlikely(gc_state & (KEY_GC_REAPING_DEAD_1 |
  250. KEY_GC_REAPING_DEAD_2))) {
  251. if (!(gc_state & KEY_GC_FOUND_DEAD_KEY)) {
  252. /* No remaining dead keys: short circuit the remaining
  253. * keytype reap cycles.
  254. */
  255. kdebug("dead short");
  256. gc_state &= ~(KEY_GC_REAPING_DEAD_1 | KEY_GC_REAPING_DEAD_2);
  257. gc_state |= KEY_GC_REAPING_DEAD_3;
  258. } else {
  259. gc_state |= KEY_GC_REAP_AGAIN;
  260. }
  261. }
  262. if (unlikely(gc_state & KEY_GC_REAPING_DEAD_3)) {
  263. kdebug("dead wake");
  264. smp_mb();
  265. clear_bit(KEY_GC_REAPING_KEYTYPE, &key_gc_flags);
  266. wake_up_bit(&key_gc_flags, KEY_GC_REAPING_KEYTYPE);
  267. }
  268. if (gc_state & KEY_GC_REAP_AGAIN)
  269. schedule_work(&key_gc_work);
  270. kleave(" [end %x]", gc_state);
  271. return;
  272. /* We found an unreferenced key - once we've removed it from the tree,
  273. * we can safely drop the lock.
  274. */
  275. found_unreferenced_key:
  276. kdebug("unrefd key %d", key->serial);
  277. rb_erase(&key->serial_node, &key_serial_tree);
  278. spin_unlock(&key_serial_lock);
  279. list_add_tail(&key->graveyard_link, &graveyard);
  280. gc_state |= KEY_GC_REAP_AGAIN;
  281. goto maybe_resched;
  282. /* We found a restricted keyring and need to update the restriction if
  283. * it is associated with the dead key type.
  284. */
  285. found_restricted_keyring:
  286. spin_unlock(&key_serial_lock);
  287. keyring_restriction_gc(key, key_gc_dead_keytype);
  288. goto maybe_resched;
  289. /* We found a keyring and we need to check the payload for links to
  290. * dead or expired keys. We don't flag another reap immediately as we
  291. * have to wait for the old payload to be destroyed by RCU before we
  292. * can reap the keys to which it refers.
  293. */
  294. found_keyring:
  295. spin_unlock(&key_serial_lock);
  296. keyring_gc(key, limit);
  297. goto maybe_resched;
  298. /* We found a dead key that is still referenced. Reset its type and
  299. * destroy its payload with its semaphore held.
  300. */
  301. destroy_dead_key:
  302. spin_unlock(&key_serial_lock);
  303. kdebug("destroy key %d", key->serial);
  304. down_write(&key->sem);
  305. key->type = &key_type_dead;
  306. if (key_gc_dead_keytype->destroy)
  307. key_gc_dead_keytype->destroy(key);
  308. memset(&key->payload, KEY_DESTROY, sizeof(key->payload));
  309. up_write(&key->sem);
  310. goto maybe_resched;
  311. }