pid_list.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (C) 2021 VMware Inc, Steven Rostedt <[email protected]>
  4. */
  5. #include <linux/spinlock.h>
  6. #include <linux/irq_work.h>
  7. #include <linux/slab.h>
  8. #include "trace.h"
  9. /* See pid_list.h for details */
  10. static inline union lower_chunk *get_lower_chunk(struct trace_pid_list *pid_list)
  11. {
  12. union lower_chunk *chunk;
  13. lockdep_assert_held(&pid_list->lock);
  14. if (!pid_list->lower_list)
  15. return NULL;
  16. chunk = pid_list->lower_list;
  17. pid_list->lower_list = chunk->next;
  18. pid_list->free_lower_chunks--;
  19. WARN_ON_ONCE(pid_list->free_lower_chunks < 0);
  20. chunk->next = NULL;
  21. /*
  22. * If a refill needs to happen, it can not happen here
  23. * as the scheduler run queue locks are held.
  24. */
  25. if (pid_list->free_lower_chunks <= CHUNK_REALLOC)
  26. irq_work_queue(&pid_list->refill_irqwork);
  27. return chunk;
  28. }
  29. static inline union upper_chunk *get_upper_chunk(struct trace_pid_list *pid_list)
  30. {
  31. union upper_chunk *chunk;
  32. lockdep_assert_held(&pid_list->lock);
  33. if (!pid_list->upper_list)
  34. return NULL;
  35. chunk = pid_list->upper_list;
  36. pid_list->upper_list = chunk->next;
  37. pid_list->free_upper_chunks--;
  38. WARN_ON_ONCE(pid_list->free_upper_chunks < 0);
  39. chunk->next = NULL;
  40. /*
  41. * If a refill needs to happen, it can not happen here
  42. * as the scheduler run queue locks are held.
  43. */
  44. if (pid_list->free_upper_chunks <= CHUNK_REALLOC)
  45. irq_work_queue(&pid_list->refill_irqwork);
  46. return chunk;
  47. }
  48. static inline void put_lower_chunk(struct trace_pid_list *pid_list,
  49. union lower_chunk *chunk)
  50. {
  51. lockdep_assert_held(&pid_list->lock);
  52. chunk->next = pid_list->lower_list;
  53. pid_list->lower_list = chunk;
  54. pid_list->free_lower_chunks++;
  55. }
  56. static inline void put_upper_chunk(struct trace_pid_list *pid_list,
  57. union upper_chunk *chunk)
  58. {
  59. lockdep_assert_held(&pid_list->lock);
  60. chunk->next = pid_list->upper_list;
  61. pid_list->upper_list = chunk;
  62. pid_list->free_upper_chunks++;
  63. }
  64. static inline bool upper_empty(union upper_chunk *chunk)
  65. {
  66. /*
  67. * If chunk->data has no lower chunks, it will be the same
  68. * as a zeroed bitmask. Use find_first_bit() to test it
  69. * and if it doesn't find any bits set, then the array
  70. * is empty.
  71. */
  72. int bit = find_first_bit((unsigned long *)chunk->data,
  73. sizeof(chunk->data) * 8);
  74. return bit >= sizeof(chunk->data) * 8;
  75. }
  76. static inline int pid_split(unsigned int pid, unsigned int *upper1,
  77. unsigned int *upper2, unsigned int *lower)
  78. {
  79. /* MAX_PID should cover all pids */
  80. BUILD_BUG_ON(MAX_PID < PID_MAX_LIMIT);
  81. /* In case a bad pid is passed in, then fail */
  82. if (unlikely(pid >= MAX_PID))
  83. return -1;
  84. *upper1 = (pid >> UPPER1_SHIFT) & UPPER_MASK;
  85. *upper2 = (pid >> UPPER2_SHIFT) & UPPER_MASK;
  86. *lower = pid & LOWER_MASK;
  87. return 0;
  88. }
  89. static inline unsigned int pid_join(unsigned int upper1,
  90. unsigned int upper2, unsigned int lower)
  91. {
  92. return ((upper1 & UPPER_MASK) << UPPER1_SHIFT) |
  93. ((upper2 & UPPER_MASK) << UPPER2_SHIFT) |
  94. (lower & LOWER_MASK);
  95. }
  96. /**
  97. * trace_pid_list_is_set - test if the pid is set in the list
  98. * @pid_list: The pid list to test
  99. * @pid: The pid to see if set in the list.
  100. *
  101. * Tests if @pid is set in the @pid_list. This is usually called
  102. * from the scheduler when a task is scheduled. Its pid is checked
  103. * if it should be traced or not.
  104. *
  105. * Return true if the pid is in the list, false otherwise.
  106. */
  107. bool trace_pid_list_is_set(struct trace_pid_list *pid_list, unsigned int pid)
  108. {
  109. union upper_chunk *upper_chunk;
  110. union lower_chunk *lower_chunk;
  111. unsigned long flags;
  112. unsigned int upper1;
  113. unsigned int upper2;
  114. unsigned int lower;
  115. bool ret = false;
  116. if (!pid_list)
  117. return false;
  118. if (pid_split(pid, &upper1, &upper2, &lower) < 0)
  119. return false;
  120. raw_spin_lock_irqsave(&pid_list->lock, flags);
  121. upper_chunk = pid_list->upper[upper1];
  122. if (upper_chunk) {
  123. lower_chunk = upper_chunk->data[upper2];
  124. if (lower_chunk)
  125. ret = test_bit(lower, lower_chunk->data);
  126. }
  127. raw_spin_unlock_irqrestore(&pid_list->lock, flags);
  128. return ret;
  129. }
  130. /**
  131. * trace_pid_list_set - add a pid to the list
  132. * @pid_list: The pid list to add the @pid to.
  133. * @pid: The pid to add.
  134. *
  135. * Adds @pid to @pid_list. This is usually done explicitly by a user
  136. * adding a task to be traced, or indirectly by the fork function
  137. * when children should be traced and a task's pid is in the list.
  138. *
  139. * Return 0 on success, negative otherwise.
  140. */
  141. int trace_pid_list_set(struct trace_pid_list *pid_list, unsigned int pid)
  142. {
  143. union upper_chunk *upper_chunk;
  144. union lower_chunk *lower_chunk;
  145. unsigned long flags;
  146. unsigned int upper1;
  147. unsigned int upper2;
  148. unsigned int lower;
  149. int ret;
  150. if (!pid_list)
  151. return -ENODEV;
  152. if (pid_split(pid, &upper1, &upper2, &lower) < 0)
  153. return -EINVAL;
  154. raw_spin_lock_irqsave(&pid_list->lock, flags);
  155. upper_chunk = pid_list->upper[upper1];
  156. if (!upper_chunk) {
  157. upper_chunk = get_upper_chunk(pid_list);
  158. if (!upper_chunk) {
  159. ret = -ENOMEM;
  160. goto out;
  161. }
  162. pid_list->upper[upper1] = upper_chunk;
  163. }
  164. lower_chunk = upper_chunk->data[upper2];
  165. if (!lower_chunk) {
  166. lower_chunk = get_lower_chunk(pid_list);
  167. if (!lower_chunk) {
  168. ret = -ENOMEM;
  169. goto out;
  170. }
  171. upper_chunk->data[upper2] = lower_chunk;
  172. }
  173. set_bit(lower, lower_chunk->data);
  174. ret = 0;
  175. out:
  176. raw_spin_unlock_irqrestore(&pid_list->lock, flags);
  177. return ret;
  178. }
  179. /**
  180. * trace_pid_list_clear - remove a pid from the list
  181. * @pid_list: The pid list to remove the @pid from.
  182. * @pid: The pid to remove.
  183. *
  184. * Removes @pid from @pid_list. This is usually done explicitly by a user
  185. * removing tasks from tracing, or indirectly by the exit function
  186. * when a task that is set to be traced exits.
  187. *
  188. * Return 0 on success, negative otherwise.
  189. */
  190. int trace_pid_list_clear(struct trace_pid_list *pid_list, unsigned int pid)
  191. {
  192. union upper_chunk *upper_chunk;
  193. union lower_chunk *lower_chunk;
  194. unsigned long flags;
  195. unsigned int upper1;
  196. unsigned int upper2;
  197. unsigned int lower;
  198. if (!pid_list)
  199. return -ENODEV;
  200. if (pid_split(pid, &upper1, &upper2, &lower) < 0)
  201. return -EINVAL;
  202. raw_spin_lock_irqsave(&pid_list->lock, flags);
  203. upper_chunk = pid_list->upper[upper1];
  204. if (!upper_chunk)
  205. goto out;
  206. lower_chunk = upper_chunk->data[upper2];
  207. if (!lower_chunk)
  208. goto out;
  209. clear_bit(lower, lower_chunk->data);
  210. /* if there's no more bits set, add it to the free list */
  211. if (find_first_bit(lower_chunk->data, LOWER_MAX) >= LOWER_MAX) {
  212. put_lower_chunk(pid_list, lower_chunk);
  213. upper_chunk->data[upper2] = NULL;
  214. if (upper_empty(upper_chunk)) {
  215. put_upper_chunk(pid_list, upper_chunk);
  216. pid_list->upper[upper1] = NULL;
  217. }
  218. }
  219. out:
  220. raw_spin_unlock_irqrestore(&pid_list->lock, flags);
  221. return 0;
  222. }
  223. /**
  224. * trace_pid_list_next - return the next pid in the list
  225. * @pid_list: The pid list to examine.
  226. * @pid: The pid to start from
  227. * @next: The pointer to place the pid that is set starting from @pid.
  228. *
  229. * Looks for the next consecutive pid that is in @pid_list starting
  230. * at the pid specified by @pid. If one is set (including @pid), then
  231. * that pid is placed into @next.
  232. *
  233. * Return 0 when a pid is found, -1 if there are no more pids included.
  234. */
  235. int trace_pid_list_next(struct trace_pid_list *pid_list, unsigned int pid,
  236. unsigned int *next)
  237. {
  238. union upper_chunk *upper_chunk;
  239. union lower_chunk *lower_chunk;
  240. unsigned long flags;
  241. unsigned int upper1;
  242. unsigned int upper2;
  243. unsigned int lower;
  244. if (!pid_list)
  245. return -ENODEV;
  246. if (pid_split(pid, &upper1, &upper2, &lower) < 0)
  247. return -EINVAL;
  248. raw_spin_lock_irqsave(&pid_list->lock, flags);
  249. for (; upper1 <= UPPER_MASK; upper1++, upper2 = 0) {
  250. upper_chunk = pid_list->upper[upper1];
  251. if (!upper_chunk)
  252. continue;
  253. for (; upper2 <= UPPER_MASK; upper2++, lower = 0) {
  254. lower_chunk = upper_chunk->data[upper2];
  255. if (!lower_chunk)
  256. continue;
  257. lower = find_next_bit(lower_chunk->data, LOWER_MAX,
  258. lower);
  259. if (lower < LOWER_MAX)
  260. goto found;
  261. }
  262. }
  263. found:
  264. raw_spin_unlock_irqrestore(&pid_list->lock, flags);
  265. if (upper1 > UPPER_MASK)
  266. return -1;
  267. *next = pid_join(upper1, upper2, lower);
  268. return 0;
  269. }
  270. /**
  271. * trace_pid_list_first - return the first pid in the list
  272. * @pid_list: The pid list to examine.
  273. * @pid: The pointer to place the pid first found pid that is set.
  274. *
  275. * Looks for the first pid that is set in @pid_list, and places it
  276. * into @pid if found.
  277. *
  278. * Return 0 when a pid is found, -1 if there are no pids set.
  279. */
  280. int trace_pid_list_first(struct trace_pid_list *pid_list, unsigned int *pid)
  281. {
  282. return trace_pid_list_next(pid_list, 0, pid);
  283. }
  284. static void pid_list_refill_irq(struct irq_work *iwork)
  285. {
  286. struct trace_pid_list *pid_list = container_of(iwork, struct trace_pid_list,
  287. refill_irqwork);
  288. union upper_chunk *upper = NULL;
  289. union lower_chunk *lower = NULL;
  290. union upper_chunk **upper_next = &upper;
  291. union lower_chunk **lower_next = &lower;
  292. int upper_count;
  293. int lower_count;
  294. int ucnt = 0;
  295. int lcnt = 0;
  296. again:
  297. raw_spin_lock(&pid_list->lock);
  298. upper_count = CHUNK_ALLOC - pid_list->free_upper_chunks;
  299. lower_count = CHUNK_ALLOC - pid_list->free_lower_chunks;
  300. raw_spin_unlock(&pid_list->lock);
  301. if (upper_count <= 0 && lower_count <= 0)
  302. return;
  303. while (upper_count-- > 0) {
  304. union upper_chunk *chunk;
  305. chunk = kzalloc(sizeof(*chunk), GFP_KERNEL);
  306. if (!chunk)
  307. break;
  308. *upper_next = chunk;
  309. upper_next = &chunk->next;
  310. ucnt++;
  311. }
  312. while (lower_count-- > 0) {
  313. union lower_chunk *chunk;
  314. chunk = kzalloc(sizeof(*chunk), GFP_KERNEL);
  315. if (!chunk)
  316. break;
  317. *lower_next = chunk;
  318. lower_next = &chunk->next;
  319. lcnt++;
  320. }
  321. raw_spin_lock(&pid_list->lock);
  322. if (upper) {
  323. *upper_next = pid_list->upper_list;
  324. pid_list->upper_list = upper;
  325. pid_list->free_upper_chunks += ucnt;
  326. }
  327. if (lower) {
  328. *lower_next = pid_list->lower_list;
  329. pid_list->lower_list = lower;
  330. pid_list->free_lower_chunks += lcnt;
  331. }
  332. raw_spin_unlock(&pid_list->lock);
  333. /*
  334. * On success of allocating all the chunks, both counters
  335. * will be less than zero. If they are not, then an allocation
  336. * failed, and we should not try again.
  337. */
  338. if (upper_count >= 0 || lower_count >= 0)
  339. return;
  340. /*
  341. * When the locks were released, free chunks could have
  342. * been used and allocation needs to be done again. Might as
  343. * well allocate it now.
  344. */
  345. goto again;
  346. }
  347. /**
  348. * trace_pid_list_alloc - create a new pid_list
  349. *
  350. * Allocates a new pid_list to store pids into.
  351. *
  352. * Returns the pid_list on success, NULL otherwise.
  353. */
  354. struct trace_pid_list *trace_pid_list_alloc(void)
  355. {
  356. struct trace_pid_list *pid_list;
  357. int i;
  358. /* According to linux/thread.h, pids can be no bigger that 30 bits */
  359. WARN_ON_ONCE(pid_max > (1 << 30));
  360. pid_list = kzalloc(sizeof(*pid_list), GFP_KERNEL);
  361. if (!pid_list)
  362. return NULL;
  363. init_irq_work(&pid_list->refill_irqwork, pid_list_refill_irq);
  364. raw_spin_lock_init(&pid_list->lock);
  365. for (i = 0; i < CHUNK_ALLOC; i++) {
  366. union upper_chunk *chunk;
  367. chunk = kzalloc(sizeof(*chunk), GFP_KERNEL);
  368. if (!chunk)
  369. break;
  370. chunk->next = pid_list->upper_list;
  371. pid_list->upper_list = chunk;
  372. pid_list->free_upper_chunks++;
  373. }
  374. for (i = 0; i < CHUNK_ALLOC; i++) {
  375. union lower_chunk *chunk;
  376. chunk = kzalloc(sizeof(*chunk), GFP_KERNEL);
  377. if (!chunk)
  378. break;
  379. chunk->next = pid_list->lower_list;
  380. pid_list->lower_list = chunk;
  381. pid_list->free_lower_chunks++;
  382. }
  383. return pid_list;
  384. }
  385. /**
  386. * trace_pid_list_free - Frees an allocated pid_list.
  387. *
  388. * Frees the memory for a pid_list that was allocated.
  389. */
  390. void trace_pid_list_free(struct trace_pid_list *pid_list)
  391. {
  392. union upper_chunk *upper;
  393. union lower_chunk *lower;
  394. int i, j;
  395. if (!pid_list)
  396. return;
  397. irq_work_sync(&pid_list->refill_irqwork);
  398. while (pid_list->lower_list) {
  399. union lower_chunk *chunk;
  400. chunk = pid_list->lower_list;
  401. pid_list->lower_list = pid_list->lower_list->next;
  402. kfree(chunk);
  403. }
  404. while (pid_list->upper_list) {
  405. union upper_chunk *chunk;
  406. chunk = pid_list->upper_list;
  407. pid_list->upper_list = pid_list->upper_list->next;
  408. kfree(chunk);
  409. }
  410. for (i = 0; i < UPPER1_SIZE; i++) {
  411. upper = pid_list->upper[i];
  412. if (upper) {
  413. for (j = 0; j < UPPER2_SIZE; j++) {
  414. lower = upper->data[j];
  415. kfree(lower);
  416. }
  417. kfree(upper);
  418. }
  419. }
  420. kfree(pid_list);
  421. }