3  * tracing_map - lock-free map for tracing
7  * tracing_map implementation inspired by lock-free map algorithms
37  * tracing_map_add_sum_field() when the tracing map was set up.
51  * call to tracing_map_add_sum_field() when the tracing map was set
69  * tracing_map_add_var() when the tracing map was set up.
84  * when the tracing map was set up.
98  * call to tracing_map_add_var() when the tracing map was set
116  * tracing_map_add_var() when the tracing map was set up.  The reset
202 static int tracing_map_add_field(struct tracing_map *map,  in tracing_map_add_field()  argument
207 	if (map->n_fields < TRACING_MAP_FIELDS_MAX) {  in tracing_map_add_field()
208 		ret = map->n_fields;  in tracing_map_add_field()
209 		map->fields[map->n_fields++].cmp_fn = cmp_fn;  in tracing_map_add_field()
217  * @map: The tracing_map
220  * the map and associated tracing_map_elts.  This is the index used
224  * Return: The index identifying the field in the map and associated
227 int tracing_map_add_sum_field(struct tracing_map *map)  in tracing_map_add_sum_field()  argument
229 	return tracing_map_add_field(map, tracing_map_cmp_atomic64);  in tracing_map_add_sum_field()
234  * @map: The tracing_map
236  * Add a var to the map and return the index identifying it in the map
241  * Return: The index identifying the var in the map and associated
244 int tracing_map_add_var(struct tracing_map *map)  in tracing_map_add_var()  argument
248 	if (map->n_vars < TRACING_MAP_VARS_MAX)  in tracing_map_add_var()
249 		ret = map->n_vars++;  in tracing_map_add_var()
256  * @map: The tracing_map
260  * Let the map know there is a key and that if it's used as a sort key
267  * Return: The index identifying the field in the map and associated
270 int tracing_map_add_key_field(struct tracing_map *map,  in tracing_map_add_key_field()  argument
275 	int idx = tracing_map_add_field(map, cmp_fn);  in tracing_map_add_key_field()
280 	map->fields[idx].offset = offset;  in tracing_map_add_key_field()
282 	map->key_idx[map->n_keys++] = idx;  in tracing_map_add_key_field()
362 	for (i = 0; i < elt->map->n_fields; i++)  in tracing_map_elt_clear()
366 	for (i = 0; i < elt->map->n_vars; i++) {  in tracing_map_elt_clear()
371 	if (elt->map->ops && elt->map->ops->elt_clear)  in tracing_map_elt_clear()
372 		elt->map->ops->elt_clear(elt);  in tracing_map_elt_clear()
381 	for (i = 0; i < elt->map->n_fields; i++) {  in tracing_map_elt_init_fields()
382 		elt->fields[i].cmp_fn = elt->map->fields[i].cmp_fn;  in tracing_map_elt_init_fields()
385 			elt->fields[i].offset = elt->map->fields[i].offset;  in tracing_map_elt_init_fields()
394 	if (elt->map->ops && elt->map->ops->elt_free)  in tracing_map_elt_free()
395 		elt->map->ops->elt_free(elt);  in tracing_map_elt_free()
403 static struct tracing_map_elt *tracing_map_elt_alloc(struct tracing_map *map)  in tracing_map_elt_alloc()  argument
412 	elt->map = map;  in tracing_map_elt_alloc()
414 	elt->key = kzalloc(map->key_size, GFP_KERNEL);  in tracing_map_elt_alloc()
420 	elt->fields = kcalloc(map->n_fields, sizeof(*elt->fields), GFP_KERNEL);  in tracing_map_elt_alloc()
426 	elt->vars = kcalloc(map->n_vars, sizeof(*elt->vars), GFP_KERNEL);  in tracing_map_elt_alloc()
432 	elt->var_set = kcalloc(map->n_vars, sizeof(*elt->var_set), GFP_KERNEL);  in tracing_map_elt_alloc()
440 	if (map->ops && map->ops->elt_alloc) {  in tracing_map_elt_alloc()
441 		err = map->ops->elt_alloc(elt);  in tracing_map_elt_alloc()
452 static struct tracing_map_elt *get_free_elt(struct tracing_map *map)  in get_free_elt()  argument
457 	idx = atomic_fetch_add_unless(&map->next_elt, 1, map->max_elts);  in get_free_elt()
458 	if (idx < map->max_elts) {  in get_free_elt()
459 		elt = *(TRACING_MAP_ELT(map->elts, idx));  in get_free_elt()
460 		if (map->ops && map->ops->elt_init)  in get_free_elt()
461 			map->ops->elt_init(elt);  in get_free_elt()
467 static void tracing_map_free_elts(struct tracing_map *map)  in tracing_map_free_elts()  argument
471 	if (!map->elts)  in tracing_map_free_elts()
474 	for (i = 0; i < map->max_elts; i++) {  in tracing_map_free_elts()
475 		tracing_map_elt_free(*(TRACING_MAP_ELT(map->elts, i)));  in tracing_map_free_elts()
476 		*(TRACING_MAP_ELT(map->elts, i)) = NULL;  in tracing_map_free_elts()
479 	tracing_map_array_free(map->elts);  in tracing_map_free_elts()
480 	map->elts = NULL;  in tracing_map_free_elts()
483 static int tracing_map_alloc_elts(struct tracing_map *map)  in tracing_map_alloc_elts()  argument
487 	map->elts = tracing_map_array_alloc(map->max_elts,  in tracing_map_alloc_elts()
489 	if (!map->elts)  in tracing_map_alloc_elts()
492 	for (i = 0; i < map->max_elts; i++) {  in tracing_map_alloc_elts()
493 		*(TRACING_MAP_ELT(map->elts, i)) = tracing_map_elt_alloc(map);  in tracing_map_alloc_elts()
494 		if (IS_ERR(*(TRACING_MAP_ELT(map->elts, i)))) {  in tracing_map_alloc_elts()
495 			*(TRACING_MAP_ELT(map->elts, i)) = NULL;  in tracing_map_alloc_elts()
496 			tracing_map_free_elts(map);  in tracing_map_alloc_elts()
516 __tracing_map_insert(struct tracing_map *map, void *key, bool lookup_only)  in __tracing_map_insert()  argument
523 	key_hash = jhash(key, map->key_size, 0);  in __tracing_map_insert()
526 	idx = key_hash >> (32 - (map->map_bits + 1));  in __tracing_map_insert()
529 		idx &= (map->map_size - 1);  in __tracing_map_insert()
530 		entry = TRACING_MAP_ENTRY(map->map, idx);  in __tracing_map_insert()
536 			    keys_match(key, val->key, map->key_size)) {  in __tracing_map_insert()
538 					atomic64_inc(&map->hits);  in __tracing_map_insert()
554 				if (dup_try > map->map_size) {  in __tracing_map_insert()
555 					atomic64_inc(&map->drops);  in __tracing_map_insert()
569 				elt = get_free_elt(map);  in __tracing_map_insert()
571 					atomic64_inc(&map->drops);  in __tracing_map_insert()
576 				memcpy(elt->key, key, map->key_size);  in __tracing_map_insert()
583 				atomic64_inc(&map->hits);  in __tracing_map_insert()
604  * @map: The tracing_map to insert into
610  * with it.  When the map was created, the number of elements to be
611  * allocated for the map was specified (internally maintained as
623  * This is a lock-free tracing map insertion function implementing a
631  * tracing map and safely access the key/val pairs.
639 struct tracing_map_elt *tracing_map_insert(struct tracing_map *map, void *key)  in tracing_map_insert()  argument
641 	return __tracing_map_insert(map, key, false);  in tracing_map_insert()
646  * @map: The tracing_map to perform the lookup on
661 struct tracing_map_elt *tracing_map_lookup(struct tracing_map *map, void *key)  in tracing_map_lookup()  argument
663 	return __tracing_map_insert(map, key, true);  in tracing_map_lookup()
668  * @map: The tracing_map to destroy
674  * reading or inserting into the map before calling this.
676 void tracing_map_destroy(struct tracing_map *map)  in tracing_map_destroy()  argument
678 	if (!map)  in tracing_map_destroy()
681 	tracing_map_free_elts(map);  in tracing_map_destroy()
683 	tracing_map_array_free(map->map);  in tracing_map_destroy()
684 	kfree(map);  in tracing_map_destroy()
689  * @map: The tracing_map to clear
691  * Resets the tracing map to a cleared or initial state.  The
696  * into the map before calling this.
698 void tracing_map_clear(struct tracing_map *map)  in tracing_map_clear()  argument
702 	atomic_set(&map->next_elt, 0);  in tracing_map_clear()
703 	atomic64_set(&map->hits, 0);  in tracing_map_clear()
704 	atomic64_set(&map->drops, 0);  in tracing_map_clear()
706 	tracing_map_array_clear(map->map);  in tracing_map_clear()
708 	for (i = 0; i < map->max_elts; i++)  in tracing_map_clear()
709 		tracing_map_elt_clear(*(TRACING_MAP_ELT(map->elts, i)));  in tracing_map_clear()
712 static void set_sort_key(struct tracing_map *map,  in set_sort_key()  argument
715 	map->sort_key = *sort_key;  in set_sort_key()
719  * tracing_map_create - Create a lock-free map and element pool
720  * @map_bits: The size of the map (2 ** map_bits)
721  * @key_size: The size of the key for the map in bytes
723  * @private_data: Client data associated with the map
725  * Creates and sets up a map to contain 2 ** map_bits number of
727  * tracing_map).  Before using, map fields should be added to the map
730  * tracing_map_elts, in order to avoid allocating anything in the map
731  * insertion path.  The user-specified map size reflects the maximum
736  * A tracing_map is a special-purpose map designed to aggregate or
738  * tracing_map_elt, which is attached by the map to a given key.
740  * tracing_map_create() sets up the map itself, and provides
744  * tracing_map_elts for a given map have the same set of sums and
747  * the fields are defined, the pool of elements allocated for the map
752  * inserted into the map using tracing_map_insert().  When called,
754  * finds an existing match in the map and in either case returns it.
773 	struct tracing_map *map;  in tracing_map_create()  local
780 	map = kzalloc(sizeof(*map), GFP_KERNEL);  in tracing_map_create()
781 	if (!map)  in tracing_map_create()
784 	map->map_bits = map_bits;  in tracing_map_create()
785 	map->max_elts = (1 << map_bits);  in tracing_map_create()
786 	atomic_set(&map->next_elt, 0);  in tracing_map_create()
788 	map->map_size = (1 << (map_bits + 1));  in tracing_map_create()
789 	map->ops = ops;  in tracing_map_create()
791 	map->private_data = private_data;  in tracing_map_create()
793 	map->map = tracing_map_array_alloc(map->map_size,  in tracing_map_create()
795 	if (!map->map)  in tracing_map_create()
798 	map->key_size = key_size;  in tracing_map_create()
800 		map->key_idx[i] = -1;  in tracing_map_create()
802 	return map;  in tracing_map_create()
804 	tracing_map_destroy(map);  in tracing_map_create()
805 	map = ERR_PTR(-ENOMEM);  in tracing_map_create()
811  * tracing_map_init - Allocate and clear a map's tracing_map_elts
812  * @map: The tracing_map to initialize
816  * 'max_elts' in struct tracing_map).  Before using, the map fields
817  * should be added to the map with tracing_map_add_sum_field() and
820  * allocating anything in the map insertion path.  The user-specified
821  * map size reflects the max number of elements requested by the user
829 int tracing_map_init(struct tracing_map *map)  in tracing_map_init()  argument
833 	if (map->n_fields < 2)  in tracing_map_init()
836 	err = tracing_map_alloc_elts(map);  in tracing_map_init()
840 	tracing_map_clear(map);  in tracing_map_init()
852 	return memcmp(a->key, b->key, a->elt->map->key_size);  in cmp_entries_dup()
871 	sort_key = &elt_a->map->sort_key;  in cmp_entries_sum()
902 	sort_key = &elt_a->map->sort_key;  in cmp_entries_key()
988 static bool is_key(struct tracing_map *map, unsigned int field_idx)  in is_key()  argument
992 	for (i = 0; i < map->n_keys; i++)  in is_key()
993 		if (map->key_idx[i] == field_idx)  in is_key()
998 static void sort_secondary(struct tracing_map *map,  in sort_secondary()  argument
1008 	if (is_key(map, primary_key->field_idx))  in sort_secondary()
1013 	if (is_key(map, secondary_key->field_idx))  in sort_secondary()
1034 		set_sort_key(map, secondary_key);  in sort_secondary()
1038 		set_sort_key(map, primary_key);  in sort_secondary()
1046  * tracing_map_sort_entries - Sort the current set of tracing_map_elts in a map
1047  * @map: The tracing_map
1053  * map and returns the list of tracing_map_sort_entries containing
1070 int tracing_map_sort_entries(struct tracing_map *map,  in tracing_map_sort_entries()  argument
1079 	entries = vmalloc(array_size(sizeof(sort_entry), map->max_elts));  in tracing_map_sort_entries()
1083 	for (i = 0, n_entries = 0; i < map->map_size; i++) {  in tracing_map_sort_entries()
1086 		entry = TRACING_MAP_ENTRY(map->map, i);  in tracing_map_sort_entries()
1109 	detect_dups(entries, n_entries, map->key_size);  in tracing_map_sort_entries()
1111 	if (is_key(map, sort_keys[0].field_idx))  in tracing_map_sort_entries()
1116 	set_sort_key(map, &sort_keys[0]);  in tracing_map_sort_entries()
1122 		sort_secondary(map,  in tracing_map_sort_entries()