spsc_queue.h 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
  1. /*
  2. * Copyright 2017 Advanced Micro Devices, Inc.
  3. *
  4. * Permission is hereby granted, free of charge, to any person obtaining a
  5. * copy of this software and associated documentation files (the "Software"),
  6. * to deal in the Software without restriction, including without limitation
  7. * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  8. * and/or sell copies of the Software, and to permit persons to whom the
  9. * Software is furnished to do so, subject to the following conditions:
  10. *
  11. * The above copyright notice and this permission notice shall be included in
  12. * all copies or substantial portions of the Software.
  13. *
  14. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15. * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16. * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  17. * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR
  18. * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  19. * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  20. * OTHER DEALINGS IN THE SOFTWARE.
  21. *
  22. */
  23. #ifndef DRM_SCHEDULER_SPSC_QUEUE_H_
  24. #define DRM_SCHEDULER_SPSC_QUEUE_H_
  25. #include <linux/atomic.h>
  26. #include <linux/preempt.h>
  27. /** SPSC lockless queue */
  28. struct spsc_node {
  29. /* Stores spsc_node* */
  30. struct spsc_node *next;
  31. };
  32. struct spsc_queue {
  33. struct spsc_node *head;
  34. /* atomic pointer to struct spsc_node* */
  35. atomic_long_t tail;
  36. atomic_t job_count;
  37. };
  38. static inline void spsc_queue_init(struct spsc_queue *queue)
  39. {
  40. queue->head = NULL;
  41. atomic_long_set(&queue->tail, (long)&queue->head);
  42. atomic_set(&queue->job_count, 0);
  43. }
  44. static inline struct spsc_node *spsc_queue_peek(struct spsc_queue *queue)
  45. {
  46. return queue->head;
  47. }
  48. static inline int spsc_queue_count(struct spsc_queue *queue)
  49. {
  50. return atomic_read(&queue->job_count);
  51. }
  52. static inline bool spsc_queue_push(struct spsc_queue *queue, struct spsc_node *node)
  53. {
  54. struct spsc_node **tail;
  55. node->next = NULL;
  56. preempt_disable();
  57. tail = (struct spsc_node **)atomic_long_xchg(&queue->tail, (long)&node->next);
  58. WRITE_ONCE(*tail, node);
  59. atomic_inc(&queue->job_count);
  60. /*
  61. * In case of first element verify new node will be visible to the consumer
  62. * thread when we ping the kernel thread that there is new work to do.
  63. */
  64. smp_wmb();
  65. preempt_enable();
  66. return tail == &queue->head;
  67. }
  68. static inline struct spsc_node *spsc_queue_pop(struct spsc_queue *queue)
  69. {
  70. struct spsc_node *next, *node;
  71. /* Verify reading from memory and not the cache */
  72. smp_rmb();
  73. node = READ_ONCE(queue->head);
  74. if (!node)
  75. return NULL;
  76. next = READ_ONCE(node->next);
  77. WRITE_ONCE(queue->head, next);
  78. if (unlikely(!next)) {
  79. /* slowpath for the last element in the queue */
  80. if (atomic_long_cmpxchg(&queue->tail,
  81. (long)&node->next, (long) &queue->head) != (long)&node->next) {
  82. /* Updating tail failed wait for new next to appear */
  83. do {
  84. smp_rmb();
  85. } while (unlikely(!(queue->head = READ_ONCE(node->next))));
  86. }
  87. }
  88. atomic_dec(&queue->job_count);
  89. return node;
  90. }
  91. #endif /* DRM_SCHEDULER_SPSC_QUEUE_H_ */