1 // SPDX-License-Identifier: GPL-2.0
3 * tracing_map - lock-free map for tracing
5 * Copyright (C) 2015 Tom Zanussi <tom.zanussi@linux.intel.com>
7 * tracing_map implementation inspired by lock-free map algorithms
8 * originated by Dr. Cliff Click:
10 * http://www.azulsystems.com/blog/cliff/2007-03-26-non-blocking-hashtable
11 * http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
14 #include <linux/vmalloc.h>
15 #include <linux/jhash.h>
16 #include <linux/slab.h>
17 #include <linux/sort.h>
18 #include <linux/kmemleak.h>
20 #include "tracing_map.h"
24 * NOTE: For a detailed description of the data structures used by
25 * these functions (such as tracing_map_elt) please see the overview
26 * of tracing_map data structures at the beginning of tracing_map.h.
30 * tracing_map_update_sum - Add a value to a tracing_map_elt's sum field
31 * @elt: The tracing_map_elt
32 * @i: The index of the given sum associated with the tracing_map_elt
33 * @n: The value to add to the sum
35 * Add n to sum i associated with the specified tracing_map_elt
36 * instance. The index i is the index returned by the call to
37 * tracing_map_add_sum_field() when the tracing map was set up.
39 void tracing_map_update_sum(struct tracing_map_elt
*elt
, unsigned int i
, u64 n
)
41 atomic64_add(n
, &elt
->fields
[i
].sum
);
45 * tracing_map_read_sum - Return the value of a tracing_map_elt's sum field
46 * @elt: The tracing_map_elt
47 * @i: The index of the given sum associated with the tracing_map_elt
49 * Retrieve the value of the sum i associated with the specified
50 * tracing_map_elt instance. The index i is the index returned by the
51 * call to tracing_map_add_sum_field() when the tracing map was set
54 * Return: The sum associated with field i for elt.
56 u64
tracing_map_read_sum(struct tracing_map_elt
*elt
, unsigned int i
)
58 return (u64
)atomic64_read(&elt
->fields
[i
].sum
);
62 * tracing_map_set_var - Assign a tracing_map_elt's variable field
63 * @elt: The tracing_map_elt
64 * @i: The index of the given variable associated with the tracing_map_elt
65 * @n: The value to assign
67 * Assign n to variable i associated with the specified tracing_map_elt
68 * instance. The index i is the index returned by the call to
69 * tracing_map_add_var() when the tracing map was set up.
71 void tracing_map_set_var(struct tracing_map_elt
*elt
, unsigned int i
, u64 n
)
73 atomic64_set(&elt
->vars
[i
], n
);
74 elt
->var_set
[i
] = true;
78 * tracing_map_var_set - Return whether or not a variable has been set
79 * @elt: The tracing_map_elt
80 * @i: The index of the given variable associated with the tracing_map_elt
82 * Return true if the variable has been set, false otherwise. The
83 * index i is the index returned by the call to tracing_map_add_var()
84 * when the tracing map was set up.
86 bool tracing_map_var_set(struct tracing_map_elt
*elt
, unsigned int i
)
88 return elt
->var_set
[i
];
92 * tracing_map_read_var - Return the value of a tracing_map_elt's variable field
93 * @elt: The tracing_map_elt
94 * @i: The index of the given variable associated with the tracing_map_elt
96 * Retrieve the value of the variable i associated with the specified
97 * tracing_map_elt instance. The index i is the index returned by the
98 * call to tracing_map_add_var() when the tracing map was set
101 * Return: The variable value associated with field i for elt.
103 u64
tracing_map_read_var(struct tracing_map_elt
*elt
, unsigned int i
)
105 return (u64
)atomic64_read(&elt
->vars
[i
]);
109 * tracing_map_read_var_once - Return and reset a tracing_map_elt's variable field
110 * @elt: The tracing_map_elt
111 * @i: The index of the given variable associated with the tracing_map_elt
113 * Retrieve the value of the variable i associated with the specified
114 * tracing_map_elt instance, and reset the variable to the 'not set'
115 * state. The index i is the index returned by the call to
116 * tracing_map_add_var() when the tracing map was set up. The reset
117 * essentially makes the variable a read-once variable if it's only
118 * accessed using this function.
120 * Return: The variable value associated with field i for elt.
122 u64
tracing_map_read_var_once(struct tracing_map_elt
*elt
, unsigned int i
)
124 elt
->var_set
[i
] = false;
125 return (u64
)atomic64_read(&elt
->vars
[i
]);
128 int tracing_map_cmp_string(void *val_a
, void *val_b
)
136 int tracing_map_cmp_none(void *val_a
, void *val_b
)
141 static int tracing_map_cmp_atomic64(void *val_a
, void *val_b
)
143 u64 a
= atomic64_read((atomic64_t
*)val_a
);
144 u64 b
= atomic64_read((atomic64_t
*)val_b
);
146 return (a
> b
) ? 1 : ((a
< b
) ? -1 : 0);
149 #define DEFINE_TRACING_MAP_CMP_FN(type) \
150 static int tracing_map_cmp_##type(void *val_a, void *val_b) \
152 type a = (type)(*(u64 *)val_a); \
153 type b = (type)(*(u64 *)val_b); \
155 return (a > b) ? 1 : ((a < b) ? -1 : 0); \
158 DEFINE_TRACING_MAP_CMP_FN(s64
);
159 DEFINE_TRACING_MAP_CMP_FN(u64
);
160 DEFINE_TRACING_MAP_CMP_FN(s32
);
161 DEFINE_TRACING_MAP_CMP_FN(u32
);
162 DEFINE_TRACING_MAP_CMP_FN(s16
);
163 DEFINE_TRACING_MAP_CMP_FN(u16
);
164 DEFINE_TRACING_MAP_CMP_FN(s8
);
165 DEFINE_TRACING_MAP_CMP_FN(u8
);
167 tracing_map_cmp_fn_t
tracing_map_cmp_num(int field_size
,
170 tracing_map_cmp_fn_t fn
= tracing_map_cmp_none
;
172 switch (field_size
) {
175 fn
= tracing_map_cmp_s64
;
177 fn
= tracing_map_cmp_u64
;
181 fn
= tracing_map_cmp_s32
;
183 fn
= tracing_map_cmp_u32
;
187 fn
= tracing_map_cmp_s16
;
189 fn
= tracing_map_cmp_u16
;
193 fn
= tracing_map_cmp_s8
;
195 fn
= tracing_map_cmp_u8
;
202 static int tracing_map_add_field(struct tracing_map
*map
,
203 tracing_map_cmp_fn_t cmp_fn
)
207 if (map
->n_fields
< TRACING_MAP_FIELDS_MAX
) {
209 map
->fields
[map
->n_fields
++].cmp_fn
= cmp_fn
;
216 * tracing_map_add_sum_field - Add a field describing a tracing_map sum
217 * @map: The tracing_map
219 * Add a sum field to the key and return the index identifying it in
220 * the map and associated tracing_map_elts. This is the index used
221 * for instance to update a sum for a particular tracing_map_elt using
222 * tracing_map_update_sum() or reading it via tracing_map_read_sum().
224 * Return: The index identifying the field in the map and associated
225 * tracing_map_elts, or -EINVAL on error.
227 int tracing_map_add_sum_field(struct tracing_map
*map
)
229 return tracing_map_add_field(map
, tracing_map_cmp_atomic64
);
233 * tracing_map_add_var - Add a field describing a tracing_map var
234 * @map: The tracing_map
236 * Add a var to the map and return the index identifying it in the map
237 * and associated tracing_map_elts. This is the index used for
238 * instance to update a var for a particular tracing_map_elt using
239 * tracing_map_update_var() or reading it via tracing_map_read_var().
241 * Return: The index identifying the var in the map and associated
242 * tracing_map_elts, or -EINVAL on error.
244 int tracing_map_add_var(struct tracing_map
*map
)
248 if (map
->n_vars
< TRACING_MAP_VARS_MAX
)
255 * tracing_map_add_key_field - Add a field describing a tracing_map key
256 * @map: The tracing_map
257 * @offset: The offset within the key
258 * @cmp_fn: The comparison function that will be used to sort on the key
260 * Let the map know there is a key and that if it's used as a sort key
263 * A key can be a subset of a compound key; for that purpose, the
264 * offset param is used to describe where within the compound key
265 * the key referenced by this key field resides.
267 * Return: The index identifying the field in the map and associated
268 * tracing_map_elts, or -EINVAL on error.
270 int tracing_map_add_key_field(struct tracing_map
*map
,
272 tracing_map_cmp_fn_t cmp_fn
)
275 int idx
= tracing_map_add_field(map
, cmp_fn
);
280 map
->fields
[idx
].offset
= offset
;
282 map
->key_idx
[map
->n_keys
++] = idx
;
287 static void tracing_map_array_clear(struct tracing_map_array
*a
)
294 for (i
= 0; i
< a
->n_pages
; i
++)
295 memset(a
->pages
[i
], 0, PAGE_SIZE
);
298 static void tracing_map_array_free(struct tracing_map_array
*a
)
308 for (i
= 0; i
< a
->n_pages
; i
++) {
311 kmemleak_free(a
->pages
[i
]);
312 free_page((unsigned long)a
->pages
[i
]);
321 static struct tracing_map_array
*tracing_map_array_alloc(unsigned int n_elts
,
322 unsigned int entry_size
)
324 struct tracing_map_array
*a
;
327 a
= kzalloc(sizeof(*a
), GFP_KERNEL
);
331 a
->entry_size_shift
= fls(roundup_pow_of_two(entry_size
) - 1);
332 a
->entries_per_page
= PAGE_SIZE
/ (1 << a
->entry_size_shift
);
333 a
->n_pages
= n_elts
/ a
->entries_per_page
;
336 a
->entry_shift
= fls(a
->entries_per_page
) - 1;
337 a
->entry_mask
= (1 << a
->entry_shift
) - 1;
339 a
->pages
= kcalloc(a
->n_pages
, sizeof(void *), GFP_KERNEL
);
343 for (i
= 0; i
< a
->n_pages
; i
++) {
344 a
->pages
[i
] = (void *)get_zeroed_page(GFP_KERNEL
);
347 kmemleak_alloc(a
->pages
[i
], PAGE_SIZE
, 1, GFP_KERNEL
);
352 tracing_map_array_free(a
);
358 static void tracing_map_elt_clear(struct tracing_map_elt
*elt
)
362 for (i
= 0; i
< elt
->map
->n_fields
; i
++)
363 if (elt
->fields
[i
].cmp_fn
== tracing_map_cmp_atomic64
)
364 atomic64_set(&elt
->fields
[i
].sum
, 0);
366 for (i
= 0; i
< elt
->map
->n_vars
; i
++) {
367 atomic64_set(&elt
->vars
[i
], 0);
368 elt
->var_set
[i
] = false;
371 if (elt
->map
->ops
&& elt
->map
->ops
->elt_clear
)
372 elt
->map
->ops
->elt_clear(elt
);
375 static void tracing_map_elt_init_fields(struct tracing_map_elt
*elt
)
379 tracing_map_elt_clear(elt
);
381 for (i
= 0; i
< elt
->map
->n_fields
; i
++) {
382 elt
->fields
[i
].cmp_fn
= elt
->map
->fields
[i
].cmp_fn
;
384 if (elt
->fields
[i
].cmp_fn
!= tracing_map_cmp_atomic64
)
385 elt
->fields
[i
].offset
= elt
->map
->fields
[i
].offset
;
389 static void tracing_map_elt_free(struct tracing_map_elt
*elt
)
394 if (elt
->map
->ops
&& elt
->map
->ops
->elt_free
)
395 elt
->map
->ops
->elt_free(elt
);
403 static struct tracing_map_elt
*tracing_map_elt_alloc(struct tracing_map
*map
)
405 struct tracing_map_elt
*elt
;
408 elt
= kzalloc(sizeof(*elt
), GFP_KERNEL
);
410 return ERR_PTR(-ENOMEM
);
414 elt
->key
= kzalloc(map
->key_size
, GFP_KERNEL
);
420 elt
->fields
= kcalloc(map
->n_fields
, sizeof(*elt
->fields
), GFP_KERNEL
);
426 elt
->vars
= kcalloc(map
->n_vars
, sizeof(*elt
->vars
), GFP_KERNEL
);
432 elt
->var_set
= kcalloc(map
->n_vars
, sizeof(*elt
->var_set
), GFP_KERNEL
);
438 tracing_map_elt_init_fields(elt
);
440 if (map
->ops
&& map
->ops
->elt_alloc
) {
441 err
= map
->ops
->elt_alloc(elt
);
447 tracing_map_elt_free(elt
);
452 static struct tracing_map_elt
*get_free_elt(struct tracing_map
*map
)
454 struct tracing_map_elt
*elt
= NULL
;
457 idx
= atomic_inc_return(&map
->next_elt
);
458 if (idx
< map
->max_elts
) {
459 elt
= *(TRACING_MAP_ELT(map
->elts
, idx
));
460 if (map
->ops
&& map
->ops
->elt_init
)
461 map
->ops
->elt_init(elt
);
467 static void tracing_map_free_elts(struct tracing_map
*map
)
474 for (i
= 0; i
< map
->max_elts
; i
++) {
475 tracing_map_elt_free(*(TRACING_MAP_ELT(map
->elts
, i
)));
476 *(TRACING_MAP_ELT(map
->elts
, i
)) = NULL
;
479 tracing_map_array_free(map
->elts
);
483 static int tracing_map_alloc_elts(struct tracing_map
*map
)
487 map
->elts
= tracing_map_array_alloc(map
->max_elts
,
488 sizeof(struct tracing_map_elt
*));
492 for (i
= 0; i
< map
->max_elts
; i
++) {
493 *(TRACING_MAP_ELT(map
->elts
, i
)) = tracing_map_elt_alloc(map
);
494 if (IS_ERR(*(TRACING_MAP_ELT(map
->elts
, i
)))) {
495 *(TRACING_MAP_ELT(map
->elts
, i
)) = NULL
;
496 tracing_map_free_elts(map
);
505 static inline bool keys_match(void *key
, void *test_key
, unsigned key_size
)
509 if (memcmp(key
, test_key
, key_size
))
515 static inline struct tracing_map_elt
*
516 __tracing_map_insert(struct tracing_map
*map
, void *key
, bool lookup_only
)
518 u32 idx
, key_hash
, test_key
;
520 struct tracing_map_entry
*entry
;
521 struct tracing_map_elt
*val
;
523 key_hash
= jhash(key
, map
->key_size
, 0);
526 idx
= key_hash
>> (32 - (map
->map_bits
+ 1));
529 idx
&= (map
->map_size
- 1);
530 entry
= TRACING_MAP_ENTRY(map
->map
, idx
);
531 test_key
= entry
->key
;
533 if (test_key
&& test_key
== key_hash
) {
534 val
= READ_ONCE(entry
->val
);
536 keys_match(key
, val
->key
, map
->key_size
)) {
538 atomic64_inc(&map
->hits
);
540 } else if (unlikely(!val
)) {
542 * The key is present. But, val (pointer to elt
543 * struct) is still NULL. which means some other
544 * thread is in the process of inserting an
547 * On top of that, it's key_hash is same as the
548 * one being inserted right now. So, it's
549 * possible that the element has the same
554 if (dup_try
> map
->map_size
) {
555 atomic64_inc(&map
->drops
);
566 if (!cmpxchg(&entry
->key
, 0, key_hash
)) {
567 struct tracing_map_elt
*elt
;
569 elt
= get_free_elt(map
);
571 atomic64_inc(&map
->drops
);
576 memcpy(elt
->key
, key
, map
->key_size
);
578 atomic64_inc(&map
->hits
);
583 * cmpxchg() failed. Loop around once
584 * more to check what key was inserted.
598 * tracing_map_insert - Insert key and/or retrieve val from a tracing_map
599 * @map: The tracing_map to insert into
600 * @key: The key to insert
602 * Inserts a key into a tracing_map and creates and returns a new
603 * tracing_map_elt for it, or if the key has already been inserted by
604 * a previous call, returns the tracing_map_elt already associated
605 * with it. When the map was created, the number of elements to be
606 * allocated for the map was specified (internally maintained as
607 * 'max_elts' in struct tracing_map), and that number of
608 * tracing_map_elts was created by tracing_map_init(). This is the
609 * pre-allocated pool of tracing_map_elts that tracing_map_insert()
610 * will allocate from when adding new keys. Once that pool is
611 * exhausted, tracing_map_insert() is useless and will return NULL to
612 * signal that state. There are two user-visible tracing_map
613 * variables, 'hits' and 'drops', which are updated by this function.
614 * Every time an element is either successfully inserted or retrieved,
615 * the 'hits' value is incremented. Every time an element insertion
616 * fails, the 'drops' value is incremented.
618 * This is a lock-free tracing map insertion function implementing a
619 * modified form of Cliff Click's basic insertion algorithm. It
620 * requires the table size be a power of two. To prevent any
621 * possibility of an infinite loop we always make the internal table
622 * size double the size of the requested table size (max_elts * 2).
623 * Likewise, we never reuse a slot or resize or delete elements - when
624 * we've reached max_elts entries, we simply return NULL once we've
625 * run out of entries. Readers can at any point in time traverse the
626 * tracing map and safely access the key/val pairs.
628 * Return: the tracing_map_elt pointer val associated with the key.
629 * If this was a newly inserted key, the val will be a newly allocated
630 * and associated tracing_map_elt pointer val. If the key wasn't
631 * found and the pool of tracing_map_elts has been exhausted, NULL is
632 * returned and no further insertions will succeed.
634 struct tracing_map_elt
*tracing_map_insert(struct tracing_map
*map
, void *key
)
636 return __tracing_map_insert(map
, key
, false);
640 * tracing_map_lookup - Retrieve val from a tracing_map
641 * @map: The tracing_map to perform the lookup on
642 * @key: The key to look up
644 * Looks up key in tracing_map and if found returns the matching
645 * tracing_map_elt. This is a lock-free lookup; see
646 * tracing_map_insert() for details on tracing_map and how it works.
647 * Every time an element is retrieved, the 'hits' value is
648 * incremented. There is one user-visible tracing_map variable,
649 * 'hits', which is updated by this function. Every time an element
650 * is successfully retrieved, the 'hits' value is incremented. The
651 * 'drops' value is never updated by this function.
653 * Return: the tracing_map_elt pointer val associated with the key.
654 * If the key wasn't found, NULL is returned.
656 struct tracing_map_elt
*tracing_map_lookup(struct tracing_map
*map
, void *key
)
658 return __tracing_map_insert(map
, key
, true);
662 * tracing_map_destroy - Destroy a tracing_map
663 * @map: The tracing_map to destroy
665 * Frees a tracing_map along with its associated array of
668 * Callers should make sure there are no readers or writers actively
669 * reading or inserting into the map before calling this.
671 void tracing_map_destroy(struct tracing_map
*map
)
676 tracing_map_free_elts(map
);
678 tracing_map_array_free(map
->map
);
683 * tracing_map_clear - Clear a tracing_map
684 * @map: The tracing_map to clear
686 * Resets the tracing map to a cleared or initial state. The
687 * tracing_map_elts are all cleared, and the array of struct
688 * tracing_map_entry is reset to an initialized state.
690 * Callers should make sure there are no writers actively inserting
691 * into the map before calling this.
693 void tracing_map_clear(struct tracing_map
*map
)
697 atomic_set(&map
->next_elt
, -1);
698 atomic64_set(&map
->hits
, 0);
699 atomic64_set(&map
->drops
, 0);
701 tracing_map_array_clear(map
->map
);
703 for (i
= 0; i
< map
->max_elts
; i
++)
704 tracing_map_elt_clear(*(TRACING_MAP_ELT(map
->elts
, i
)));
707 static void set_sort_key(struct tracing_map
*map
,
708 struct tracing_map_sort_key
*sort_key
)
710 map
->sort_key
= *sort_key
;
714 * tracing_map_create - Create a lock-free map and element pool
715 * @map_bits: The size of the map (2 ** map_bits)
716 * @key_size: The size of the key for the map in bytes
717 * @ops: Optional client-defined tracing_map_ops instance
718 * @private_data: Client data associated with the map
720 * Creates and sets up a map to contain 2 ** map_bits number of
721 * elements (internally maintained as 'max_elts' in struct
722 * tracing_map). Before using, map fields should be added to the map
723 * with tracing_map_add_sum_field() and tracing_map_add_key_field().
724 * tracing_map_init() should then be called to allocate the array of
725 * tracing_map_elts, in order to avoid allocating anything in the map
726 * insertion path. The user-specified map size reflects the maximum
727 * number of elements that can be contained in the table requested by
728 * the user - internally we double that in order to keep the table
729 * sparse and keep collisions manageable.
731 * A tracing_map is a special-purpose map designed to aggregate or
732 * 'sum' one or more values associated with a specific object of type
733 * tracing_map_elt, which is attached by the map to a given key.
735 * tracing_map_create() sets up the map itself, and provides
736 * operations for inserting tracing_map_elts, but doesn't allocate the
737 * tracing_map_elts themselves, or provide a means for describing the
738 * keys or sums associated with the tracing_map_elts. All
739 * tracing_map_elts for a given map have the same set of sums and
740 * keys, which are defined by the client using the functions
741 * tracing_map_add_key_field() and tracing_map_add_sum_field(). Once
742 * the fields are defined, the pool of elements allocated for the map
743 * can be created, which occurs when the client code calls
744 * tracing_map_init().
746 * When tracing_map_init() returns, tracing_map_elt elements can be
747 * inserted into the map using tracing_map_insert(). When called,
748 * tracing_map_insert() grabs a free tracing_map_elt from the pool, or
749 * finds an existing match in the map and in either case returns it.
750 * The client can then use tracing_map_update_sum() and
751 * tracing_map_read_sum() to update or read a given sum field for the
754 * The client can at any point retrieve and traverse the current set
755 * of inserted tracing_map_elts in a tracing_map, via
756 * tracing_map_sort_entries(). Sorting can be done on any field,
759 * See tracing_map.h for a description of tracing_map_ops.
761 * Return: the tracing_map pointer if successful, ERR_PTR if not.
763 struct tracing_map
*tracing_map_create(unsigned int map_bits
,
764 unsigned int key_size
,
765 const struct tracing_map_ops
*ops
,
768 struct tracing_map
*map
;
771 if (map_bits
< TRACING_MAP_BITS_MIN
||
772 map_bits
> TRACING_MAP_BITS_MAX
)
773 return ERR_PTR(-EINVAL
);
775 map
= kzalloc(sizeof(*map
), GFP_KERNEL
);
777 return ERR_PTR(-ENOMEM
);
779 map
->map_bits
= map_bits
;
780 map
->max_elts
= (1 << map_bits
);
781 atomic_set(&map
->next_elt
, -1);
783 map
->map_size
= (1 << (map_bits
+ 1));
786 map
->private_data
= private_data
;
788 map
->map
= tracing_map_array_alloc(map
->map_size
,
789 sizeof(struct tracing_map_entry
));
793 map
->key_size
= key_size
;
794 for (i
= 0; i
< TRACING_MAP_KEYS_MAX
; i
++)
795 map
->key_idx
[i
] = -1;
799 tracing_map_destroy(map
);
800 map
= ERR_PTR(-ENOMEM
);
806 * tracing_map_init - Allocate and clear a map's tracing_map_elts
807 * @map: The tracing_map to initialize
809 * Allocates a clears a pool of tracing_map_elts equal to the
810 * user-specified size of 2 ** map_bits (internally maintained as
811 * 'max_elts' in struct tracing_map). Before using, the map fields
812 * should be added to the map with tracing_map_add_sum_field() and
813 * tracing_map_add_key_field(). tracing_map_init() should then be
814 * called to allocate the array of tracing_map_elts, in order to avoid
815 * allocating anything in the map insertion path. The user-specified
816 * map size reflects the max number of elements requested by the user
817 * - internally we double that in order to keep the table sparse and
818 * keep collisions manageable.
820 * See tracing_map.h for a description of tracing_map_ops.
822 * Return: the tracing_map pointer if successful, ERR_PTR if not.
824 int tracing_map_init(struct tracing_map
*map
)
828 if (map
->n_fields
< 2)
829 return -EINVAL
; /* need at least 1 key and 1 val */
831 err
= tracing_map_alloc_elts(map
);
835 tracing_map_clear(map
);
840 static int cmp_entries_dup(const void *A
, const void *B
)
842 const struct tracing_map_sort_entry
*a
, *b
;
845 a
= *(const struct tracing_map_sort_entry
**)A
;
846 b
= *(const struct tracing_map_sort_entry
**)B
;
848 if (memcmp(a
->key
, b
->key
, a
->elt
->map
->key_size
))
854 static int cmp_entries_sum(const void *A
, const void *B
)
856 const struct tracing_map_elt
*elt_a
, *elt_b
;
857 const struct tracing_map_sort_entry
*a
, *b
;
858 struct tracing_map_sort_key
*sort_key
;
859 struct tracing_map_field
*field
;
860 tracing_map_cmp_fn_t cmp_fn
;
864 a
= *(const struct tracing_map_sort_entry
**)A
;
865 b
= *(const struct tracing_map_sort_entry
**)B
;
870 sort_key
= &elt_a
->map
->sort_key
;
872 field
= &elt_a
->fields
[sort_key
->field_idx
];
873 cmp_fn
= field
->cmp_fn
;
875 val_a
= &elt_a
->fields
[sort_key
->field_idx
].sum
;
876 val_b
= &elt_b
->fields
[sort_key
->field_idx
].sum
;
878 ret
= cmp_fn(val_a
, val_b
);
879 if (sort_key
->descending
)
885 static int cmp_entries_key(const void *A
, const void *B
)
887 const struct tracing_map_elt
*elt_a
, *elt_b
;
888 const struct tracing_map_sort_entry
*a
, *b
;
889 struct tracing_map_sort_key
*sort_key
;
890 struct tracing_map_field
*field
;
891 tracing_map_cmp_fn_t cmp_fn
;
895 a
= *(const struct tracing_map_sort_entry
**)A
;
896 b
= *(const struct tracing_map_sort_entry
**)B
;
901 sort_key
= &elt_a
->map
->sort_key
;
903 field
= &elt_a
->fields
[sort_key
->field_idx
];
905 cmp_fn
= field
->cmp_fn
;
907 val_a
= elt_a
->key
+ field
->offset
;
908 val_b
= elt_b
->key
+ field
->offset
;
910 ret
= cmp_fn(val_a
, val_b
);
911 if (sort_key
->descending
)
917 static void destroy_sort_entry(struct tracing_map_sort_entry
*entry
)
922 if (entry
->elt_copied
)
923 tracing_map_elt_free(entry
->elt
);
929 * tracing_map_destroy_sort_entries - Destroy an array of sort entries
930 * @entries: The entries to destroy
931 * @n_entries: The number of entries in the array
933 * Destroy the elements returned by a tracing_map_sort_entries() call.
935 void tracing_map_destroy_sort_entries(struct tracing_map_sort_entry
**entries
,
936 unsigned int n_entries
)
940 for (i
= 0; i
< n_entries
; i
++)
941 destroy_sort_entry(entries
[i
]);
946 static struct tracing_map_sort_entry
*
947 create_sort_entry(void *key
, struct tracing_map_elt
*elt
)
949 struct tracing_map_sort_entry
*sort_entry
;
951 sort_entry
= kzalloc(sizeof(*sort_entry
), GFP_KERNEL
);
955 sort_entry
->key
= key
;
956 sort_entry
->elt
= elt
;
961 static void detect_dups(struct tracing_map_sort_entry
**sort_entries
,
962 int n_entries
, unsigned int key_size
)
964 unsigned int dups
= 0, total_dups
= 0;
971 sort(sort_entries
, n_entries
, sizeof(struct tracing_map_sort_entry
*),
972 (int (*)(const void *, const void *))cmp_entries_dup
, NULL
);
974 key
= sort_entries
[0]->key
;
975 for (i
= 1; i
< n_entries
; i
++) {
976 if (!memcmp(sort_entries
[i
]->key
, key
, key_size
)) {
977 dups
++; total_dups
++;
980 key
= sort_entries
[i
]->key
;
984 WARN_ONCE(total_dups
> 0,
985 "Duplicates detected: %d\n", total_dups
);
988 static bool is_key(struct tracing_map
*map
, unsigned int field_idx
)
992 for (i
= 0; i
< map
->n_keys
; i
++)
993 if (map
->key_idx
[i
] == field_idx
)
998 static void sort_secondary(struct tracing_map
*map
,
999 const struct tracing_map_sort_entry
**entries
,
1000 unsigned int n_entries
,
1001 struct tracing_map_sort_key
*primary_key
,
1002 struct tracing_map_sort_key
*secondary_key
)
1004 int (*primary_fn
)(const void *, const void *);
1005 int (*secondary_fn
)(const void *, const void *);
1006 unsigned i
, start
= 0, n_sub
= 1;
1008 if (is_key(map
, primary_key
->field_idx
))
1009 primary_fn
= cmp_entries_key
;
1011 primary_fn
= cmp_entries_sum
;
1013 if (is_key(map
, secondary_key
->field_idx
))
1014 secondary_fn
= cmp_entries_key
;
1016 secondary_fn
= cmp_entries_sum
;
1018 for (i
= 0; i
< n_entries
- 1; i
++) {
1019 const struct tracing_map_sort_entry
**a
= &entries
[i
];
1020 const struct tracing_map_sort_entry
**b
= &entries
[i
+ 1];
1022 if (primary_fn(a
, b
) == 0) {
1024 if (i
< n_entries
- 2)
1034 set_sort_key(map
, secondary_key
);
1035 sort(&entries
[start
], n_sub
,
1036 sizeof(struct tracing_map_sort_entry
*),
1037 (int (*)(const void *, const void *))secondary_fn
, NULL
);
1038 set_sort_key(map
, primary_key
);
1046 * tracing_map_sort_entries - Sort the current set of tracing_map_elts in a map
1047 * @map: The tracing_map
1048 * @sort_key: The sort key to use for sorting
1049 * @sort_entries: outval: pointer to allocated and sorted array of entries
1051 * tracing_map_sort_entries() sorts the current set of entries in the
1052 * map and returns the list of tracing_map_sort_entries containing
1053 * them to the client in the sort_entries param. The client can
1054 * access the struct tracing_map_elt element of interest directly as
1055 * the 'elt' field of a returned struct tracing_map_sort_entry object.
1057 * The sort_key has only two fields: idx and descending. 'idx' refers
1058 * to the index of the field added via tracing_map_add_sum_field() or
1059 * tracing_map_add_key_field() when the tracing_map was initialized.
1060 * 'descending' is a flag that if set reverses the sort order, which
1061 * by default is ascending.
1063 * The client should not hold on to the returned array but should use
1064 * it and call tracing_map_destroy_sort_entries() when done.
1066 * Return: the number of sort_entries in the struct tracing_map_sort_entry
1067 * array, negative on error
1069 int tracing_map_sort_entries(struct tracing_map
*map
,
1070 struct tracing_map_sort_key
*sort_keys
,
1071 unsigned int n_sort_keys
,
1072 struct tracing_map_sort_entry
***sort_entries
)
1074 int (*cmp_entries_fn
)(const void *, const void *);
1075 struct tracing_map_sort_entry
*sort_entry
, **entries
;
1076 int i
, n_entries
, ret
;
1078 entries
= vmalloc(array_size(sizeof(sort_entry
), map
->max_elts
));
1082 for (i
= 0, n_entries
= 0; i
< map
->map_size
; i
++) {
1083 struct tracing_map_entry
*entry
;
1085 entry
= TRACING_MAP_ENTRY(map
->map
, i
);
1087 if (!entry
->key
|| !entry
->val
)
1090 entries
[n_entries
] = create_sort_entry(entry
->val
->key
,
1092 if (!entries
[n_entries
++]) {
1098 if (n_entries
== 0) {
1103 if (n_entries
== 1) {
1104 *sort_entries
= entries
;
1108 detect_dups(entries
, n_entries
, map
->key_size
);
1110 if (is_key(map
, sort_keys
[0].field_idx
))
1111 cmp_entries_fn
= cmp_entries_key
;
1113 cmp_entries_fn
= cmp_entries_sum
;
1115 set_sort_key(map
, &sort_keys
[0]);
1117 sort(entries
, n_entries
, sizeof(struct tracing_map_sort_entry
*),
1118 (int (*)(const void *, const void *))cmp_entries_fn
, NULL
);
1120 if (n_sort_keys
> 1)
1122 (const struct tracing_map_sort_entry
**)entries
,
1127 *sort_entries
= entries
;
1131 tracing_map_destroy_sort_entries(entries
, n_entries
);