queue_stack_maps.c 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * queue_stack_maps.c: BPF queue and stack maps
  4. *
  5. * Copyright (c) 2018 Politecnico di Torino
  6. */
  7. #include <linux/bpf.h>
  8. #include <linux/list.h>
  9. #include <linux/slab.h>
  10. #include <linux/capability.h>
  11. #include "percpu_freelist.h"
  12. #define QUEUE_STACK_CREATE_FLAG_MASK \
  13. (BPF_F_NUMA_NODE | BPF_F_ACCESS_MASK)
  14. struct bpf_queue_stack {
  15. struct bpf_map map;
  16. raw_spinlock_t lock;
  17. u32 head, tail;
  18. u32 size; /* max_entries + 1 */
  19. char elements[] __aligned(8);
  20. };
  21. static struct bpf_queue_stack *bpf_queue_stack(struct bpf_map *map)
  22. {
  23. return container_of(map, struct bpf_queue_stack, map);
  24. }
  25. static bool queue_stack_map_is_empty(struct bpf_queue_stack *qs)
  26. {
  27. return qs->head == qs->tail;
  28. }
  29. static bool queue_stack_map_is_full(struct bpf_queue_stack *qs)
  30. {
  31. u32 head = qs->head + 1;
  32. if (unlikely(head >= qs->size))
  33. head = 0;
  34. return head == qs->tail;
  35. }
  36. /* Called from syscall */
  37. static int queue_stack_map_alloc_check(union bpf_attr *attr)
  38. {
  39. if (!bpf_capable())
  40. return -EPERM;
  41. /* check sanity of attributes */
  42. if (attr->max_entries == 0 || attr->key_size != 0 ||
  43. attr->value_size == 0 ||
  44. attr->map_flags & ~QUEUE_STACK_CREATE_FLAG_MASK ||
  45. !bpf_map_flags_access_ok(attr->map_flags))
  46. return -EINVAL;
  47. if (attr->value_size > KMALLOC_MAX_SIZE)
  48. /* if value_size is bigger, the user space won't be able to
  49. * access the elements.
  50. */
  51. return -E2BIG;
  52. return 0;
  53. }
  54. static struct bpf_map *queue_stack_map_alloc(union bpf_attr *attr)
  55. {
  56. int ret, numa_node = bpf_map_attr_numa_node(attr);
  57. struct bpf_map_memory mem = {0};
  58. struct bpf_queue_stack *qs;
  59. u64 size, queue_size, cost;
  60. size = (u64) attr->max_entries + 1;
  61. cost = queue_size = sizeof(*qs) + size * attr->value_size;
  62. ret = bpf_map_charge_init(&mem, cost);
  63. if (ret < 0)
  64. return ERR_PTR(ret);
  65. qs = bpf_map_area_alloc(queue_size, numa_node);
  66. if (!qs) {
  67. bpf_map_charge_finish(&mem);
  68. return ERR_PTR(-ENOMEM);
  69. }
  70. memset(qs, 0, sizeof(*qs));
  71. bpf_map_init_from_attr(&qs->map, attr);
  72. bpf_map_charge_move(&qs->map.memory, &mem);
  73. qs->size = size;
  74. raw_spin_lock_init(&qs->lock);
  75. return &qs->map;
  76. }
  77. /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
  78. static void queue_stack_map_free(struct bpf_map *map)
  79. {
  80. struct bpf_queue_stack *qs = bpf_queue_stack(map);
  81. bpf_map_area_free(qs);
  82. }
  83. static int __queue_map_get(struct bpf_map *map, void *value, bool delete)
  84. {
  85. struct bpf_queue_stack *qs = bpf_queue_stack(map);
  86. unsigned long flags;
  87. int err = 0;
  88. void *ptr;
  89. raw_spin_lock_irqsave(&qs->lock, flags);
  90. if (queue_stack_map_is_empty(qs)) {
  91. memset(value, 0, qs->map.value_size);
  92. err = -ENOENT;
  93. goto out;
  94. }
  95. ptr = &qs->elements[qs->tail * qs->map.value_size];
  96. memcpy(value, ptr, qs->map.value_size);
  97. if (delete) {
  98. if (unlikely(++qs->tail >= qs->size))
  99. qs->tail = 0;
  100. }
  101. out:
  102. raw_spin_unlock_irqrestore(&qs->lock, flags);
  103. return err;
  104. }
  105. static int __stack_map_get(struct bpf_map *map, void *value, bool delete)
  106. {
  107. struct bpf_queue_stack *qs = bpf_queue_stack(map);
  108. unsigned long flags;
  109. int err = 0;
  110. void *ptr;
  111. u32 index;
  112. raw_spin_lock_irqsave(&qs->lock, flags);
  113. if (queue_stack_map_is_empty(qs)) {
  114. memset(value, 0, qs->map.value_size);
  115. err = -ENOENT;
  116. goto out;
  117. }
  118. index = qs->head - 1;
  119. if (unlikely(index >= qs->size))
  120. index = qs->size - 1;
  121. ptr = &qs->elements[index * qs->map.value_size];
  122. memcpy(value, ptr, qs->map.value_size);
  123. if (delete)
  124. qs->head = index;
  125. out:
  126. raw_spin_unlock_irqrestore(&qs->lock, flags);
  127. return err;
  128. }
  129. /* Called from syscall or from eBPF program */
  130. static int queue_map_peek_elem(struct bpf_map *map, void *value)
  131. {
  132. return __queue_map_get(map, value, false);
  133. }
  134. /* Called from syscall or from eBPF program */
  135. static int stack_map_peek_elem(struct bpf_map *map, void *value)
  136. {
  137. return __stack_map_get(map, value, false);
  138. }
  139. /* Called from syscall or from eBPF program */
  140. static int queue_map_pop_elem(struct bpf_map *map, void *value)
  141. {
  142. return __queue_map_get(map, value, true);
  143. }
  144. /* Called from syscall or from eBPF program */
  145. static int stack_map_pop_elem(struct bpf_map *map, void *value)
  146. {
  147. return __stack_map_get(map, value, true);
  148. }
  149. /* Called from syscall or from eBPF program */
  150. static int queue_stack_map_push_elem(struct bpf_map *map, void *value,
  151. u64 flags)
  152. {
  153. struct bpf_queue_stack *qs = bpf_queue_stack(map);
  154. unsigned long irq_flags;
  155. int err = 0;
  156. void *dst;
  157. /* BPF_EXIST is used to force making room for a new element in case the
  158. * map is full
  159. */
  160. bool replace = (flags & BPF_EXIST);
  161. /* Check supported flags for queue and stack maps */
  162. if (flags & BPF_NOEXIST || flags > BPF_EXIST)
  163. return -EINVAL;
  164. raw_spin_lock_irqsave(&qs->lock, irq_flags);
  165. if (queue_stack_map_is_full(qs)) {
  166. if (!replace) {
  167. err = -E2BIG;
  168. goto out;
  169. }
  170. /* advance tail pointer to overwrite oldest element */
  171. if (unlikely(++qs->tail >= qs->size))
  172. qs->tail = 0;
  173. }
  174. dst = &qs->elements[qs->head * qs->map.value_size];
  175. memcpy(dst, value, qs->map.value_size);
  176. if (unlikely(++qs->head >= qs->size))
  177. qs->head = 0;
  178. out:
  179. raw_spin_unlock_irqrestore(&qs->lock, irq_flags);
  180. return err;
  181. }
  182. /* Called from syscall or from eBPF program */
  183. static void *queue_stack_map_lookup_elem(struct bpf_map *map, void *key)
  184. {
  185. return NULL;
  186. }
  187. /* Called from syscall or from eBPF program */
  188. static int queue_stack_map_update_elem(struct bpf_map *map, void *key,
  189. void *value, u64 flags)
  190. {
  191. return -EINVAL;
  192. }
  193. /* Called from syscall or from eBPF program */
  194. static int queue_stack_map_delete_elem(struct bpf_map *map, void *key)
  195. {
  196. return -EINVAL;
  197. }
  198. /* Called from syscall */
  199. static int queue_stack_map_get_next_key(struct bpf_map *map, void *key,
  200. void *next_key)
  201. {
  202. return -EINVAL;
  203. }
  204. static int queue_map_btf_id;
  205. const struct bpf_map_ops queue_map_ops = {
  206. .map_meta_equal = bpf_map_meta_equal,
  207. .map_alloc_check = queue_stack_map_alloc_check,
  208. .map_alloc = queue_stack_map_alloc,
  209. .map_free = queue_stack_map_free,
  210. .map_lookup_elem = queue_stack_map_lookup_elem,
  211. .map_update_elem = queue_stack_map_update_elem,
  212. .map_delete_elem = queue_stack_map_delete_elem,
  213. .map_push_elem = queue_stack_map_push_elem,
  214. .map_pop_elem = queue_map_pop_elem,
  215. .map_peek_elem = queue_map_peek_elem,
  216. .map_get_next_key = queue_stack_map_get_next_key,
  217. .map_btf_name = "bpf_queue_stack",
  218. .map_btf_id = &queue_map_btf_id,
  219. };
  220. static int stack_map_btf_id;
  221. const struct bpf_map_ops stack_map_ops = {
  222. .map_meta_equal = bpf_map_meta_equal,
  223. .map_alloc_check = queue_stack_map_alloc_check,
  224. .map_alloc = queue_stack_map_alloc,
  225. .map_free = queue_stack_map_free,
  226. .map_lookup_elem = queue_stack_map_lookup_elem,
  227. .map_update_elem = queue_stack_map_update_elem,
  228. .map_delete_elem = queue_stack_map_delete_elem,
  229. .map_push_elem = queue_stack_map_push_elem,
  230. .map_pop_elem = stack_map_pop_elem,
  231. .map_peek_elem = stack_map_peek_elem,
  232. .map_get_next_key = queue_stack_map_get_next_key,
  233. .map_btf_name = "bpf_queue_stack",
  234. .map_btf_id = &stack_map_btf_id,
  235. };